16 Aug
2010
16 Aug
'10
9:53 p.m.
On Aug 17, 2010, at 12:37 AM, Roel van Dijk wrote:
phi = (1 + sqrt 5) / 2 fib n = ((phi ** n) - (1 - phi) ** n) / sqrt 5
The use of (**) should make the complexity at least O(n). Please correct me if I'm wrong (or sloppy).
Using the classic x**0 = 1 x**1 = x x**(2k+0) = (x**2)**k k > 0 x**(2k+1) = (x**2)**k + x k > 1 powers of smallish numbers or matrices can be computed in logarithmic time. Using x**n = exp(n*log(x)) and floating point arithmetic, the whole thing can be done in O(1) time, and the price of some inaccuracy. Using double precision arithmetic, I get fib(52) = 32951280099.0001 which is clearly wrong. Truncation will save you, up to fib(72) = 498454011879265.1875 which is wrong in the units place.