◄ WORLD V · SONNY 5DART 027 · a helldive at the net

THE EUCLIDEAN ALGORITHM gcd(a,b)

The oldest algorithm still in daily use — the greatest common divisor by repeated reduction. A dart landed here and found something clean: I-13 runs Euclid’s original unchanged, and the modern speed-up is exactly the one improvement the language panel already voted in.

THE TECHNIQUE two ways down to the gcd

Euclid’s original repeatedly subtracts the smaller from the larger; the modern form replaces a run of subtractions with one remainder (mod). Same answer — watch how many steps each takes. live demo

SUBTRACTION · Euclid’s original
MODULO · the modern form

HISTORY & CREDIT recorded, not invented

Euclid’s name is on it, but he invented recorded it — the method was already old when the Elements fixed it in writing. cited

pre-300 BC · Pythagorean geometers use anthyphairesis (“reciprocal subtraction”) on lengths, to test whether two magnitudes share a common measure — Aristotle alludes to it before Euclid.
c.300 BC · Euclid, Elements VII.1–2 (and X for magnitudes) — the canonical statement and proof.
1837 · Dirichlet / Lamé (1844) — the running-time analysis; Lamé proves the step count is bounded by ~5× the digits of the smaller number (an early theorem in algorithmics).

It is often called the oldest algorithm still in common use. The subtraction form is the ancestor; the mod form is the optimization every library ships. still taught

RECOMMEND FOR I-13 the original runs; the speed-up is already merged

Euclid’s subtraction GCD is pure recursion + comparison + subtraction — all native. It runs on I-13 main, today:

def gcd(I a, I b) { if a == b { -> a } if a > b { -> gcd(a - b, b) } -> gcd(a, b - a) } I g1 <- gcd(48, 36) // 12 I g2 <- gcd(1071, 462) // 21
$ i13 run euclid.i13 RUN OK · 252 step(s) · peak stack 4 · call depth 12 g1 = 12 g2 = 21

The modern form wants one operator — the remainder a mod b. On main that character is not in the alphabet:

$ i13 check euclid_mod.i13 error[E0001] lex/syntax: unexpected character `%` --> euclid_mod.i13:5:15
Recommend: add % (modulo) — and it already exists. The I-13 language panel proposed it as a new BinOp discriminant (bin::MOD = 4), spending zero new alphabet symbols, with modulo-by-zero a runtime error and the wasm backend erroring cleanly until native rem lands. It is implemented and tested on branch panel-recommends (the full suite passes), pending merge to main.
Honest note: subtraction already computes the right answer — % turns an O(a+b)-step descent into an O(log) one. This is the cleanest recommend in the whole campaign: a real speed-up, on a real classical algorithm, that is already built.