[Libreoffice-commits] core.git: sc/inc

[dante (via logerrit)]

 sc/inc/kahan.hxx |  136 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 sc/inc/math.hxx  |    1 
 2 files changed, 137 insertions(+)

New commits:
commit 9c4e0c35d70659097b235028047efcb80dcfb10d
Author:     dante <dante19031999 at gmail.com>
AuthorDate: Fri Apr 23 20:04:11 2021 +0200
Commit:     Mike Kaganski <mike.kaganski at collabora.com>
CommitDate: Mon Apr 26 12:51:11 2021 +0200

    Add a Kahan summation class.
    
    Change-Id: I4021d07a2c011c2d5b2e79ecd878019d29cabd21
    Reviewed-on: https://gerrit.libreoffice.org/c/core/+/114567
    Tested-by: Jenkins
    Reviewed-by: Mike Kaganski <mike.kaganski at collabora.com>

diff --git a/sc/inc/kahan.hxx b/sc/inc/kahan.hxx
new file mode 100644
index 000000000000..45b59617e2b7
--- /dev/null
+++ b/sc/inc/kahan.hxx
@@ -0,0 +1,136 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4; fill-column: 100 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ */
+
+#pragma once
+
+/**
+  * This class provides LO with Kahan summation algorithm
+  * About this algorithm: https://en.wikipedia.org/wiki/Kahan_summation_algorithm
+  * For general purpose software we assume first order error is enough.
+  * This class could be made constexpr if needed.
+  */
+
+class KahanSum
+{
+public:
+    constexpr KahanSum() = default;
+
+    constexpr KahanSum(double x_0)
+        : m_fSum(x_0)
+    {
+    }
+
+    constexpr KahanSum(const KahanSum& fSum) = default;
+
+public:
+    /**
+      * Adds a value to the sum using Kahan sumation.
+      * @param x_i
+      */
+    void add(double x_i)
+    {
+        double t = m_fSum + x_i;
+        if (std::abs(m_fSum) >= std::abs(x_i))
+            m_fError += (m_fSum - t) + x_i;
+        else
+            m_fError += (x_i - t) + m_fSum;
+        m_fSum = t;
+    }
+
+    /**
+      * Adds a value to the sum using Kahan sumation.
+      * @param fSum
+      */
+    inline void add(const KahanSum& fSum)
+    {
+        add(fSum.m_fSum);
+        add(fSum.m_fError);
+    }
+
+public:
+    constexpr KahanSum operator-() const
+    {
+        KahanSum fKahanSum;
+        fKahanSum.m_fSum = -m_fSum;
+        fKahanSum.m_fError = -m_fError;
+        return fKahanSum;
+    }
+
+    constexpr KahanSum& operator=(double fSum)
+    {
+        m_fSum = fSum;
+        m_fError = 0;
+        return *this;
+    }
+
+    constexpr KahanSum& operator=(const KahanSum& fSum) = default;
+
+    inline void operator+=(const KahanSum& fSum) { add(fSum); }
+
+    inline void operator+=(double fSum) { add(fSum); }
+
+    inline void operator-=(const KahanSum& fSum) { add(-fSum); }
+
+    inline void operator-=(double fSum) { add(-fSum); }
+
+    /**
+      * In some parts of the code of interpr_.cxx this may be used for
+      * productory instead of sum. This operator shall be used for that task.
+      */
+    constexpr void operator*=(double fTimes)
+    {
+        m_fSum *= fTimes;
+        m_fError *= fTimes;
+    }
+
+    constexpr void operator/=(double fDivides)
+    {
+        m_fSum /= fDivides;
+        m_fError /= fDivides;
+    }
+
+    constexpr bool operator<(const KahanSum& fSum) const { return get() < fSum.get(); }
+
+    constexpr bool operator<(double fSum) const { return get() < fSum; }
+
+    constexpr bool operator>(const KahanSum& fSum) const { return get() > fSum.get(); }
+
+    constexpr bool operator>(double fSum) const { return get() > fSum; }
+
+    constexpr bool operator<=(const KahanSum& fSum) const { return get() <= fSum.get(); }
+
+    constexpr bool operator<=(double fSum) const { return get() <= fSum; }
+
+    constexpr bool operator>=(const KahanSum& fSum) const { return get() >= fSum.get(); }
+
+    constexpr bool operator>=(double fSum) const { return get() >= fSum; }
+
+    constexpr bool operator==(const KahanSum& fSum) const
+    {
+        return fSum.m_fSum == m_fSum && fSum.m_fError == m_fError;
+    }
+
+    constexpr bool operator!=(const KahanSum& fSum) const
+    {
+        return fSum.m_fSum != m_fSum || fSum.m_fError != m_fError;
+    }
+
+public:
+    /**
+      * Returns the final sum.
+      * @return final sum
+      */
+    constexpr double get() const { return m_fSum + m_fError; }
+
+private:
+    double m_fSum = 0;
+    double m_fError = 0;
+};
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab cinoptions=b1,g0,N-s cinkeys+=0=break: */
diff --git a/sc/inc/math.hxx b/sc/inc/math.hxx
index 2e2ffe0f4bb6..459b82e74bcd 100644
--- a/sc/inc/math.hxx
+++ b/sc/inc/math.hxx
@@ -21,6 +21,7 @@
 
 #include <formula/errorcodes.hxx>
 #include <rtl/math.hxx>
+#include "kahan.hxx"
 
 namespace sc {