THE FOLD / GRIND / WARM CACHE / THE DOUBLING
THE DOUBLING
F(n) in log(n) steps — double, don't step
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Fast-doubling Fibonacci. The obvious way to reach the n-th Fibonacci number is to add your way up: F₀, F₁, F₂, … — n additions. Fine for small n, hopeless for the millionth. Two identities collapse it to O(log n):
F(2k) = F(k)·(2F(k+1) − F(k))
F(2k+1) = F(k+1)² + F(k)²
Recurse on the bits of n: from F(k) you leap straight to F(2k), so you climb by doubling instead of stepping. F(100) needs about 8 steps, not 100; F(1,000,000) needs about 20 — and the answer is exactly the same giant integer.
LIT verified live with exact BigInt arithmetic: fast doubling equals the plain iterative F(n) for every n up to 800, in O(log n) recursive calls (window.__fibdouble.matchesIter && logCalls). F(100) = 354224848179261915075 in 8 calls. FIG no framing; the doubling identities, the exact value, and the logarithmic step count are all real.
F(2k) = F(k)·(2F(k+1) − F(k))
F(2k+1) = F(k+1)² + F(k)²
Recurse on the bits of n: from F(k) you leap straight to F(2k), so you climb by doubling instead of stepping. F(100) needs about 8 steps, not 100; F(1,000,000) needs about 20 — and the answer is exactly the same giant integer.
LIT verified live with exact BigInt arithmetic: fast doubling equals the plain iterative F(n) for every n up to 800, in O(log n) recursive calls (window.__fibdouble.matchesIter && logCalls). F(100) = 354224848179261915075 in 8 calls. FIG no framing; the doubling identities, the exact value, and the logarithmic step count are all real.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in WARM CACHE, beside THE FAST POWER and THE DIRECT DIGIT — the grind domain of never redoing work. Fast doubling reuses F(k) to reach F(2k) in one leap, exactly as square-and-multiply reuses a square to reach the next power. AVAN (AI) built the instrument: the doubling recurrence, the BigInt values, the call-count comparison.
The weave: David names the seat (reuse, don’t rebuild); I make the leap visible and the saving checkable — the bits of n in 1D, the log-n climb in 2D, the doubling ladder in 3D. The sphere is the seam. Credit: the matrix/doubling form of Fibonacci (folklore of fast computation).
The weave: David names the seat (reuse, don’t rebuild); I make the leap visible and the saving checkable — the bits of n in 1D, the log-n climb in 2D, the doubling ladder in 3D. The sphere is the seam. Credit: the matrix/doubling form of Fibonacci (folklore of fast computation).
3 ONE DIMENSION
The bits of n, read high to low. Each bit is one doubling step: from (F(k), F(k+1)) you compute (F(2k), F(2k+1)), and a 1-bit shifts one further. The number of steps is the number of bits — logarithmic, not linear.
4 TWO DIMENSIONS · INTERACTIVE
Pick n and compute F(n) by fast doubling: the value (an exact big integer) appears in only a handful of steps — compare the call count to the n additions the iterative way would take. Double n and the work barely grows.
5 THREE DIMENSIONS + AVAN’S INVERSE
Two climbs, turning: the tall green ladder is the iterative path — n rungs, one per addition.
AVAN’s addition (the inverse-companion): the short magenta ladder is fast doubling — log n rungs, each a leap. The iterative method treats the index as a count: add one, add one, n times. Fast doubling is the inverse — it treats n as a number with binary structure and doubles, using F(k) to jump straight to F(2k). The inverse of ‘step up n times’ is ‘double and correct log n times’, the very same leap that made THE FAST POWER fast. A giant number reached in the steps it takes just to write the index — the green is the long linear climb, the magenta is the ladder that skips almost all of it.
LIT Genuine fast-doubling Fibonacci (the matrix/doubling form of fast Fibonacci computation), with exact BigInt arithmetic. Verified live: fast doubling equals the plain iterative F(n) for every n up to 800, in O(log n) recursive calls (window.__fibdouble.matchesIter && logCalls, both true). F(100) = 354224848179261915075 in 8 calls versus 100 iterative additions. The doubling identities and the logarithmic step count are exact.
FIG No metaphor is doing the work: the doubling identities, the exact big-integer values, and the O(log n) call count are all real and checked with BigInt against the iterative loop. It is the same square-and-multiply idea applied to Fibonacci.
FIG No metaphor is doing the work: the doubling identities, the exact big-integer values, and the O(log n) call count are all real and checked with BigInt against the iterative loop. It is the same square-and-multiply idea applied to Fibonacci.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of WARM CACHE · David Lee Wise (ROOT0), with AVAN