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
--
http://mail.python.org/mailman/listinfo/python-list
