This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author mark.dickinson
Recipients MrJean1, mark.dickinson, rhettinger
Date 2008-05-16.14:47:56
SpamBayes Score 0.0748157
Marked as misclassified No
Message-id <1210949320.22.0.487138765065.issue2819@psf.upfronthosting.co.za>
In-reply-to
Content
Here's (msum.py) an example in Python of one fairly straightforward way of 
dealing with overflow correctly, without needing more than one pass 
through the data, and without significant slowdown in the normal case.
(The Python code is needlessly inefficient in places, notably in that 
partials[1:] creates a new list;  this is obviously not a problem in C.)

The idea is essentially just to maintain the sum modulo integer multiples 
of 2.**1024.  partials[0] is reserved for keeping track of the current 
multiple of 2.**!024.  So at each stage, the sum so far is 
sum(partials[1:], 0.0) + 2.**1024 * partials[0].

I'm 97.3% convinced that the proof of correctness goes through:  it's 
still true with this modification that partials always consists of 
nonadjacent, nonzero values of increasing magnitude.  One of the keys to proving this is to note that for any value x between 2**1023 and 2**1024, 
both x-2**1023 and x-2**1024 are exactly representable.

---

There's one more 'nice-to-have' that I think should be considered:  it 
would be nice if the result of msum were always correctly rounded.  One 
aspect of correct rounding is that it provides a guarantee that the sum is 
independent of the order of the summands, so

msum(list) == msum(sorted(list))

would hold true.
History
Date User Action Args
2008-05-16 14:48:43mark.dickinsonsetspambayes_score: 0.0748157 -> 0.0748157
recipients: + mark.dickinson, rhettinger, MrJean1
2008-05-16 14:48:40mark.dickinsonsetspambayes_score: 0.0748157 -> 0.0748157
messageid: <1210949320.22.0.487138765065.issue2819@psf.upfronthosting.co.za>
2008-05-16 14:48:34mark.dickinsonlinkissue2819 messages
2008-05-16 14:48:27mark.dickinsoncreate