[Python-Dev] sum() (original) (raw)

Tim Peters tim.peters at gmail.com
Sun Mar 13 02:30:03 CET 2005

[Raymond Hettinger]

The approach I'm using relies on being able to exactly multiply the 0 or 1 bit error term mantissas by an integer (a count of how many times the term occurs). With a Python dictionary keeping the counts, many steps are saved and the tool becomes much more memory friendly than with the previous queue approach.

Cool! That's a nice approach.

For contrast, here's one that doesn't use frexp(), and is probably faster because of that; internally, len(sums) probably won't exceed 5 in real life (but could get as large as 2K for pathological inputs, spanning fp's full dynamic range):

def summer4(iterable): sums = [0.0] for x in iterable: sums.append(x) for i in xrange(len(sums)-2, -1, -1): y = sums[i] if abs(x) < abs(y): x, y = y, x hi = x+y lo = y - (hi - x) if lo: sums[i+1] = lo else: del sums[i+1] x = hi sums[0] = x return sum(reversed(sums), 0.0)

In effect, that keeps an arbitrarily long list of "error terms" so that no info is lost before the final sum(). I think it's surprising at first how short that list usually is.

... Aside from being a nice recipe, this was a good exercise in seeing what pure Python can do with IEEE-754 guarantees.

Now you know I how feel everytime sometime proclaims that fp arithmetic is inherently unreliable <0.3 wink>. Learning how to use it correctly is indeed the blackest of obscure arts, though.

The modest memory consumption and the typical O(n) runtime are a nice plus (no pun intended).

Yup, they're all emminently practical if you don't care too much about speed. The one above is the fastest I tried, and it still takes some 40x longer than plain sum() over a million-element random.random() list.

More information about the Python-Dev mailing list