Re:Node-fib: Fast non-blocking fibonacci server
by SamReidHughes on Tuesday October 04, 2011 @02:25AM
(#3069661)
Binet's formula doesn't run in O(1) if you want an exact answer. Using a + b * sqrt(5) representations or floating point with sufficient precision, you can get O(n log n 2^O(log* n)) time (quoting Wikipedia's Furer's algorithm page here). Which beats O(n log n log log n) time, if you were wondering. If something beats that for computing Fibonacci numbers, that'd be pretty cool.
[ Parent
| on HN ]
There are no comments on this comment yet.