THE BINARY GCD Stein’s algorithm — greatest common divisor with only shifts and subtraction
Euclid’s GCD leans on the modulo operation, which on old or small hardware is expensive. Stein’s algorithm (1967) replaces it with the cheapest operations a machine has: shifts, subtraction, and parity tests. Both even? Pull out a factor of 2 and remember it. One even? Halve it — 2 cannot be a common factor. Both odd? Subtract the smaller from the larger (the result is even) and continue. No division ever runs, and it reaches the same GCD Euclid would. It is the division-free GCD, ideal for bignums and for hardware.
THE TECHNIQUE even/even ⇒ 2·gcd(a/2,b/2); else halve or subtract — no division
The demo runs Stein’s algorithm on gcd(48,36) using only halving, subtraction, and parity, reaching 12: live demo
HISTORY & CREDIT Stein 1967 · older roots (Knuth)
“GCD needs the remainder.” — Euclid uses mod; Stein uses only shifts and subtraction and lands on the same answer. cited
both even · gcd(a,b) = 2·gcd(a/2, b/2) — factor 2 out and count it. one even · gcd(2a, b) = gcd(a, b) for odd b — halve, 2 is not shared. both odd · gcd(a,b) = gcd(|a−b|, min) — the difference is even. Named for Josef Stein (1967), though Knuth notes a binary halving GCD in antiquity and an independent rediscovery by Silver & Terzian (~1962).
The common divisor found by halving and subtracting — Euclid’s answer without Euclid’s division. resource
RECOMMEND FOR I-13 division-free GCD, on the compiler
On the canonical compiler, Stein’s algorithm returns gcd(48,36) = 12 — using only shifts, subtraction, and parity:
$ i13 run tk_binarygcd.i13 # even/odd cases, shifts + subtract only
RUN OK · 292 step(s) · peak stack 5 · call depth 8
g = 12 -- gcd(48, 36)
same = 1 -- matches Euclid, no modulo used
Recommend as a NULL — resource, and a foil to Euclid. Binary GCD returns the very same value as Euclid’s modulo-based algorithm (i13 prints 12); it merely swaps an expensive primitive (mod) for cheap ones (shift, subtract). That is the resource axis (B40) in its purest “avoid the slow op” form. It sits beside Newton division (416) and Russian-peasant (409) as the batch’s division-free trio. NULL — same GCD, cheaper mechanism.