2 ms·
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
by davidtgoldblatt 15y ago
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).
- T-hawk 15y agoNot 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.
- aidenn0 15y agoThat's only a constant factor improvement. What if you want to calculate 104 binary digits?