Kahan Compensated Sum

In [8]:

    

from functools import reduce


    

In [9]:

    

def kahan_sum(xs):
    s = c = 0
    for x in xs:
        v = x + c
        s_next = s + v
        c = v - (s_next - s)
        s = s_next
        
    return s

def naive_sum(xs):
    return reduce(lambda x, y: x + y, xs)


    

In [14]:

    

a = [1e-10] * 100

naive_sum(a) == kahan_sum(a)


    

    
Out[14]:





False

In [18]:

    

naive_sum(a) == sum(a)


    

    
Out[18]:





True

In [17]:

    

naive_sum(a)


    

    
Out[17]:





9.999999999999985e-09

In [16]:

    

kahan_sum(a)


    

    
Out[16]:





1e-08