2 ms·
Errors grow exponentially in most floating-point operations. The exception is cancellation error, which can suddenly cause the error rate to spike dramatically
by dragontamer 5y ago
Errors grow exponentially in most floating-point operations.
The exception is cancellation error, which can suddenly cause the error rate to spike dramatically. But if you sort your numbers before adding/subtracting, you can often negate this overwhelming cancellation error.
The exponential growth of other floating point errors is almost unstoppable however. The only real way to stop it is to design an algorithm that operates with fewer steps.
---------
64-bit has a much smaller initial error (1/2^53), while 32-bit has (1/2^23) initial errors... starting with 30-magnitudes more error than double-precision.
- vlovich123 5y agoKahan 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.