Editing Kahan summation algorithm (section)

==Alternatives==
Although Kahan's algorithm achieves <math>O(1)</math> error growth for summing ''n'' numbers, only slightly worse <math>O(\log n)</math> growth can be achieved by [[pairwise summation]]: one [[recursively]] divides the set of numbers into two halves, sums each half, and then adds the two sums.<ref name=Higham93/>  This has the advantage of requiring the same number of arithmetic operations as the naive summation (unlike Kahan's algorithm, which requires four times the arithmetic and has a latency of four times a simple summation) and can be calculated in parallel.  The base case of the recursion could in principle be the sum of only one (or zero) numbers, but to amortize the overhead of recursion, one would normally use a larger base case.  The equivalent of pairwise summation is used in many [[fast Fourier transform]] (FFT) algorithms and is responsible for the logarithmic growth of roundoff errors in those FFTs.<ref>{{cite web |last1=Johnson |first1=S.G. |last2=Frigo |first2=M. |editor=C. Sidney Burns |title=Fast Fourier Transforms: Implementing FFTs in Practice |archive-url=https://web.archive.org/web/20081220074554/http://cnx.org/content/m16336/latest/ |archive-date=Dec 20, 2008 |url=http://cnx.org/content/m16336/latest/ |url-status=dead}}</ref> In practice, with roundoff errors of random signs, the root mean square errors of pairwise summation actually grow as <math>O\left(\sqrt{\log n}\right)</math>.<ref name=Tasche/>

Another alternative is to use [[arbitrary-precision arithmetic]], which in principle need no rounding at all with a cost of much greater computational effort.  A way of performing correctly rounded sums using arbitrary precision is to extend adaptively using multiple floating-point components. This will minimize computational cost in common cases where high precision is not needed.<ref>{{cite journal |last1=Richard Shewchuk |first1=Jonathan |title=Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates |journal=Discrete & Computational Geometry |date=October 1997 |volume=18 |issue=3 |pages=305–363 |doi=10.1007/PL00009321 |s2cid=189937041 |url=https://people.eecs.berkeley.edu/~jrs/papers/robustr.pdf}}</ref><ref name="python_fsum">{{cite web |last1=Hettinger |first1=R. |title=Improve accuracy of builtin sum() for float inputs · Issue #100425 · python/cpython |url=https://github.com/python/cpython/issues/100425 |website=GitHub - CPython v3.12 Added Features |access-date=7 October 2023 |language=en}}</ref>
Another method that uses only integer arithmetic, but a large accumulator, was described by Kirchner and [[Ulrich W. Kulisch|Kulisch]]; <ref>{{cite journal |last1=Kirchner |first1=R. |last2=Kulisch |first2=U. |title=Accurate arithmetic for vector processors |journal=Journal of Parallel and Distributed Computing |date=June 1988 |volume=5 |issue=3 |pages=250–270 |doi=10.1016/0743-7315(88)90020-2 |url=https://www.sciencedirect.com/science/article/abs/pii/0743731588900202|url-access=subscription }}</ref> a hardware implementation was described by Müller, Rüb and Rülling.<ref>{{cite conference |last1=Muller |first1=M. |last2=Rub |first2=C. |last3=Rulling |first3=W. |title=Exact accumulation of floating-point numbers |date=1991 |pages=64–69 |conference=Proceedings 10th IEEE Symposium on Computer Arithmetic |doi=10.1109/ARITH.1991.145535 |url=https://ieeexplore.ieee.org/document/145535|url-access=subscription }}</ref>