Thread: fibonacci sequence

You know what laserlight, I had an unfortunate IO error (That would be "Idiot Operator" not "Input/Output"). Yeah it works fine.. I am just a boob sometimes.

And yeah I tried the non-trigonometric version when I was looking at the derivation which is why I wasn't following how come my results weren't working. But it works fine.

Originally Posted by MK27

Oh malarky

Code:

#include <stdio.h>

int main () {
	int a=0, b=1, n=a+b,i,ii;
	puts("Number of iterations");
	scanf("&#37;d",&ii);
	printf("%d %d ",a,b);
	for (i=0;i<ii;i++) {
		n=a+b;
		printf("%d ",n);
		a=b;b=n;
	}
}

I don't know much math, so I'd be really interested to read how you could make this computation "more efficient".

[edit] i guess this is actually iterative, and not recursive

That was a challenge! Here is my contest entry:

Code:

int fib(int n) {
int a[2] = { 0, 1 }, i;
for (i = n + 1 >> 1 ; i; i--)
    a[0] += a[1] += a[0];
return a[n & 1]; }

This takes about 1/2 the time yours does. But caution: highest legit value is 64. Gives 1,640,636,603 which is the largest integer that fits into 32 bit. I could go 64-bit but for timing purposes I just threw the two functions into another loop - executing factorial(64) 10,000,000 times.

Yours took about 12-13 seconds.
Mine is around 6-7 seconds.
(Mac laptop 1.33 GHz PowerPC G4)

um, excuse me, may I rephrase my question?

Code:

/* http://goldennumber.net/five(5).htm */
#define PHI pow(M_E, asinh(0.5))

/* http://goldennumber.net/five(5).htm */
double fib (unsigned int n)
{
    return((pow(PHI, (double)n)) / sqrt(5.0));
}

I need to get the right result from the function fib(), because when n=71, n=76, and after n=79 the function returns incorrect result (f[n]!=f[n-1]+f[n-2]).

Originally Posted by cph

I need to get the right result from the function fib(), because when n=71, n=76, and after n=79 the function returns incorrect result (f[n]!=f[n-1]+f[n-2]).

64-bit numbers?
GMP?

You are asking how to reach above and beyond a hardware limitation. You are asking how to make your computer do something that is beyond the implementation of your algorithm. Right? I mean you see how I arrive at that conclusion, right?

Originally Posted by matsp

Code:

a[0] += a[1] += a[0];

isn't that UB?

Code:

i = (n + 1) >> 1

??

--
Mats

+= associativity is right-to-left just as any assignment, so I assume it is executed in that order.

(n + 1) >> 1 - true, but I abhor extra parenthesis when they're not needed. Operator precedence is such that addition is done before the shift.

Thanks for that explanation, laserlight. i was starting to get worried that I am misunderstanding associativity in any standard precedence chart. What is it then if "right-to-left" is not related to execution order? The right argument is evaluated first, I thought.

Sorry to bump an old thread, but I came accross this accidentally and wanted to share my thoughts.

First of all, the problem with this method posted above:

Code:

pow(PHI, n) / sqrt(5.0)

is that it's simply incorrect, or incomplete. It's only half of the Fibonacci recurrence relation.

The correct way would be:

Code:

int Fib( int n )
{
  static const double s = sqrt(5.0);
  return int( (pow(1+s,n)-pow(1-s,n))/(pow(2.0,n)*s) );
}

(use long long instead of int for large n, as the result will obviously not fit in 32 bit integers).

There is, however, an even much faster way. After quite some experimenting with several approaches and lotsa optimizing, this is imho the ultimate solution: (besides using a direct lookup or caching table of course)

Code:

unsigned int Fib( unsigned int n )
{
  n--;
  unsigned int a=1,b=0,c=1,p=1,t;
  while (p<=n) p += p;
  do
  {
    p >>= 1;
    t = b*b;
    b *= a+c;
    a = a*a + t;
    c = c*c + t;    
    if (n&p)
    {
      c = b;
      b = a;
      a += c;
    }
  }
  while (p>1);
  return a;
}

This performs about 3 times as fast as the pow / √5 method. Of course, again, use long long for large n.

Originally Posted by laserlight

It is not incorrect in its idea since the idea is that the other half can be ignored as it has negligible contribution in the approximation. I demonstrated a correct way to perform this approximation in post #45.

Ah I see, you're right, the correction you applied indeed makes up for the missing term.

Nonetheless, when I compare this "single pow" method to my integer version, the latter is still almost 15% faster.