DuckDB fsum returns a sum that is off by one rounding step
In DuckDB 2.0.0, fsum returns a sum that is off by one rounding step.
Reproduce it
SELECT fsum(v) FROM (VALUES (0.1::DOUBLE), (0.3)) t(v);
DuckDB 2.0.0 returns:
0.39999999999999997
The correct answer
The correct answer is 0.4.
from fractions import Fraction as F
def fsum(values):
# the exact sum, rounded once to a double
return float(sum(F(v) for v in values))
print(fsum([0.1, 0.3])) # 0.4
Why DuckDB gets it wrong
DuckDB's fsum applies a Kahan correction that is itself rounded. Applying it moves the sum off the correctly rounded result.
Kahan Algorithm
- adjusted value = value − correction
- new sum = old sum + adjusted value
- correction = (new sum − old sum) − adjusted value
- merge: add the sum, then minus the correction, into an empty sum with steps 1–3
- result = sum
| Value | Adjusted | Sum | Correction | Explanation |
|---|---|---|---|---|
| — | — | 0 | 0 | init |
| 0.1 | 0.1 | 0.1 | 0 | First value into the sum |
| 0.3 | 0.3 | 0.4 | 5.551115123125783e-17 | 0.4 − 0.1 rounds to 0.30000000000000004, so the correction is twice the real loss |
| merge: 0.4 | 0.4 | 0.4 | 0 | The partial state is merged into an empty one: the sum |
| merge: −5.551115123125783e-17 | −5.551115123125783e-17 | 0.39999999999999997 | 0 | Then minus the correction, which moves the sum one rounding step below 0.4 |
Result: fsum returns the sum, 0.39999999999999997.
How to fix it
A fixed-point sum keeps the sum exact by adding every value as a whole number of units of the smallest double.
Fixed-Point Algorithm
- Start with a sum of 0
- Turn each value into a whole number of units of the smallest double (value × 2^1074)
- Add that whole number to the sum exactly
Final Step: result = sum × 2^−1074, rounded once
| Value | Units | Sum (units) | Explanation |
|---|---|---|---|
| — | — | 0 | init |
| 0.1 | 0.1 × 2^1074 | 0.1 × 2^1074 | First value into the sum, exactly |
| 0.3 | 0.3 × 2^1074 | (0.1 + 0.3) × 2^1074 | Added exactly, so nothing is lost |
Result: (0.1 + 0.3) × 2^1074 × 2^−1074 = 0.39999999999999999444…, halfway between 0.39999999999999997 and 0.4, and the tie rounds to 0.4.
Vendor issue
Reported to DuckDB as duckdb/duckdb#28165.
writePath
FSUM function
writePath's FSUM uses an exact fixed-point sum. No precision is lost because every value is added as a whole number. The sum is rounded once at the end, so the result is the most precise double. The result does not depend on row order.
About us
writePath is an AWS Marketplace SaaS for sub-millisecond aggregations over the first or last N rows of your data with no pre-computation. It offers 65 high-precision aggregation functions tested against reference implementations.