why memoizing is faster

[Steven D'Aprano]

On Sat, 26 Mar 2011 07:14:17 -0700, eryksun () wrote:

> On Saturday, March 26, 2011 7:50:36 AM UTC-4, Steven D'Aprano wrote:
>> 
>> That's of the order of 200 MB of memory -- not that much for today's
>> systems. I've had people email me .doc files that big *wink*
> 
> Yikes! I know this thread is about caching the output of a function, but
> in the example of Fibonacci numbers, we're blessed with an easily
> derived closed form expression (via Z transform, etc):
> 
>     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.



-- 
Steven