[OT] fastest fibbonacci

Stefam Koch via Digitalmars-d digitalmars-d at puremagic.com
Sun Oct 23 08:42:15 PDT 2016


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 ?


More information about the Digitalmars-d mailing list