Documentation

Consider the following matrix equation, where \(F(n)\) is the \(n\)th Fibonacci number:

\[ \begin{pmatrix} x_2 \\ x_1 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F(n+1) \\ F(n) \end{pmatrix} \]

When written out as linear equations, this is equivalent to:

\[ \begin{align} x_2 & = F(n+1) + F(n) \\ x_1 & = F(n+1) \end{align} \]

So \(x_2 = F(n+2)\) and \(x_1 = F(n+1)\). Together with the associativity of matrix multiplication, this means:

\[ \begin{pmatrix} F(n+2) \\ F(n+1) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F(n+1) \\ F(n) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^2 \begin{pmatrix} F(n) \\ F(n-1) \end{pmatrix} = \cdots = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} F(2) \\ F(1) \end{pmatrix} \]

Take advantage of this to write a function which computes the \(n\)th Fibonacci number with \(O(\log n)\) multiplications.

Compare with the solution for Problems.P29:

$ stack bench --benchmark-arguments="P29/fibonacci P30/fibonacci'"

Examples

>>> map fibonacci' [1..10]
[1,1,2,3,5,8,13,21,34,55]

>>> fibonacci' 1000000
19532821287077577316...

>>> length $ show $ fibonacci' 1000000
208988

Hint