Closing the Loop on Floating-Point Error

Theodolite traverses return to their starting point specifically to measure accumulated error. You shoot a polygon around a property boundary, and when the final angle reading should close the loop, it doesn’t—off by eight arc-seconds, maybe twelve. That discrepancy is distributed backward through every measurement, each station getting its proportional correction.

Floating-point addition has the same problem. Add a million tiny numbers to a large running total and the small ones vanish into rounding error—the mantissa can’t hold both scales simultaneously. By the time you finish, you’ve lost precision you’ll never recover.

William Kahan solved this in 1965 with compensated summation. Instead of just accumulating a sum, you maintain a second variable tracking what was lost to rounding in the previous step. Each iteration, you add back that compensation before adding the next value, then recalculate what this step lost. The error gets recycled rather than abandoned.

Here’s Clojure maintaining both sum and compensation:

(defn kahan-sum [numbers]
  (loop [nums numbers, sum 0.0, c 0.0]
    (if (empty? nums)
      sum
      (let [y (- (first nums) c)
            t (+ sum y)
            c (- (- t sum) y)]
        (recur (rest nums) t c)))))

(kahan-sum (repeat 1000000 1e-7))  ; Returns 0.1, naive sum drifts

Ada makes the precision contract explicit with typed ranges:

procedure Kahan_Demo is
   type Float_Array is array (Positive range <>) of Float;

   function Kahan_Sum(Numbers : Float_Array) return Float is
      Sum, C, Y, T : Float := 0.0;
   begin
      for N of Numbers loop
         Y := N - C;
         T := Sum + Y;
         C := (T - Sum) - Y;
         Sum := T;
      end loop;
      return Sum;
   end Kahan_Sum;
begin
   null;
end Kahan_Demo;

The algorithm’s beauty is its simplicity—four operations per element, no special hardware required. Numerical analysts in the 1970s discovered dozens of these compensated schemes for different operations. Kahan’s approach became standard in scientific computing precisely because it closes the error loop: what you lose in one step, you recover in the next. The sum converges correctly not because the arithmetic is exact, but because the mistakes are tracked and redistributed, station by station, like a theodolite traverse that knows it must return home.