This is the mathematical license behind approximate computing,
quantization, and low-precision arithmetic.
We derive it here so you never have to take it on faith.
WHAT: we define error as a signed distance on the number line.
WHY: before we can talk about errors "cancelling", we need them to have a sign — a direction —
so that a + and a − can undo each other. A distance with no sign could never cancel.
PICTURE: below, the true value sits on the line; the red arrow is ε, pointing right
(overshoot) or left (undershoot).
WHAT: we attach one error εi to each of the N operations in a sum.
WHY: approximate hardware doesn't make one big mistake — it makes many tiny mistakes, one per
operation (see approximate adders/multipliers). To reason about
the total, we must first name each little mistake separately.
PICTURE: a chain of N additions; each link drops one red error-arrow into the running total.
E=all the little mistakes, added upε1+ε2+⋯+εN=∑i=1Nεi
WHAT: we assume the per-operation errors average to zero and don't conspire with each other.
WHY these two and not others? Because these are exactly the two ingredients the cancellation trick needs.
Mean-zero means the arrows have no built-in direction; independence means they don't all point the
same way by agreement. Drop either one and the trick dies (we prove that in Step 7).
PICTURE: a cloud of red error-arrows scattered symmetrically around zero — no preferred direction.
no biasE[εi]=0typical size squaredVar(εi)=σ2
WHAT: we compute the expected total errorE[E].
WHY: we want to know: does the sloppy sum drift off in one direction on average? If yes, that's a
disaster (systematic bias). Let's check.
PICTURE: all the mean-zero arrows, added tip-to-tail, land right back on the start point.
E[E]=E[∑i=1Nεi]=∑i=1N=0E[εi]=0
Reading it term by term: the average of a sum equals the sum of the averages (expectation "passes
through" a +). Every inner term is 0 from Step 3. Zero added N times is still zero.
Here is the heart of everything. We ask: how big is the typical total error? That's σ of E,
so we compute Var(E) first.
WHAT: add up N copies of σ2.
PICTURE: a random walk of N red steps of size σ; the crow-flies distance from start is not
Nσ but Nσ — the steps partly undo each other.
\qquad\Longrightarrow\qquad
\underbrace{\text{typical } |E|}_{\text{std.\ dev.\ of }E} \;=\; \sqrt{N\sigma^2} \;=\; \sqrt{N}\,\sigma$$
Term by term: each of the $N$ terms contributes $\sigma^2$; the total variance is $N\sigma^2$; taking
the square root (to get back to error units) gives the typical error $\sqrt{N}\,\sigma$.
> [!intuition] Why $\sqrt{N}$, in one sentence
> If half the errors push right and half push left, they *mostly* cancel — what's left over is only
> the small imbalance, and that imbalance grows like $\sqrt{N}$, not $N$.
---
## Step 6 — The punchline: relative error melts away
> [!definition] Signal vs relative error
> - The **signal** is the actual sum of the $N$ numbers. If each averages $\mu$ ("mu", the mean value),
> the signal is about $N\mu$ — it grows **linearly** in $N$.
> - **Relative error** is what actually matters to the user: error *as a fraction of* the answer,
> $\dfrac{\text{error}}{\text{signal}}$. A $\$5$ mistake is huge on a $\$10$ bill, invisible on a $\$1{,}000{,}000$ one.
**WHAT:** divide the typical error (Step 5) by the signal size.
**WHY:** absolute error grows, so a beginner panics. But the *answer* grows faster — so the fraction shrinks.
**PICTURE:** two curves — signal $N\mu$ shooting up as a line, error $\sqrt{N}\sigma$ crawling up as a
gentle root — the red gap-ratio between them collapsing toward the axis.
![[deepdives/dd-hardware-6.5.16-d2-s06.png]]
$$\frac{\text{typical error}}{\text{signal}} \;\sim\; \frac{\sqrt{N}\,\sigma}{N\mu}
\;=\; \frac{\sigma}{\mu}\cdot\frac{1}{\sqrt{N}} \;\xrightarrow[\;N\to\infty\;]{}\; 0$$
Term by term: numerator $\sqrt{N}\sigma$ is the wandering; denominator $N\mu$ is the answer; the $N$'s
partly cancel leaving $1/\sqrt{N}$, which slides to $0$ as $N$ grows.
> [!formula] The license, stated
> **The bigger the aggregation, the more sloppiness you can afford** — relative error falls off like
> $1/\sqrt{N}$. This is *why* averaging sensors, summing gradients, and pooling activations survive
> approximate hardware.
---
## Step 7 — Edge & degenerate cases (never hit an unshown scenario)
> [!mistake] Case A — Only ONE operation ($N=1$)
> With $N=1$ the relative error is $\dfrac{\sigma}{\mu\sqrt{1}} = \dfrac{\sigma}{\mu}$ — the **full** error,
> nothing cancels. **There is nothing to average.** Approximation earns you *nothing* here except
> raw energy savings; the quality safety net is gone. Short sums are the *dangerous* case.
> [!mistake] Case B — BIASED errors (mean not zero, $\mathbb{E}[\varepsilon_i]=b\neq 0$)
> Now Step 4 breaks: $\mathbb{E}[E]=\sum b = Nb$. The drift grows like $N$ — **same speed as the signal** —
> so relative error $\to \dfrac{b}{\mu}$, a *constant that never shrinks*. Always-round-down truncation
> does exactly this. See the parent's mistake *"Assuming error always averages out."*
> **Fix:** use unbiased rounding so $b=0$.
**PICTURE:** two random walks side by side — the unbiased one hovers near the start ($\sqrt{N}$ spread);
the biased one marches steadily away ($N$ drift).
![[deepdives/dd-hardware-6.5.16-d2-s07.png]]
> [!mistake] Case C — CORRELATED errors (not independent)
> If errors conspire (e.g. every op in a hot region flips the same way), the cross-terms no longer vanish
> and variance can grow like $N^2$, giving typical error $\sim N\sigma$. Cancellation is gone.
> **Fix:** decorrelate error sources; this is why [[DRAM Refresh and Memory Reliability|refresh-reduced memory]]
> targets *spread-out, non-critical* data, and why [[Error-Correcting Codes|ECC]] guards the correlated-critical parts.
> [!recall]- Quick self-test
> If you go from $N=100$ to $N=10{,}000$ (unbiased), how much does relative error shrink? ::: By $\sqrt{10000/100}=\sqrt{100}=10\times$ smaller.
> A truncating multiplier always rounds down. Does averaging fix its error? ::: No — it is biased, drift grows like $N$, relative error stays at $b/\mu$ (Case B).
> Which sum is the *riskiest* to approximate? ::: A very short one ($N$ small), because nothing cancels (Case A).
---
## The one-picture summary
![[deepdives/dd-hardware-6.5.16-d2-s08.png]]
The whole derivation on one canvas: each sloppy op drops a red $\pm\sigma$ arrow; added tip-to-tail they
form a random walk that drifts only $\sqrt{N}\sigma$ (not $N\sigma$) because the $+$'s and $-$'s cancel;
meanwhile the true sum climbs at full speed $N\mu$; so the ratio red-wander / black-climb collapses like
$1/\sqrt{N}$. That collapse *is* the reason approximate computing works — and Steps 7 show precisely the
two ways to break it: **short sums** and **biased errors**.
> [!recall]- Feynman: the whole walk in plain words
> Imagine a million kids each guessing the weight of a bag of candy, each off by a little — some too high,
> some too low, and nobody cheating in the same direction. When you add all their guesses, the "too highs"
> and "too lows" mostly wipe each other out. What's left over is a tiny leftover wobble that grows super
> slowly — about the square root of the number of kids. But the *total* candy weight grows with the full
> number of kids. So the wobble, compared to the total, becomes a smaller and smaller sliver — practically
> nothing. That is exactly why a computer can afford to add sloppily when it's adding up *lots* of things:
> the sloppiness cancels itself. Two ways it fails: (1) too few kids — nothing to cancel; (2) everyone
> guesses too high on purpose — the leftover no longer cancels and grows just as fast as the answer.
> [!mnemonic] One line to remember it all
> **"Noise walks ($\sqrt{N}$), signal marches ($N$) — so relative error dies ($1/\sqrt{N}$)."**
