[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