3 ms·
How to compute Fib(n) in log(n) time
- cperciva 17y agoCorrection: This computes Fib(n) in O(n log n log log n) time given a fast integer multiplication.
- Xichekolas 17y agoYeah, it's only logarithmic in the number of matrix multiplications, so the title is a bit hyperbolic, but I just thought the technique was cool. I got there via: http://blog.sigfpe.com/2008/11/approach-to-algorithm-parallelisation.html http://blog.sigfpe.com/2008/11/approach-to-algorithm-paralle... Which was perhaps more informative as to the actual technique, but had less obvious wow factor. My bad.