Faster Recursive Fibonacci Numbers

[Steven D'Aprano]

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.



-- 
Steven