[OT] fastest fibbonacci

Timon Gehr via Digitalmars-d digitalmars-d at puremagic.com
Sun Oct 23 08:12:37 PDT 2016


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.)


More information about the Digitalmars-d mailing list