This is a tutorial to find large fibonacci numbers using matrix exponentiation, speeded up with binary exponentiation.
The part where dynamic programming comes in, is when storing the 2th powers of the base matrix.

We do this using an array where each element is populated using the square of the last element. a[i]=a[i-1]^2.
The fibonacci sequence can be evaluated using the recursive matrix form as shown in this lecture. This lets us evaluate the Nth fibonacci term in O(logN)

References:
Fibonacci Numbers:
[ Ссылка ]

Matrix exponentiation:
[ Ссылка ]
[ Ссылка ]

Solving Recurrences:
[ Ссылка ]

Code Link: [ Ссылка ]

#fibonacci #matrix-exponentiation #dynamic-programming

свернуть