The exact sum
You are given n numbers written in decimal. Read each as an ordinary double-precision floating-point number (float in Python, float64 in Go) and print two sums.
- The sum added in order from left to right, with the result rounded to
float64after each addition: what an ordinary loop does. - The exact sum of the same
float64numbers, as if it were computed with no rounding at all, rounded to the nearestfloat64once, at the very end.
Input
The first line holds n (1 ≤ n ≤ 2·10⁵). Then come n numbers, one per line, for example 0.1, -149.90 or 3.5e120; each at most 10³⁰⁰ in absolute value.
Output
Two lines: the sum in order and the exact sum, each in the %.17g format (17 significant digits, as printed by f"{x:.17g}" in Python and fmt.Printf("%.17g") in Go).
Examples
Example 1
5 1e100 1 -1e100 0.1 0.2
0.30000000000000004 1.3
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The first line is an ordinary loop. For the second you must not round even once until the very end. What precision is enough for a sum of any float64 numbers to be computed without loss?
2The idea
Any float64 number is a binary fraction: at most 53 significant bits, and the positions of these bits lie between 2¹⁰²³ and 2⁻¹⁰⁷⁴. The sum of two hundred thousand such numbers fits into a binary number of about 2120 bits. So addition with a margin of 2200 bits of precision will not lose a single bit: in Go that is big.Float with SetPrec(2200), and at the end Float64() rounds to the nearest. In Python math.fsum does the same: it keeps the sum as several float numbers that together represent it exactly (Shewchuk’s algorithm), and rounds once.
3Walkthrough
Kahan’s correction, which looks like a ready solution, will not do here. It keeps one correction, what was lost in the previous addition, and fixes slow drift well, when small numbers are added to a large sum many times. But in the first example a one stands between 10¹⁰⁰ and −10¹⁰⁰: when added to 10¹⁰⁰ it is lost entirely, the correction becomes −1, and when 10¹⁰⁰ is subtracted there is nothing left to apply the correction to: it is lost again against the huge number. Kahan gives 0.3 instead of 1.3. Neumaier’s variant, which became built into sum() in Python 3.12, copes with this example, but it too does not guarantee an exact answer on all data; the exact sum comes only with a margin of bits.
Look at the tests. In the fifth, a hundred thousand ones are added to 10¹⁶: the loop returns exactly 10¹⁶: neighbouring float64 numbers near 10¹⁶ are 2 apart, a one is exactly half a step, and rounding to even throws it away every time. In the sixth, huge numbers cancel each other, and the sum in order comes out around −10²⁸⁷ instead of −212 thousand. In the fourth, the daily rainfall in Almaty over 85 years: the sum in order differs from the exact one only in the 15th digit, but it differs.
3+Solution
4Complexity
O(n) for the loop. The exact sum is O(n) additions of long 2200-bit numbers in Go; math.fsum in Python usually keeps only a few parts and runs almost as fast as the loop.
5Common mistakes
- Kahan’s correction. Goes wrong when a small number is squeezed between huge ones of different sign: the first and sixth tests.
- The built-in
sum()for the first line. Since Python 3.12 it adds with Neumaier’s correction, and that is no longer “in order with rounding after each step”: an explicit loop is needed. - Sorting before adding. Adding from small to large reduces the error but does not remove it.