Thread: fibonacci sequence

That's because you're not calculating the Fibonacci series. The fibonacci series is simply starting with 1 and 1 and every subsequent number in the series is the sum of the preceding two. You definitly don't need pow, sqrt or doubles to accomplish that. At its simplest it's just a recursive algorithm.

QuantumPete

Of course, if you want to calculate all fibonacci numbers from fib(1) to fib(n) where n is a relatively large number, you may want to solve the problem in a different way than recursively - for example, you could store the previous results in an array (or just keep the last two values) - that way, you don't need to calculate ALL the values from fib(1) to fib(x-1) before you get fib(x).

--
Mats

Just to confirm, calculating every fib(n) for 0..4999999 takes 0.11 seconds using an array to store the previous values [I doubt that the higher numbers are actually correct, as my math uses integers to calculate the fibonacci values - and at some point pretty soon the integer values overflow - I just went that far to get past 0.0 seconds].

--
Mats

Originally Posted by cph

actually I've tried that (slow) recursive fibonacci algorithm (and the problem is it's too slow).

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

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("%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".

Well, of course, if you ONLY want to know what fibonacci number 43 is, you will have to loop around. On my machine, using the recursive method, it takes 621 seconds to do the first 50 - but that's not the time it takes to do one number.

--
Mats

Originally Posted by matsp

On my machine, using the recursive method, it takes 621 seconds to do the first 50 - but that's not the time it takes to do one number.

I think what matsp means is that he's on the machine, and it took him ten minutes.

Code:

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

isn't that UB?

Code:

i = (n + 1) >> 1

??

--
Mats

Originally Posted by QuantumPete

That's because you're not calculating the Fibonacci series.

But that's what it calculates. The fibbonacci series does have a closed form representation. Off the top of my head I'm not sure if the formula implemented here is the correct one, but I suspect that it is, given that things don't go wrong until the 71st element.

I'd attribute the problem to simple floating point inaccuracy.

Code:

int fib (int num) {
    if (num < 2) {
      return 1;
    }
    return fib (num-1) + fib(num-2);
}

Something like that. I haven't tested it.

QuantumPete

[QUOTE=QuantumPete;797086]

Code:

int fib (int num) {
    if (num < 2) {
      return 1;
    }
    return fib (num-1) + fib(num-2);
}

If num = 3, it will take even more than ten minutes...it could take forever.

Originally Posted by MK27

If num = 3, it will take even more than ten minutes...it could take forever.

I just tested it and though it should be an "<=" instead of just "<", it does work properly and returns immediately.

QuantumPete

Originally Posted by QuantumPete

I just tested it and though it should be an "<=" instead of just "<", it does work properly and returns immediately.

QuantumPete

Wow. You are correct (except the first number is 0...).

Using this loop to produce the first 45 (I think it wraps after that) did take more than a minute tho, whereas the iteritive one is instant:

Code:

int main (int argc, char *argv[]) {
	int answer,i;
	
	for (i=1;i<=atoi(argv[1]);i++) {
		answer=fib(i);
		printf("%d ", answer);
	}
}