Faster Recursive Fibonacci Numbers

[Steven D'Aprano]

On Fri, 20 May 2011 09:37:59 +1000, Chris Angelico wrote:

> On Fri, May 20, 2011 at 8:47 AM, Steven D'Aprano
> <steve+comp.lang.python at pearwood.info> wrote:
>> On Tue, 17 May 2011 10:02:21 -0700, geremy condra wrote:
>>
>>> or O(1):
>>>
>>> φ = (1 + sqrt(5)) / 2
>>>     numerator = (φ**n) - (1 - φ)**n
>>
>> I'd just like to point out that, strictly speaking, it's only O(1) if
>> you assume that exponentiation is O(1). Computer scientists often like
>> to make this simplifying assumption, and it might even be true for
>> floats, but for long ints and any numeric data types with unlimited
>> precision, it won't be.
>>
>>
> Python doesn't have arbitrary precision non-integers, does it? So this
> is going to be done with floats.

Sure, which is why the above fib() function will become increasing 
inaccurate beyond some given n, by memory about n=71 or so. Er, at least 
the fib() function that *was* above until you deleted most of it :)

If you want an *accurate* fib() function using exponentiation of φ, you 
need arbitrary precision non-integers.

Nevertheless, at some point you will hit the limit of floats, which 
thanks to the exponential growth of the Fibonacci sequence won't take 
that long: it takes roughly 1475 iterations to exceed the range of Python 
floats.


-- 
Steven