sc/inc/kahan.hxx | 136 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ sc/inc/math.hxx | 1 2 files changed, 137 insertions(+)
New commits: commit 9c4e0c35d70659097b235028047efcb80dcfb10d Author: dante <[email protected]> AuthorDate: Fri Apr 23 20:04:11 2021 +0200 Commit: Mike Kaganski <[email protected]> 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 <[email protected]> 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 { _______________________________________________ Libreoffice-commits mailing list [email protected] https://lists.freedesktop.org/mailman/listinfo/libreoffice-commits
