THE FOLD / GRIND / THE GRINDSTONE / THE BINARY GCD
THE BINARY GCD
Stein's algorithm — gcd with no division
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Stein’s binary GCD. Euclid finds the greatest common divisor by repeated division — but division is the slowest thing a processor does. In 1967 Josef Stein found a way to get the same answer using only the operations hardware loves: subtraction, comparison, and bit-shifts (halving). No division, no modulo, ever.
The rules are all about the factor 2. If both numbers are even, pull out a shared 2 and remember it. If just one is even, halve it — 2 can’t be in the gcd on that side. Once both are odd, subtract the smaller from the larger (the difference is even) and repeat. At the end, shift back in the shared 2s you set aside.
LIT verified live: over 50,000 random pairs Stein’s binary GCD gives exactly the same result as Euclid’s algorithm, using no division at all (window.__stein.matchesEuclid). gcd(1071, 462) = 21. FIG no framing; the shift-and-subtract reduction and its agreement with Euclid are exact.
The rules are all about the factor 2. If both numbers are even, pull out a shared 2 and remember it. If just one is even, halve it — 2 can’t be in the gcd on that side. Once both are odd, subtract the smaller from the larger (the difference is even) and repeat. At the end, shift back in the shared 2s you set aside.
LIT verified live: over 50,000 random pairs Stein’s binary GCD gives exactly the same result as Euclid’s algorithm, using no division at all (window.__stein.matchesEuclid). gcd(1071, 462) = 21. FIG no framing; the shift-and-subtract reduction and its agreement with Euclid are exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE GRINDSTONE, right beside THE EUCLID — the grind domain of grinding two numbers down to their common measure. Stein’s is Euclid reborn for silicon: the same descent, done in binary. AVAN (AI) built the instrument: the halvings, the subtractions, the shared-power-of-2 bookkeeping.
The weave: David names the seat (the common measure), placed next to its ancestor; I make the binary dance visible and its agreement with Euclid checkable — the bits in 1D, the step-by-step reduction in 2D, the shrinking bit-columns in 3D. The sphere is the seam. Credit: Josef Stein (1967); the binary analogue of Euclid.
The weave: David names the seat (the common measure), placed next to its ancestor; I make the binary dance visible and its agreement with Euclid checkable — the bits in 1D, the step-by-step reduction in 2D, the shrinking bit-columns in 3D. The sphere is the seam. Credit: Josef Stein (1967); the binary analogue of Euclid.
3 ONE DIMENSION
The two numbers in binary. A trailing zero means ‘even’ — shift it away. Shared trailing zeros are a shared power of 2, set aside for the end. Everything is done by looking at the low bit and shifting: no division in sight.
4 TWO DIMENSIONS · INTERACTIVE
Step through the reduction: halve an even number, or subtract the smaller odd from the larger. Watch the pair grind down to the gcd — and confirm it matches Euclid’s answer, reached without a single division.
5 THREE DIMENSIONS + AVAN’S INVERSE
The two numbers as turning bit-columns, shrinking step by step — green, the bits that remain.
AVAN’s addition (the inverse-companion): the magenta bits are the ones being shifted out — the powers of 2 removed, the shared factor set aside. Euclid reduces by division; Stein reaches the identical gcd by refusing to divide and using only shifts and subtractions. It is an inverse route to the same summit: where Euclid asks ‘what is the remainder?’, Stein asks only ‘is the low bit zero?’ — a question a machine answers for free. Two algorithms, one truth, opposite tools. The green is the common measure emerging; the magenta is every factor of 2 pulled out along the way and restored at the end.
LIT Genuine Stein binary GCD (Josef Stein, 1967). Verified live: over 50,000 random pairs it gives exactly Euclid's gcd using no division at all (window.__stein.matchesEuclid === true). gcd(1071,462) = 21. The rules (extract shared powers of 2, halve evens, subtract odds) are exact and reach the same value as division-based Euclid — the binary analogue seated beside THE EUCLID.
FIG No metaphor is doing the work: the shift-and-subtract reduction and its exact agreement with Euclid are checked over 50,000 pairs. It's the same gcd by hardware-friendly operations, not an approximation.
FIG No metaphor is doing the work: the shift-and-subtract reduction and its exact agreement with Euclid are checked over 50,000 pairs. It's the same gcd by hardware-friendly operations, not an approximation.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE GRINDSTONE · David Lee Wise (ROOT0), with AVAN