Re:V8 is faster than GCC
by davidtgoldblatt on Friday June 10, 2011 @07:08PM
(#2642740)
In fact, since the fibonacci sequence grows as O(phi^n), we need O(n) digits to hold the n'th fibonacci number, so the fastest possible algorithm to compute the n'th fibonacci number must run in time Omega(n).
[ Parent
| on HN ]
Not necessarily if you can parallelize computing the digits. Your average Pentium processor can compute a floating-point number with a mantissa of 16 decimal or 52 binary digits in one clock cycle, not 16 or 52. It does so by using enough silicon to compute them all in parallel.