Matrix exponentiation

Can we beat the linear cost? Yes, by writing the recurrence in matrix form. Stack two consecutive terms and notice:

   | F(n+1) |   | 1  1 |   | F(n)   |
   |        | = |      | * |        |
   | F(n)   |   | 1  0 |   | F(n-1) |

Multiplying by this matrix advances one step. Applying it n times gives a remarkable identity:

   | 1  1 |^n   | F(n+1)  F(n)   |
   |      |   = |                |
   | 1  0 |     | F(n)    F(n-1) |

So computing F(n) amounts to raising this matrix to the power n. And a power is computed by fast exponentiation: instead of multiplying n times, you square repeatedly by reading n in binary.

   M^16 = ((((M^2)^2)^2)^2)      (4 squarings, not 15 products)

Cost: logarithmic, O(log n) multiplications of 2×2 matrices. You reach F(1 000 000) in a handful of operations, where iteration would need a million.

This form also yields elegant identities as a bonus. Taking the determinant of the equality above (the base matrix has determinant −1, so its n-th power has determinant (−1)^n):

   F(n-1) * F(n+1) − F(n)²  =  (−1)^n       (Cassini's identity)

A single idea — seeing the recurrence as a matrix — provides both the fastest algorithm and elegant formulas. This is the full power of linear algebra put to work on a sequence of integers.