Faster Recursive Fibonacci Numbers

[geremy condra]

On Tue, May 17, 2011 at 2:04 PM, Wolfram Hinderer
<wolfram.hinderer at googlemail.com> wrote:
> On 17 Mai, 20:56, geremy condra <debat... at gmail.com> wrote:
>> On Tue, May 17, 2011 at 10:19 AM, Jussi Piitulainen
>>
>> <jpiit... 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 ;).
>
> I think you can write it even more funny
>
> def fib(n):
>    return round(((.5 + .5 * 5 ** .5) ** n -  (.5 - .5 * 5 ** .5) **
> n) * 5 ** -.5)
>
> ;-)

Ok, that's amusing. It does hide the interaction with the golden ratio
though, which is what I find so fascinating about the earlier one.

Geremy Condra