Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Cancellation — the series

3 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹xrelative error of the computed value(1 − cos x)/x², as written2 sin²(x/2)/x²no digits left at allbinary64 throughoutone function, two spellings · zero below 1.5·10⁻⁸

    Cancellation takes the answer, not a digit

    Subtracting two nearly equal numbers is exact. That is what makes it dangerous — the subtraction introduces no error at all, it exposes error the operands were already carrying, and the exposure can consume every significant figure at once.

    part 1 · arithmetic
  2. 24 bits, κ² 10⁶one-pass ÷ κ²u7.7compensated ÷ κ²u0.92Welford ÷ κu0.067two-pass, in u6.5110²10⁴10⁶10⁸10¹⁰10¹²10¹⁴110²10⁴10⁶10⁸10¹⁰10¹²10¹⁴10¹⁶κ² = 1 + mean² ÷ variancerelative error ÷ uevery digit goneκ²uone-passcompensated or pairwiseWelfordshifted by x₁two-passdashed purple: κ²u, the digits-lost rulethe formula sets the power of κ

    The formula sets the power, the sum sets the constant

    The one-pass variance was found losing three to sixty-nine times more than the digits-lost rule allows, and the explanation offered — operands built from a thousand roundings — was never priced. Measured against the exact variance of the stored data, the rule's ratio is the variance's own condition number squared, and the formula decides what power of it the error grows with: two for every one-pass variant, one for Welford's update, none for two passes or a shift. The summation decides only the constant in front — about 0.4√n for running sums, one for pairwise or compensated ones — and the sixty-nine was neither: it belonged to the random numbers.

    part 2 · arithmetic
  3. 0.010.1110100the earlier recipe, product rounded41 of 41 over · median 62.0the same recurrence, exact24 of 41 over · median 6.3a well-mixed generator21 of 41 over · median 8.0one-pass error ÷ κ²u, one dot a seed; bar: medianfilled: the variance over-estimated; open: underthe line at one is the digits-lost rulethe exact recurrence does not lean

    The generator that rounded its own product

    A one-pass variance leaned the same way on forty-one seeds, and the low bits of a congruential generator were the suspect. Replacing the lowest five bits made the lean larger, not smaller. The generator was not congruential at all: written in double precision, its product of two 31-bit numbers was rounded before the modulus, its states collapsed onto a handful of low bytes, and those are the bits a running sum near a billion throws away. The exact recurrence does not lean, and random bits are not neutral either: fewer of them than the sum discards all round one way.

    part 3 · arithmetic

All series