[Haskell-cafe] Question about memory usage

[Richard O'Keefe]

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.