why memoizing is faster

[eryksun ()]

On Saturday, March 26, 2011 11:49:02 AM UTC-4, Steven D'Aprano wrote:
> >
> >     def fib(n):
> >         phi = (5 ** 0.5 + 1) / 2
> >         f = (phi ** n - (1 - phi) ** n) / 5 ** 0.5 
> >         return int(f)
> 
> Have you tried it?
> 
> Unfortunately, with floating point rounding error, that rapidly becomes 
> inaccurate. It gives:
> 
> >>> fib(72)
> 498454011879265
> 
> compared to the correct value of 498454011879264 (an error of 1) and 
> rapidly gets worse. It's true that the above formula is correct for real 
> numbers, but floats are not reals. Unless you have an infinite number of 
> decimal places, it will be inaccurate.

That's true. If you need more than double precision, obviously it's time to defer to the experts. Here's an O(n) algorithm:

http://www.gnu.org/software/gmp/manual/html_node/Fibonacci-Numbers-Algorithm.html

This library is wrapped by the gmpy extension module:

http://code.google.com/p/gmpy

I was just shocked to see 200 MB of memory used up like chump change, and I immediately looked for an alternative. In practice, I prefer to rely on libraries created by specialists who have carefully worked out the best trade-offs for typical use, and puzzled through the algorithms needed to compute that which is so easy to derive on paper (such as my simple little Z-transform derived formula that fails so wonderfully in practice). I'm not a computer scientist; I don't even play one on TV.