Sorry, I didn't mean log (2n), I meant (log sub 2) n. Or in other words, the computation times is proportional to the number of binary bits in n. The algorithm

Sorry, I didn't mean log (2n), I meant (log sub 2) n. Or in other words, the computation times is proportional to the number of binary bits in n. The algorithm is remarkably simple. Given that fib(40) can be extracted from: 40 [ 1 1 ] [ 1 0 ] The simplest implementation, as you surmise, is to do 40 matrix multiplications. I don't think that part is dynamic. the dynamic part comes in observing that n^40 = (n^20)^2. This can be followed downward recursively: n^20 = (n^10)^2, n^10 = (n^5)^2, n^5 = (n^2)^2 * n and n^2 = n * n. So... The actual matrix multiplication is much slower than a simple bignum multiplication, but there are only six such operations to perform.