Actually I don't actually have that array, I have a stream of numbers that get generated. I can imagine a class storing numbers in magnitude buckets, adding numbers of the same magnitude and moving numbers to the next bucket if they exceed their bucket limit. But that seems rather involved.
> In particular, simply summing n numbers in sequence has a worst-case error that grows proportional to n, and a root mean square error that grows as √n for random inputs (the roundoff errors form a random walk).[2] With compensated summation, the worst-case error bound is effectively independent of n, so a large number of values can be summed with an error that only depends on the floating-point precision.[2]
there are only 2 variables that are kept between iterations, so by simple pigeon holing the accuracy cannot exceed the double the accuracy of a single number
Yeah, they are all pretty close to each other. The issue is that the accumulator eventually drifts so far away from the values that error accumulation becomes really bad.
and you have to ensure your compiler doesn't do associative float addition optimization (IOW disable -fastmath)
> A careful analysis of the errors in compensated summation is needed to appreciate its accuracy characteristics. While it is more accurate than naive summation, it can still give large relative errors for ill-conditioned sums.
@ratchetfreak Yeah--Kahan summation handles like 99% of cases, with only minimal (like 2:1) loss of speed. But yes, there are still a few truly horrendous cases that benefit from other (slower) methods. For a truly terrible case, another possibility is to start by separating the numbers into positive and negative. Put all of the numbers of the same sign into a priority queue sorted by smallest magnitude. Grab two numbers from the PQ, sum them, push the result. Repeat until only one number remains.
Do the same with the numbers of the other sign.When you're done, add the two sums together.
I'm not sure though--it may be better to leave the positives and negatives together, so you're working with both when they're as close as possible to the same magnitude.
@Mikhail There was once something that used something like base 80, if memory serves. As I recall, at least at the time they did some testing and concluded there were only a few more characters they could potentially use, and base 84 (or whatever) didn't make enough difference to be worth the trouble.