[OT] fastest fibbonacci

[Timon Gehr via Digitalmars-d]

On 23.10.2016 17:42, Stefam Koch wrote:
> On Sunday, 23 October 2016 at 15:12:37 UTC, Timon Gehr wrote:
>> On 23.10.2016 15:04, 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;
>>> }
>>>
>>
>> int computeFib(int n){
>>     int[2] a=[0,1],b=[1,2],c=[1,-1];
>>     for(;n;n>>=1){
>>         foreach(i;1-n&1..2){
>>             auto d=a[i]*a[1];
>>             a[i]=a[i]*b[1]+c[i]*a[1];
>>             b[i]=b[i]*b[1]-d;
>>             c[i]=c[i]*c[1]-d;
>>         }
>>     }
>>     return a[0];
>> }
>>
>> (Also: you might want to use BigInt.)
>
> Wow, that looks intresting.
> Can you explain how it computes fibbonacci ?

It uses a general technique to speed up computation of linear 
recurrences, with a few additional optimizations. One iteration of your 
while loop multiplies the vector (result,t) by a matrix. I exponentiate 
this matrix using a logarithmic instead of a linear number of operations.