Faster Recursive Fibonacci Numbers

[geremy condra]

On Tue, May 17, 2011 at 10:19 AM, Jussi Piitulainen
<jpiitula at ling.helsinki.fi> wrote:
> geremy condra writes:
>
>> or O(1):
>>
>> φ = (1 + sqrt(5)) / 2
>> def fib(n):
>>     numerator = (φ**n) - (1 - φ)**n
>>     denominator = sqrt(5)
>>     return round(numerator/denominator)
>>
>> Testing indicates that it's faster somewhere around 7 or so.
>
> And increasingly inaccurate from 71 on.

Yup. That's floating point for you. For larger values you could just
add a linear search at the bottom using the 5f**2 +/- 4 rule, which
would still be quite fast out to about 10 times that. The decimal
module gets you a tiny bit further, and after that it's time to just
use Dijkstra's, like rusi suggested. In any event, I still think this
formulation is the most fun ;).

Geremy Condra