3 ms·
The site is down now, but from looking at wikipedia, you are probably right. (Sorry, I just glanced at the way they were using the matrix before, and assumed t
by lliiffee 17y ago
The site is down now, but from looking at wikipedia, you are probably right. (Sorry, I just glanced at the way they were using the matrix before, and assumed they did n matrix multiplies to calculate fib(n)) I think you are also right about the complexity, though people would usually just write log(n) since log(a*b)=log(a)+log(b).
- raganwald 17y agoSorry, 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.