Re:Introducing Surinx (Ruby syntax w/ Java typing)
by lliiffee on Wednesday August 26, 2009 @11:18AM
(#787305)
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).
[ Parent
| on HN ]
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.