Faster Recursive Fibonacci Numbers

[Chris Angelico]

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.

Chris Angelico