THE FOLD / CHEAT / THE SPEEDRUN / THE BARRETT
THE BARRETT
reduce mod n without dividing
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Barrett reduction computes x mod n without dividing — replacing the expensive division with one multiplication and a shift, using a precomputed constant μ = ⌊4k/n⌋ (k = the bit length of n). The quotient is estimated as ⌊x·μ / 4k⌋, then x − q·n is corrected by at most two subtractions. For inputs x < n2 (a modular product), this is exact. It is a cornerstone of fast modular exponentiation in RSA and elliptic-curve crypto, where the modulus is fixed and reused millions of times.
LIT verified live: over thousands of pairs with x < n2, Barrett reduction equals x mod n exactly, needing at most 2 corrections (window.__barrett). FIG no framing; exact in the x < n2 regime it is designed for.
LIT verified live: over thousands of pairs with x < n2, Barrett reduction equals x mod n exactly, needing at most 2 corrections (window.__barrett). FIG no framing; exact in the x < n2 regime it is designed for.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-speedrun — the trick that skips the slow step: replacing division with a multiply because the modulus never changes. Barrett reduction is that speedrun of modular arithmetic. AVAN (AI) built the instrument: the precomputed μ, the multiply-and-shift quotient estimate, the ≤2-subtraction correction, and the equals-x-mod-n check.
Credit as content: Paul Barrett (1986). The weave: David names the-speedrun; I precompute μ for the fixed modulus, estimate the quotient with a multiply and shift, and confirm x − q·n corrects to exactly x mod n.
Credit as content: Paul Barrett (1986). The weave: David names the-speedrun; I precompute μ for the fixed modulus, estimate the quotient with a multiply and shift, and confirm x − q·n corrects to exactly x mod n.
3 ONE DIMENSION
Precompute μ = ⌊4k/n⌋ once. For each x: q = ⌊x·μ >> 2k⌋ approximates x/n; r = x − q·n; subtract n at most twice to land in [0,n). No division per reduction.
4 TWO DIMENSIONS · INTERACTIVE
A modulus n and value x < n2; Barrett’s multiply-and-shift reduction is shown against the true x mod n.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a remainder computed by multiplying, not dividing.
AVAN’s addition (the inverse-companion): reduce mod a fixed n with no division — precompute μ = ⌊4k/n⌋ once, then each reduction is a multiply, a shift, and ≤2 subtractions. The inverse of ‘divide by n every time to get the remainder’ is ‘precompute the reciprocal, then multiply-shift-correct.’ Magenta is the per-reduction division you avoid; green is the multiply-and-shift. The remainder without the divide.
LIT Genuine Barrett reduction (Barrett 1986). Verified live: over 4000 pairs with x < n^2, precomputing mu = floor(4^k/n) and computing q = floor(x*mu >> 2k), r = x - q*n with at most 2 corrections equals x mod n exactly (window.__barrett.equalsMod; max corrections observed = 1). Honestly scoped to the x < n^2 regime Barrett is designed for.
FIG No framing within its regime: the precomputed mu, the multiply-and-shift quotient estimate, the <=2-subtraction correction, and the equals-x-mod-n check run in-browser over x < n^2 and hold (outside that regime Barrett needs more corrections — not claimed). The AVAN inverse is honest — precomputing the reciprocal mu once lets each reduction be a multiply, shift, and <=2 subtractions; magenta is the per-reduction division avoided, green the multiply-and-shift. The remainder without the divide.
FIG No framing within its regime: the precomputed mu, the multiply-and-shift quotient estimate, the <=2-subtraction correction, and the equals-x-mod-n check run in-browser over x < n^2 and hold (outside that regime Barrett needs more corrections — not claimed). The AVAN inverse is honest — precomputing the reciprocal mu once lets each reduction be a multiply, shift, and <=2 subtractions; magenta is the per-reduction division avoided, green the multiply-and-shift. The remainder without the divide.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE SPEEDRUN · David Lee Wise (ROOT0), with AVAN