[Python-Dev] sum()

[Raymond Hettinger]

> [Tim Peters]
> Summer.add() _can_ lose info -- it needs additional
> trickery to make it loss-free, and because x+y can lose (at most one
> bit) when x and y have the same binary exponent.

Computing an error term can get the bit back and putting that term back
in the input queue restores the overall sum.  Once the inputs are
exhausted, the components of exp2sum should be exact.



from math import frexp
from itertools import chain

def summer2(iterable):
    exp2sum = {}    
    queue = []
    for x in chain(iterable, queue):
        mant, exp = frexp(x)        
        while exp in exp2sum:
            y = exp2sum.pop(exp)
            z = x + y
            d = x - z + y   # error term
            assert z + d == x + y
            if d:
                queue.append(d)
            x = z
            mant, exp = frexp(x)
        exp2sum[exp] = x
    return sum(sorted(exp2sum.itervalues(), key=abs), 0.0)


The implementation can be tweaked to consume the error term right away
so the queue won't grow by more than few pending items.  Also, the speed
can be boosted by localizing frexp, exp2sum.pop, and queue.append.


Raymond Hettinger