why memoizing is faster

[Terry Reedy]

On 3/26/2011 11:49 AM, Steven D'Aprano wrote:
> On Sat, 26 Mar 2011 07:14:17 -0700, eryksun () wrote:

>> 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

In the real number system, the above is the exact integer.

 >>          return int(f)

In the real number system, this would by a pure type cast, with no 
truncation. In the float system, where, in general, answers could be a 
bit too small as well as too big, rounding might be better. If one 
truncates real numbers, there is no need (except for fib(0)) to subtract 
(1-phi)**n as that is always less than 1 (except for fib(0)). However..

> Have you tried it?

I have been thinking about it. Thanks for doing 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.

So it appears that float_phi > real_phi, so that the powers get 
increasingly too large with n. Even without thisproblem, Rounding would 
happen anyway as soon as fib(n) had 18 digits (for standard 8-byte floats).

If one uses fib(n) in a floating point calculation, the error might not 
matter, but if one is verifying any of the existing exact equality 
theorems or searching for a new one, exact values are necessary.

-- 
Terry Jan Reedy