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.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
