[–] cperciva 16y ago ↗ Correction: This computes Fib(n) in O(n log n log log n) time given a fast integer multiplication. [–] Xichekolas 16y ago ↗ Yeah, 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-paralle...Which was perhaps more informative as to the actual technique, but had less obvious wow factor. My bad.
[–] Xichekolas 16y ago ↗ Yeah, 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-paralle...Which was perhaps more informative as to the actual technique, but had less obvious wow factor. My bad.
2 comments
[ 3.1 ms ] story [ 32.7 ms ] threadI got there via: 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.