News for hackers. Stuff that matters.
Re:Introducing Surinx (Ruby syntax w/ Java typing) by raganwald on Wednesday August 26, 2009 @11:34AM (#787348)
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.

There are no comments on this comment yet.