• Stefam Koch (17/17) Oct 23 2016 Hi Guys,
• Timon Gehr (14/31) Oct 23 2016 int computeFib(int n){
• Stefam Koch (3/43) Oct 23 2016 Wow, that looks intresting.
• Timon Gehr (5/48) Oct 23 2016 It uses a general technique to speed up computation of linear
• Andrei Alexandrescu (4/5) Oct 23 2016 Would be awesome to factor this out of the particular algorithm. I
• safety0ff (4/6) Oct 23 2016 Rosettacode is a good place to check for "floating around"
• Minas Mina (2/19) Oct 23 2016 You can even calculate Fibonacci in O(1).
• Stefam Koch (2/27) Oct 23 2016 An approximation of it.
• Matthias Bentrup (15/43) Oct 24 2016 The fibonacci sequence can be represented exactly as a linear
• Andrea Fontana (5/9) Oct 24 2016 You can simply write it as:
• Era Scarecrow (28/31) Oct 24 2016 Ran your example and it's perfect for 32bit code. But 64bit, not
• Era Scarecrow (9/15) Oct 25 2016 Hmm as an experiment I changed from doubles to reals, and got a
• Andrea Fontana (2/4) Oct 25 2016 Of course floating precision is not unlimited :)
• Timon Gehr (6/31) Oct 23 2016 The closed form does not give you an O(1) procedure that computes the
• Andrea Fontana (20/37) Oct 24 2016 import std.stdio;

Stefam Koch <uplink.coder googlemail.com> writes:

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

Timon Gehr <timon.gehr gmx.ch> writes:

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

Stefam Koch <uplink.coder googlemail.com> writes:

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 ?

Timon Gehr <timon.gehr gmx.ch> writes:

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.

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

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

safety0ff <safety0ff.dev gmail.com> writes:

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

Minas Mina <minas_0 hotmail.co.uk> writes:

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

Stefam Koch <uplink.coder googlemail.com> writes:

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.

Matthias Bentrup <matthias.bentrup googlemail.com> writes:

On Sunday, 23 October 2016 at 23:17:28 UTC, Stefam Koch wrote:
 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.

The fibonacci sequence can be represented exactly as a linear 
combination of two exponential functions, but the two bases of 
the exponentials and the linear multipliers of them are 
irrational numbers, which cannot be represented exactly on a 
computer.

However the rounding error is so small, that rounding to int will 
give you always the correct answer as long as you stay within the 
precision limit of the floating point type you use, e.g. a real 
should give you 64-bit fibonacci in O(1), if the exponential 
function is O(1).

PS: the exact formula is fib(n) = 1/sqrt(5) * (0.5 + 
0.5sqrt(5))^n - 1/sqrt(5) * (0.5 - 0.5sqrt(5))^n. If you round to 
integer anyway, the second term can be ignored as it is always <= 
0.5.

Andrea Fontana <nospam example.com> writes:

On Monday, 24 October 2016 at 08:20:26 UTC, Matthias Bentrup 
wrote:
 PS: the exact formula is fib(n) = 1/sqrt(5) * (0.5 + 
 0.5sqrt(5))^n - 1/sqrt(5) * (0.5 - 0.5sqrt(5))^n. If you round 
 to integer anyway, the second term can be ignored as it is 
 always <= 0.5.

You can simply write it as:
round(phi^n/sqrt(5));

Check my example above :)

Era Scarecrow <rtcvb32 yahoo.com> writes:

On Monday, 24 October 2016 at 08:54:38 UTC, Andrea Fontana wrote:
 You can simply write it as:
 round(phi^n/sqrt(5));

 Check my example above :)

Ran your example and it's perfect for 32bit code. But 64bit, not 
so much. It's only good through 71 iterations (longs) then it 
starts having errors. Also for some odd reason the input is one 
off, so i had to add a -1 to the input for it to align. This 
makes it accurate to 41/64 bit results.

   for(int i = 1; i < 100; ++i) {
     auto cf = computeFib(i);
     auto cfm = computeFibMagic(i-1); //with magic numbers exampled
     writeln(i, ": ", cf, "\t", cfm, "\t", cf == cfm);
   }

64: 10610209857723      10610209857723  true
65: 17167680177565      17167680177565  true
66: 27777890035288      27777890035288  true
67: 44945570212853      44945570212853  true
68: 72723460248141      72723460248141  true
69: 117669030460994     117669030460994 true
70: 190392490709135     190392490709135 true
71: 308061521170129     308061521170129 true
72: 498454011879264     498454011879265 false
73: 806515533049393     806515533049395 false
74: 1304969544928657    1304969544928660        false
75: 2111485077978050    2111485077978055        false
76: 3416454622906707    3416454622906715        false
77: 5527939700884757    5527939700884771        false
78: 8944394323791464    8944394323791487        false
79: 14472334024676221   14472334024676258       false
80: 23416728348467685   23416728348467746       false

Era Scarecrow <rtcvb32 yahoo.com> writes:

On Monday, 24 October 2016 at 19:03:51 UTC, Era Scarecrow wrote:
 It's only good through 71 iterations (longs) then it starts 
 having errors. Also for some odd reason the input is one off, 
 so I had to add a -1 to the input for it to align. This makes 
 it accurate to 41/64 bit results.

 71: 308061521170129     308061521170129 true
 72: 498454011879264     498454011879265 false

  Hmm as an experiment I changed from doubles to reals, and got a 
slightly higher result, up to 85 giving us a 58/64

83: 99194853094755497   99194853094755497       true
84: 160500643816367088  160500643816367088      true
85: 259695496911122585  259695496911122585      true
86: 420196140727489673  420196140727489674      false
87: 679891637638612258  679891637638612259      false
88: 1100087778366101931 1100087778366101933     false

Andrea Fontana <nospam example.com> writes:

On Tuesday, 25 October 2016 at 07:05:20 UTC, Era Scarecrow wrote:
  Hmm as an experiment I changed from doubles to reals, and got 
 a slightly higher result, up to 85 giving us a 58/64


Of course floating precision is not unlimited :)

Timon Gehr <timon.gehr gmx.ch> writes:

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.

Andrea Fontana <nospam example.com> writes:

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