Fibonacci and the Rolling-Array Space Reduction

What This Concept Is

Space reduction follows value lifetimes: discard a state only after its last future reader. For F(i)=F(i-1)+F(i-2), two consecutive values suffice to compute the next one. For a two-sequence recurrence, keep the previous row and current row; a one-row version additionally preserves the overwritten diagonal.

This changes storage, not the recurrence. It must preserve the layer of every read. It can also remove information needed for reconstruction, so distinguish value-only space from full output space.

Why It Matters Here

An array can appear correct on most inputs while reading a newly overwritten cell instead of the previous layer. Loop direction is therefore part of a proof. And "constant space" in a unit-cost model can hide integers whose representation grows with the input: counting algorithms cannot ignore answer bit length.

Concrete Examples

Exact Fibonacci. This loop handles n=0 and uses simultaneous assignment:

def fib(n):
    if n < 0:
        raise ValueError("negative index")
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Before iteration i, (a,b)=(F(i),F(i+1)). Reading both old values preserves the invariant. Sequential a=b; b=a+b would use the new a and fail. The algorithm performs O(n) additions and stores O(1) integer objects. Exact F(n) has Θ(n) bits. Under linear-time integer addition the loop uses O(n²) bit work and O(n) live numeric bits; the full table stores Θ(n²) bits. The decimal output itself grows with n. A billion iterations is not made practical merely by keeping two variables. Fast doubling is an optional separate algorithm; fixed-precision evaluation of Binet's formula is not an exact replacement.

Edit distance. While updating cell (i,j) in one row, old row[j] is the previous-row value, new row[j-1] is the current-row value, and a saved scalar holds old (i-1,j-1). Save old row[j] before overwriting it. This can compute the value in linear row storage; it does not return an alignment for free. Hirschberg-style divide-and-conquer reconstruction requires a separate derivation.

Knapsack. Positive item weight w gives source index c-w<c. Descending capacity ensures that source still belongs to the previous-item layer for 0/1 use. Ascending capacity intentionally exposes this item's current layer for unbounded use. Both may be correct for different contracts.

Common Confusion / Misconceptions

Rolling arrays do not eliminate output storage or arbitrary-precision costs. LIS tails use a dominance argument, not merely a recent-row lifetime argument. Keeping fewer slots is unsafe if future transitions can still read evicted values. A cache eviction policy that recomputes states may increase time dramatically.

How To Use It

Annotate each read as previous/current layer, mark the last reader of each cell, then choose update order. Verify the full-table and compressed values on exhaustive small inputs. If reconstruction is required, account for all retained choices, or state that the compressed variant is value-only. Use the same arithmetic and output contract in performance comparisons.

Check Yourself

Why are two Python integers not a constant number of bits? Which value gets lost in one-row edit distance? Why does changing loop direction change knapsack semantics?

Mini Drill or Application

Trace the Fibonacci pair for n=0..4, then intentionally use sequential updates. Feedback: correct outputs are 0,1,1,2,3; the broken loop returns 2 at n=2. For one (2,3) item and capacity 4, compare ascending and descending values.

Read This Only If Stuck

Skiena: Fibonacci caching and tabulation. Add your own object-count versus bit-count analysis; the model must accompany every O(1)-space claim.