Faster Recursive Fibonacci Numbers

[geremy condra]

On Thu, May 19, 2011 at 3:47 PM, 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
>> def fib(n):
>>     numerator = (φ**n) - (1 - φ)**n
>>     denominator = sqrt(5)
>>     return round(numerator/denominator)
>
> 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.

Great point, and something I should have paid attention to. Thanks.

Geremy Condra