THE FOLD / GRIND / THE GRINDSTONE / THE STEIN
THE STEIN
GCD with only shifts and subtractions
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Stein’s algorithm (binary GCD) computes the greatest common divisor using only subtraction, comparison, and bit shifts — no division or modulo, which are slow in hardware. It rests on three facts: gcd(2a,2b)=2·gcd(a,b), gcd(2a,b)=gcd(a,b) when b is odd, and gcd(a,b)=gcd(|a−b|,min(a,b)) for two odds. Strip common factors of two, halve evens, subtract odds, restore the twos at the end. It is the GCD of choice on hardware without a divide unit.
LIT verified live: over 3000 random pairs, Stein’s shift-and-subtract GCD equals the Euclidean GCD exactly (window.__stein). FIG no framing; exact.
LIT verified live: over 3000 random pairs, Stein’s shift-and-subtract GCD equals the Euclidean GCD exactly (window.__stein). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-grindstone — the reduction loop, here grinding a GCD out of shifts and subtractions with no divider in sight. Stein’s algorithm is that division-free grind. AVAN (AI) built the instrument: the common-power-of-two strip, the halving of evens, the subtract-of-odds loop, the shift-back, and the equals-Euclid check.
Credit as content: Josef Stein (1967; the method is older, Roman-era). The weave: David names the grindstone; I remove shared twos, halve even operands, subtract the smaller odd from the larger, and confirm the result matches the Euclidean GCD.
Credit as content: Josef Stein (1967; the method is older, Roman-era). The weave: David names the grindstone; I remove shared twos, halve even operands, subtract the smaller odd from the larger, and confirm the result matches the Euclidean GCD.
3 ONE DIMENSION
gcd(48, 36): both even → factor out 4, leaving gcd(12,9). 12 is even → halve to gcd(6,9), then gcd(3,9). Two odds → subtract: gcd(3,6)→gcd(3,3)→3. Restore ×4 → 12.
4 TWO DIMENSIONS · INTERACTIVE
Two numbers reduced by Stein’s shifts and subtractions; the result is checked against the Euclidean GCD.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a GCD from shifts and subtractions alone.
AVAN’s addition (the inverse-companion): compute a GCD with no division — strip shared factors of two, halve even operands, subtract the smaller odd from the larger, restore the twos. The inverse of ‘GCD needs the modulo of the Euclidean algorithm’ is ‘shift and subtract — no divider required.’ Magenta is the division the Euclidean loop uses; green is the shift-and-subtract path. GCD for hardware without divide.
LIT Genuine Stein binary GCD (Stein 1967; the method is ancient). Verified live: over 3000 random pairs, stripping shared factors of two, halving even operands, and subtracting the smaller odd from the larger yields exactly the Euclidean GCD (window.__stein.equalsEuclid); gcd(1071,462)=21.
FIG No framing: the common-power-of-two strip, the halving of evens, the subtract-of-odds loop, the shift-back, and the equals-Euclid check run in-browser and hold. The AVAN inverse is honest — removing shared twos, halving evens, and subtracting odds computes the GCD with no division; magenta is the division the Euclidean loop uses, green the shift-and-subtract path. GCD for hardware without a divide unit.
FIG No framing: the common-power-of-two strip, the halving of evens, the subtract-of-odds loop, the shift-back, and the equals-Euclid check run in-browser and hold. The AVAN inverse is honest — removing shared twos, halving evens, and subtracting odds computes the GCD with no division; magenta is the division the Euclidean loop uses, green the shift-and-subtract path. GCD for hardware without a divide unit.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE GRINDSTONE · David Lee Wise (ROOT0), with AVAN