[OT] fastest fibbonacci

[Timon Gehr via Digitalmars-d]

On 23.10.2016 21:59, Minas Mina wrote:
> On Sunday, 23 October 2016 at 13:04:30 UTC, Stefam Koch wrote:
>> Hi Guys,
>>
>> while brushing up on my C and algorithm skills, accidently created a
>> version of fibbonaci which I deem to be faster then the other ones
>> floating around.
>>
>> It's also more concise
>>
>> the code is :
>>
>> int computeFib(int n)
>> {
>>     int t = 1;
>>     int result = 0;
>>
>>     while(n--)
>>     {
>>         result = t - result;
>>         t = t + result;
>>     }
>>
>>    return result;
>> }
>
> You can even calculate Fibonacci in O(1).

The closed form does not give you an O(1) procedure that computes the 
same as the above code (with the same wrap-around-behaviour).

If arbitrary precision is used, the result grows linearly, so the 
calculation cannot be better than linear. I don't think the closed form 
gives you a procedure that is faster than Θ(n·log n) in that case.