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;
}

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

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 ?

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.

On 10/23/16 12:32 PM, Timon Gehr wrote:
> It uses a general technique to speed up computation of linear recurrences

Would be awesome to factor this out of the particular algorithm. I recall SICP famously does that with a convergence accelerating technique for series. -- Andrei

On Sunday, 23 October 2016 at 13:04:30 UTC, Stefam Koch wrote:
>
> created a version of fibbonaci which I deem to be faster then the other ones floating around.

Rosettacode is a good place to check for "floating around" implementations of common practice exercises e.g.:

http://rosettacode.org/wiki/Fibonacci_sequence#Matrix_Exponentiation_Version

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

On Sunday, 23 October 2016 at 19:59:16 UTC, 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).

An approximation of it.

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.

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;
> }
import std.stdio;
import std.math: pow;

int computeFib(int n)
{
	if (n==0) return 1;
	
    // Magic :)
	enum magic_1 = 1.61803398874989484820458683436563811772030917980576286213544862270526046281890244970720720418939113748475;
	enum magic_2 = 2.23606797749978969640917366873127623544061835961152572427089724541052092563780489941441440837878227;
	return cast(int)((0.5+pow(magic_1,n+1))/magic_2);
	
}

void main()
{

	for(int i = 0; i < 10; ++i) writeln(computeFib(i));
	
}