2 ms·
Kahan summation[1] may be better than just doing a sorted sum & doesn't require you have all the numbers up-front to sort (i.e. running sum). Although I think e
by vlovich123 5y ago
Kahan summation[1] may be better than just doing a sorted sum & doesn't require you have all the numbers up-front to sort (i.e. running sum). Although I think even it benefits from doing it in sorted order if you do have the full history available & the wikipedia article lists a parallelization technique you can leverage in that case. Klein sum might be better but I haven't investigated.
EDIT: Apparently there's a nice Rust crate for doing this stuff: https://crates.io/crates/accurate https://crates.io/crates/accurate
[1] https://en.wikipedia.org/wiki/Kahan_summation_algorithm#Alternatives https://en.wikipedia.org/wiki/Kahan_summation_algorithm#Alte...
- adgjlsfhk1 5y agoOne thing to consider here is XSum. It's a C library that has surprisingly fast exact floating point sums.
- a1369209993 5y agoKahan summation is basically just synthesizing a larger floating point type (with 46/106 bits of mantissa for 32/64-bit base type) and then using that to do the sum, though. You still lose precision if your errors exceed that new, larger margin. Eg try adding 34000 + 56 + .078 - 56 - 34000, carrying two digits per float.