THE FOLD / RESPAWN / ROLLBACK / THE BRENT CYCLE
THE BRENT CYCLE
cycle detection in O(1) memory, fewer evals than Floyd
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Brent’s cycle detection finds the loop in a sequence x, f(x), f(f(x)), … using constant memory. It keeps ONE saved value and compares the moving value to it at exponentially spaced checkpoints (powers of two); when the value repeats, the gap reveals the cycle length λ, and a second short scan finds where the cycle starts (μ). It uses fewer function evaluations than the tortoise-and-hare.
It is the cycle-finder inside Pollard’s rho factorisation.
LIT verified live: over 300 random functional graphs Brent’s (cycle length λ, start μ) equals a brute record-every-value computation (window.__brentcycle). FIG no framing; exact — with O(1) memory.
It is the cycle-finder inside Pollard’s rho factorisation.
LIT verified live: over 300 random functional graphs Brent’s (cycle length λ, start μ) equals a brute record-every-value computation (window.__brentcycle). FIG no framing; exact — with O(1) memory.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at rollback — the sequence eventually rolls back to a value it has seen before, and Brent’s method finds that return without storing the history. AVAN (AI) built the instrument: the doubling-checkpoint search for λ, the offset scan for μ, the brute cross-check.
Credit as content: Richard Brent (1980). The weave: David names the rollback; I keep one teleporting checkpoint at doubling distances and read off the cycle from the first repeat, confirmed against an exhaustive record.
Credit as content: Richard Brent (1980). The weave: David names the rollback; I keep one teleporting checkpoint at doubling distances and read off the cycle from the first repeat, confirmed against an exhaustive record.
3 ONE DIMENSION
The saved checkpoint jumps to the current value at distances 1, 2, 4, 8, … The moving value runs ahead; when it meets the saved one, the distance travelled since the last jump is the cycle length λ.
4 TWO DIMENSIONS · INTERACTIVE
A functional graph (each node points to f(node)); the rho-shaped tail and cycle are shown, with Brent’s λ, μ checked against brute.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the single teleporting checkpoint catching the cycle.
AVAN’s addition (the inverse-companion): find the cycle with O(1) memory by comparing the current value to a saved one at exponentially-spaced checkpoints (powers of two) — when the value repeats, the gap reveals the cycle length, with fewer function evaluations than the tortoise-and-hare. The inverse of ‘store all seen values’ is ‘keep one saved value at doubling distances and watch for a repeat.’ Magenta is the full history you don’t store; green is the single teleporting checkpoint. Constant memory, fewer steps than Floyd. (Kin to the-tortoise.)
LIT Genuine Brent's cycle detection (Brent 1980). Verified live: the doubling-checkpoint search for the cycle length and the offset scan for the cycle start return the same (lambda, mu) as a brute record-every-value computation for 300 random functional graphs (window.__brentcycle.matchesBrute).
FIG No framing: the doubling-checkpoint search for lambda, the offset scan for mu, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — comparing to one saved value at exponentially-spaced checkpoints finds the cycle in O(1) memory with fewer function evaluations than tortoise-and-hare; magenta is the unstored history, green the single teleporting checkpoint. Kin to the-tortoise.
FIG No framing: the doubling-checkpoint search for lambda, the offset scan for mu, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — comparing to one saved value at exponentially-spaced checkpoints finds the cycle in O(1) memory with fewer function evaluations than tortoise-and-hare; magenta is the unstored history, green the single teleporting checkpoint. Kin to the-tortoise.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of ROLLBACK · David Lee Wise (ROOT0), with AVAN