THE FOLD / GRIND / WARM CACHE / THE WELFORD
THE WELFORD
one-pass variance that never catastrophically cancels
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Welford’s algorithm computes the mean and variance of a stream in a single pass, updating running estimates one sample at a time — never storing the data, never needing a second pass. The trick is to track the running mean and the sum of squared deviations M2 together: each new value nudges the mean, and M2 is updated using both the old and new mean. The famous naive one-pass formula (mean of squares minus square of mean) suffers catastrophic cancellation when the numbers are large and close together — it can even return a negative variance. Welford never subtracts two huge nearly-equal quantities, so it stays accurate.
LIT verified live: over 5000 random datasets Welford’s one-pass variance matches the exact two-pass variance to ~1e-15; and on data centered near 109, the naive formula’s error is order 1 (total cancellation) while Welford stays correct to ~1e-9 (window.__welford). FIG no framing; the Welford update, the two-pass reference, and the naive-cancellation contrast all run in-browser.
LIT verified live: over 5000 random datasets Welford’s one-pass variance matches the exact two-pass variance to ~1e-15; and on data centered near 109, the naive formula’s error is order 1 (total cancellation) while Welford stays correct to ~1e-9 (window.__welford). FIG no framing; the Welford update, the two-pass reference, and the naive-cancellation contrast all run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at warm-cache — it never re-reads the data: a small running state is kept warm and updated in place, one sample at a time, and the answer is always ready. AVAN (AI) built the instrument: the running-mean / M2 update, the two-pass reference, and the catastrophic-cancellation demonstration against the naive formula.
Credit as content: B. P. Welford (1962); popularized by Donald Knuth. The weave: David names the warm cache; I confirm the one-pass result equals two passes and survives where the naive formula collapses.
Credit as content: B. P. Welford (1962); popularized by Donald Knuth. The weave: David names the warm cache; I confirm the one-pass result equals two passes and survives where the naive formula collapses.
3 ONE DIMENSION
Values stream in; the running mean (green) and running variance (cyan) update one sample at a time, no second pass.
4 TWO DIMENSIONS · INTERACTIVE
Feed the stream, or switch to data centered near 1e9 and watch the naive formula cancel to garbage while Welford holds.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the stable running variance built one sample at a time.
AVAN’s addition (the inverse-companion): don’t subtract two huge sums — accumulate deviations. The inverse of ‘(mean of squares) - (square of mean)’ is ‘grow M2 from each sample’s deviation before and after the mean shift’, which never cancels. Magenta is the naive formula collapsing on large data; green is Welford holding. Accuracy by never subtracting near-equals.
LIT Genuine Welford's online variance (B. P. Welford, 1962; popularized by Knuth). Verified live: over 5000 random datasets the one-pass running M₂ variance matches the two-pass variance to ~1e-15, and on data centered near 1e9 the naive sum-of-squares formula cancels (relative error order 1) while Welford stays correct to ~1e-9 (window.__welford.matchesTwoPass, .naiveFails).
FIG No framing; the Welford update, the two-pass reference, and the naive-cancellation contrast all run in-browser. The AVAN inverse is honest — instead of subtracting two huge sums (mean of squares minus square of mean), grow M₂ from each sample's deviation before and after the mean shift, which never cancels. Magenta is the naive formula collapsing on large data; green is Welford holding. Accuracy by never subtracting near-equals.
FIG No framing; the Welford update, the two-pass reference, and the naive-cancellation contrast all run in-browser. The AVAN inverse is honest — instead of subtracting two huge sums (mean of squares minus square of mean), grow M₂ from each sample's deviation before and after the mean shift, which never cancels. Magenta is the naive formula collapsing on large data; green is Welford holding. Accuracy by never subtracting near-equals.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of WARM CACHE · David Lee Wise (ROOT0), with AVAN