Editing Kahan summation algorithm (section)

==Further enhancements==
Neumaier<ref name=Neumaier74>{{cite journal |first=A. |last=Neumaier |doi=10.1002/zamm.19740540106 |bibcode=1974ZaMM...54...39N |title=Rundungsfehleranalyse einiger Verfahren zur Summation endlicher Summen |trans-title=Rounding Error Analysis of Some Methods for Summing Finite Sums |language=de |journal=[[Zeitschrift für Angewandte Mathematik und Mechanik]] |volume=54 |issue=1 |date=1974 |pages=39–51 |url=https://www.mat.univie.ac.at/~neum/scan/01.pdf}}</ref> introduced an improved version of Kahan algorithm, which he calls an "improved Kahan–Babuška algorithm", which also covers the case when the next term to be added is larger in absolute value than the running sum, effectively swapping the role of what is large and what is small. In [[pseudocode]], the algorithm is:
 
 '''function''' KahanBabushkaNeumaierSum(input)
     '''var''' sum = 0.0
     '''var''' c = 0.0                       // A running compensation for lost low-order bits.
 
     '''for''' i = 1 '''to''' input.length '''do'''
         '''var''' t = sum + input[i]
         '''if''' |sum| >= |input[i]| '''then'''
             c += (sum - t) + input[i] // If ''sum'' is bigger, low-order digits of ''input[i]'' are lost.
         '''else'''
             c += (input[i] - t) + sum // Else low-order digits of ''sum'' are lost.
         '''endif'''
         sum = t
     '''next''' i
 
     '''return''' sum + c                    // Correction only applied once in the very end.

This enhancement is similar to the Fast2Sum version of Kahan's algorithm with Fast2Sum replaced by [[2Sum]].

For many sequences of numbers, both algorithms agree, but a simple example due to Peters<ref name="python_fsum" /> shows how they can differ: summing <math>[1.0, +10^{100}, 1.0, -10^{100}]</math> in double precision, Kahan's algorithm yields 0.0, whereas Neumaier's algorithm yields the correct value 2.0.

Higher-order modifications of better accuracy are also possible. For example, a variant suggested by Klein,<ref>{{Cite journal |last=A. |first=Klein |date=2006 |title=A generalized Kahan–Babuška-Summation-Algorithm |journal=Computing |volume=76 |issue=3–4 |pages=279–293 |publisher=Springer-Verlag |doi=10.1007/s00607-005-0139-x |s2cid=4561254 }}</ref> which he called a second-order "iterative Kahan–Babuška algorithm". In [[pseudocode]], the algorithm is:

 '''function''' KahanBabushkaKleinSum(input)
     '''var''' sum = 0.0
     '''var''' cs  = 0.0
     '''var''' ccs = 0.0
 
     '''for''' i = 1 '''to''' input.length '''do'''
         '''var''' c, cc
         '''var''' t = sum + input[i]
         '''if''' |sum| >= |input[i]| '''then'''
             c = (sum - t) + input[i]
         '''else'''
             c = (input[i] - t) + sum
         '''endif'''
         sum = t
         t = cs + c
         '''if''' |cs| >= |c| '''then'''
             cc = (cs - t) + c
         '''else'''
             cc = (c - t) + cs
         '''endif'''
         cs = t
         ccs = ccs + cc
     '''end loop''' 
 
     '''return''' sum + (cs + ccs)