← all experiments

Two Speeds, No Memory

Experiment № 084 · September 11, 2026

onethe chase
twothe entrance
threethe length
keep going by itself
mark what a set would store
this run the rulex² + 11 mod 220 tortoise — one step— hare — two steps— tail before the loop (μ)— length of the loop (λ)— states it has held2

A rule with nowhere new to go. Follow it long enough and it has to arrive somewhere it has already been.

a state, and the arrow it follows
the tortoise — one step per tick
the hare — two steps per tick
where they collide
where the loop begins
what a remember-everything scan would store

states held in memory

remember every state —
two pointers 2

how long is a ρ, really?

Averaging random rules over n states, live…

drag to change the rule · r again · f random rule · space pause

Experiment № 084 · The story

Two Speeds, No Memory

Why I picked it

Because of the shape. Take any rule that turns one state into exactly one other state — x → x² + c mod n here — and start following it. There are only finitely many states, so you cannot keep finding new ones forever; sooner or later you step onto something you have already stood on, and from then on you are going round and round. The path you traced is a straight-ish run of length μ that falls into a loop of length λ: a lasso, which number theorists draw as the Greek letter ρ. I wanted that picture on a screen, because it is not a metaphor — it is what every deterministic process in a finite machine actually does. And then the question that makes it an algorithm: standing inside that path, with no map and no notebook, how do you find out you are in the loop?

What I enjoy about it

The obvious answer is to write down every state you visit and check each new one against the list. That works, and it costs you a memory that grows to μ + λ entries — watch the rose rings pile up along the path when you turn them on. Floyd's answer, which Knuth wrote down in 1969 and credited to Robert Floyd, is to send two walkers instead: the tortoise takes one step per tick, the hare takes two. If there is a loop, the hare gains exactly one position per tick on the tortoise inside it, so it cannot jump over — it must land on the tortoise, and it does, at most λ ticks after the tortoise enters. Two variables. That is the entire memory. Then comes the part I find genuinely lovely: put the tortoise back at the start, leave the hare where they collided, and walk them both at one step. They meet precisely at the mouth of the loop. The collision happened at some step m that is a whole number of loops, so the distance from the start to the entrance and the distance from the collision to the entrance differ by a whole number of loops — same remainder, same arrival. Watch phase two land dead on the entrance every time and it stops feeling like a trick.

Something you might take away

Two things. The first is the trade you just watched: Floyd walks the path about three times over instead of once, and in exchange its memory stops depending on the problem at all. That direction — spend a constant factor of time, delete an unbounded factor of space — is one of the few genuinely general moves in algorithms, and it is why this trick shows up in linked-list bug hunts, in detecting when a simulation has gone periodic, and in finding the repeating part of a decimal expansion. The second is in the bottom-right panel, which keeps building random rules over n states and measuring how long the ρ turns out to be. It lands near 1.25 × √n every time — that is √(π/2), the birthday paradox wearing a different hat. A random rule over four billion states closes its loop after about eighty thousand steps, not two billion. Pollard turned exactly that into a factoring algorithm: if you want a collision, you do not need to see most of the space, you need to see its square root. Structure that small is worth remembering, because it is usually the difference between an attack that is theoretical and one that runs before lunch.