Optimal Fibonacci Computation

Worked Solution

How to Think About It: The Fibonacci recurrence $F(n) = F(n-1) + F(n-2)$ screams "dynamic programming," and the naive DP solution runs in $O(n)$ time with $O(1)$ space -- which is fine for small $n$. But when $n$ can be $10^{18}$, linear time is way too slow. The key observation is that the Fibonacci recurrence is a *linear* recurrence, which means it can be expressed as a $2 \times 2$ matrix multiplication. Once you see that, you can use repeated squaring (fast exponentiation) to compute the $n$-th power of that matrix in $O(\log n)$ multiplications.

Algorithm:

The Fibonacci recurrence can be written in matrix form:

$$\begin{pmatrix} F(n+1) \\\\ F(n) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\\\ 1 & 0 \end{pmatrix} \begin{pmatrix} F(n) \\\\ F(n-1) \end{pmatrix}$$

Applying this repeatedly gives:

$$\begin{pmatrix} F(n+1) \\\\ F(n) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\\\ 1 & 0 \end{pmatrix}^{n} \begin{pmatrix} 1 \\\\ 0 \end{pmatrix}$$

So $F(n)$ is the bottom-left (or top-right) entry of the matrix $M^n$ where $M = \begin{pmatrix} 1 & 1 \\\\ 1 & 0 \end{pmatrix}$.

To compute $M^n$ in $O(\log n)$ steps, use exponentiation by squaring:

1. Start with result = I (identity matrix) and base = M. 2. While $n > 0$: - If $n$ is odd, multiply result = result * base. - Square the base: base = base * base. - Integer-divide $n$ by 2. 3. Return result[1][0] (which is $F(n)$).

Each step involves a constant number of $2 \times 2$ matrix multiplications (4 multiplies and 2 adds each), so the total work is $O(\log n)$ multiplications.

Code:

```python def fib(n: int) -> int: """Compute F(n) in O(log n) time via matrix exponentiation.""" if n == 0: return 0

def mat_mul(A, B): return [ [A[0][0] * B[0][0] + A[0][1] * B[1][0], A[0][0] * B[0][1] + A[0][1] * B[1][1]], [A[1][0] * B[0][0] + A[1][1] * B[1][0], A[1][0] * B[0][1] + A[1][1] * B[1][1]] ]

result = [[1, 0], [0, 1]] # identity matrix base = [[1, 1], [1, 0]] # Fibonacci matrix

while n > 0: if n % 2 == 1: result = mat_mul(result, base) base = mat_mul(base, base) n //= 2

return result[0][1] ```

For comparison, here are the slower approaches:

```python # O(n) time, O(1) space -- iterative DP def fib_linear(n: int) -> int: a, b = 0, 1 for _ in range(n): a, b = b, a + b return a

# O(2^n) time, O(n) space -- naive recursion (never use this) def fib_naive(n: int) -> int: if n <= 1: return n return fib_naive(n - 1) + fib_naive(n - 2) ```

Complexity:

| Method | Time | Space | |---|---|---| | Naive recursion | $O(2^n)$ | $O(n)$ | | Memoized recursion | $O(n)$ | $O(n)$ | | Iterative DP | $O(n)$ | $O(1)$ | | Matrix exponentiation | $O(\log n)$ | $O(1)$ |

Note: the $O(\log n)$ bound counts matrix multiplications. If you account for big-integer arithmetic (since $F(n)$ has $O(n)$ digits), the true cost is $O(n \log n)$ bit operations, but this is still dramatically faster than the $O(n^2)$ bit operations of the iterative approach for large $n$.

Answer: The optimal approach uses matrix exponentiation: express the Fibonacci recurrence as $M^n$ where $M$ is the $2 \times 2$ transition matrix, then compute $M^n$ via repeated squaring in $O(\log n)$ matrix multiplications.