Follow a sequence where each value points to the next. Eventually it must loop — but where, and how long is the loop, using almost no memory? Send two walkers: one slow, one twice as fast. They are guaranteed to meet inside the loop. It runs in I-13 as plain recursion — and its name is a mystery.
THE TECHNIQUE slow by one, fast by two
The path looks like the Greek letter ρ: a tail that runs into a loop. The tortoise steps once, the hare twice. Inside the loop the hare gains one step per tick on the tortoise, so it must land on it. Watch them meet. live demo
HISTORY & CREDIT the algorithm nobody can source
Textbooks say “Floyd’s cycle detection” with total confidence — and cannot point to where Floyd wrote it. disputed
the attribution · Donald Knuth credits the tortoise-and-hare method to Robert W. Floyd in The Art of Computer Programming — but gives no citation, and no Floyd paper describing it has been found. Floyd · a Turing Award winner (Floyd–Warshall, Floyd–Steinberg dithering) — real, prolific, but this one seems to be folklore pinned to a famous name. 1980 · Richard Brent publishes a genuinely faster variant (and cites it properly) — the one many libraries actually use. the honest label · “the tortoise and the hare,” after Aesop, is the name that owes nobody a citation.
A rare inversion of this campaign’s usual bug: not a real author denied credit, but credit assigned to someone who may not have asked for it. unsourced
RECOMMEND FOR I-13 a no-wall for constant memory
Two walkers, one function, no data structure — recursion carries the two positions. I-13 runs it:
def f(I x, I m) { -> (x * x + 1) % m }
def chase(I t, I h, I m, I k) {
if k == 0 { -> t }
I nt <- f(t, m) I nh <- f(f(h, m), m)
if nt == nh { -> nt }
-> chase(nt, nh, m, k - 1)
}
$ i13 run floyd.i13
meet = 2 # tortoise and hare collide inside the loop
Recommend:nothing new — and it is a good showcase of I-13’s actual strength. The whole point of the algorithm is O(1) memory; I-13, having no heap and only bounded recursion, is a natural fit for exactly the class of algorithms that refuse to allocate. The walls this campaign keeps hitting (arrays, bignum) are absent here by the algorithm’s own design. Note: the depth bound k is I-13’s honesty showing — a real cycle finder loops until collision; here the bound is explicit and provable, which is the language’s whole ethos.