Re:Node-fib: Fast non-blocking fibonacci server
by jules on Monday October 03, 2011 @03:32PM
(#3067638)
That formula fails for fib(71) with double precision floating point arithmetic:
And it's not that the latter is not exactly representable as a floating point number:
So you'd have to use bigger precision numbers. How many digits are you going to use? You have to use enough not to produce a wrong result and not too many to slow down the algorithm. I bet that the resulting algorithm is slower than the standard [1 1; 1 0]^n matrix exponentiation. Note that your formula comes from the eigenvalue expansion of this matrix exponentiation, which -- despite what you might hear from undergraduate linear algebra courses -- is not a good method for matrix exponentiation. On the contrary, finding eigenvalues is done by a process analogous to matrix exponentiation: http://en.wikipedia.org/wiki/Power_iteration
[ Parent
| on HN ]
There are no comments on this comment yet.