core practice · coding problem
Log-sum-exp without overflow
Implement logSumExp(xs) returning log(sum(exp(x))) that stays finite for large inputs by subtracting the maximum first. Must return a finite number for [1000, 1001, 1002], where the naive form overflows to Infinity.
The mechanism
Floating point stores a fixed number of significant digits, so error is relative, not absolute — and subtracting two nearly equal numbers throws away the leading digits that agreed, leaving noise promoted to the front. That is catastrophic cancellation, and it is why the naive variance formula and the quadratic formula both fail. The standard fixes are algebraic rather than numerical: reorder to avoid the subtraction, or shift into a domain where the range is safe, which is exactly what log-sum-exp does by subtracting the max before exponentiating.
Expected evidence
logSumExp([1000,1001,1002]) ~ 1002.4076; logSumExp([0,0]) ~ 0.6931
Try this drill in the practice workspace →
Hints when you need them
- log(sum(exp(x))) = m + log(sum(exp(x - m))) where m is the max — algebraically identical, numerically safe.
- Handle an all -Infinity input without producing NaN.
Watch for these mistakes
- Comparing floats with ==; use a tolerance scaled to the magnitude, not an absolute epsilon
- Summing a long series left to right, letting small terms vanish against a large running total
- Exponentiating raw logits and overflowing before the softmax normalises
- Assuming double precision hides the problem — it postpones cancellation, it does not prevent it