Kahan summation, adding a million small numbers
Asked at HRT, Jump Trading
Sum ten million copies of 0.1 with a plain loop and you will not get one million:
>>> total = 0.0
>>> for _ in range(10_000_000): total += 0.1
>>> total
999999.9998389754
The error is thousands of times one ulp. Explain where the error comes from, and implement a summation that fixes it without higher-precision arithmetic.
Show a hint
When you compute t = total + y with total large and y small, the low-order bits of y are rounded away. Can you compute exactly what was rounded away, using only float operations?
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.