Skip to the content ForoHackers
Log inJoin

Adding the same floats in a different order gives a different answer

Computer architectureNumerical analysisPython
#1067 · bitflip_betty · · Report

A fun one for anyone who thinks floating point is just "a bit imprecise":

>>> (1e16 + 1.0) + -1e16
0.0
>>> (1e16 + -1e16) + 1.0
1.0

(Python's built-in sum on floats has used compensated summation since 3.12, so I spell the additions out.) Same three numbers. Different answers. The reason: a 64-bit float has 53 bits of mantissa, so near 1e16 the spacing between representable numbers is 2. Adding 1.0 to 1e16 lands halfway between two representable values and rounds to even, which gives back 1e16. The 1.0 is simply gone before the -1e16 arrives.

Floating-point addition is commutative but not associative. This matters in practice:

  • parallel reductions (GPU, threads, SIMD) change the order of additions, so results differ run to run or machine to machine;
  • compilers are not allowed to reorder your sums unless you ask for it with something like -ffast-math.

Mitigations: sort by magnitude, use pairwise summation, Kahan compensated summation, or math.fsum in Python, which tracks partial sums exactly and returns 1.0 for [1e16, 1.0, -1e16] in either order.

No cosmic rays involved here. For once, the arithmetic is guilty all by itself.

#1630 · undefined_behaviour_enjoyer · · Report

And -ffast-math is the classic "I asked for it" trap: it lets the compiler assume no NaNs or infinities and reassociate freely, so your carefully written Kahan summation can be optimised into a plain sum. Compensated algorithms and fast-math do not get along.

#1631 · off_by_two · · Report

Puzzle version: find three numbers where the order of addition changes the result of a three-term sum, using only small integers as floats. (Hint: it is impossible below 2^53. Why?)

#1632 · bitflip_betty · · Report

Because every integer below 2^53 and every partial sum of small integers is exactly representable, so no rounding ever happens and addition behaves associatively. Nice one. The trouble starts when the intermediate result needs more than 53 bits.

#1633 · regex_regret · · Report

math.fsum is one of those standard library functions I wish more people knew. I have replaced a hand-written Kahan loop with it more than once and nobody missed the loop.

#1634 · hexdump_hermit · · Report

Historic footnote: on 32-bit x86 builds using the x87 unit, intermediate sums were held in 80-bit registers, so the same C source could give yet another answer depending on whether a value was spilled to memory. Reproducibility was a property of the register allocator.

Log in or join to reply.