3 ms·
How does it compare to converting each number to a large fixed-point integer (implemented as N 64-bit integers), summing them with exact integer math (order-inv
by kardos 2y ago
How does it compare to converting each number to a large fixed-point integer (implemented as N 64-bit integers), summing them with exact integer math (order-invariant), and converting back to floating point at the end?
The sum part can be done with AVX-512 [1] if N=8, and N=8 is probably enough for a lot of real world summations. The conversion back to floating point at the end is only done once so not very costly.
The conversion to fixed point is probably the worst part. Is there a faster way to do it than a loop that extracts one 64-bit integer per iteration? If not we could convert several input numbers at a time with SIMD. But it would be nifty to be able to convert one double to N integers with SIMD instead of a loop.
[1] http://www.numberworld.org/y-cruncher/internals/addition.html#ks_add http://www.numberworld.org/y-cruncher/internals/addition.htm...
- deleted 2y ago[deleted]
- moonchild 2y agosee xsum https://gitlab.com/radfordneal/xsum https://gitlab.com/radfordneal/xsum
- kardos 2y agoThanks! Yes this is exactly it. Interesting about the choice of 32 bits for carries. N=67 is pretty high. I suspect N could be tuned down significantly depending on the problem. Eg global sums in geophysics models -- the range of values being summed does not span the full double range. But that would require analysis to decide about, while the full sized superaccumulator works directly. I wonder how it stacks up in terms of performance w/r/t the methods in the blog post
- zokier 2y agoN=5 should cover easily single precision float range. Doubles are more tricky, you'd need N=33
- kardos 2y agoAgree if we need exact for any range of inputs. It should be possible to get by with fewer for real life problems, for ex, https://www.sciencedirect.com/science/article/abs/pii/S0167819114000507 https://www.sciencedirect.com/science/article/abs/pii/S01678...