Thread: fibonacci sequence

Originally Posted by MK27

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:

Of course, my code only provides you with a final answer. It's not designed to print out all the fibonacci numbers along the way. That very much depends on the requirements for the program!

QuantumPete

This is what I get:

Code:

 time ./fib.tsk 50
Result = -298632863

real    13m27.65s
user    11m42.11s
sys     0m4.31s

Obviously it's wrapped around, since i'm only using ints instead of unsigned long longs. I've also got a version that uses a run-time populated table to speed up calculation.

Code:

 time ./fib_table.tsk 50
Fib for 50 = -298632863

real    0m0.02s
user    0m0.01s
sys     0m0.01s

QuantumPete

Originally Posted by MK27

Really it's useless, since you might as well use the iterative approach and just limit the output to the final loop (as matsp just noted).

That's "useless" too, since you might as well use the formula

Except the original poster is complaining that the result is inexact - I suspect it's simply that the double precision isn't good enough...

--
Mats

Originally Posted by matsp

Except the original poster is complaining that the result is inexact - I suspect it's simply that the double precision isn't good enough...

--
Mats

True, but why use an approximation, when a computed-table approach will get you the result almost as fast?

QuantumPete

This is similar to what matsp posted, except it will take arbitrary numbers:

Code:

typedef unsigned long long ull;

ull fib_t (int num, ull * precalc) {
    if (num <= 2) {
        return 1;
    }
    if (precalc[num] == 0) {
        precalc[num] =  fib_t(num-1, precalc) + fib_t (num-2, precalc);
        printf ("&#37;d = %llu\n", num, precalc[num]);
    }
    return precalc[num];
}

int main (int argc, char ** argv) {
    int num = 0;
    ull * table = 0; 
    if (argc != 2) {
        printf ("You must specifiy a number\n");
        return 1;
    }

    num = atoi (argv[1]);
    table = calloc (num+1, sizeof (ull));
    if (table == 0) {
        printf ("malloc failed!\n");
        return 1;
    }

    printf ("Fibonacci Number for %d = %llu\n", num, fib_t(num, table));
    free (table);
    return 0;
}

It even prints out all the numbers as it computes them

QuantumPete

Originally Posted by MK27

But it's very clever -- I could not even have thought that one up, and am still staring at it and inserting printf's to figure out what's going on. My eyes tell me it should have either looped forever, or always returned 2.

Checking the Wikipedia entry on the Fibonacci numbers, I see that one can actually derive it directly from the recurrence relation presented there. I also recall that it was the introductory example of at least one algorithms textbook. Consequently, I suggest that you work through such a text to help you understand recursion better.

Originally Posted by matsp

Except the original poster is complaining that the result is inexact - I suspect it's simply that the double precision isn't good enough...

Yes, I think so too.

Originally Posted by QuantumPete

True, but why use an approximation, when a computed-table approach will get you the result almost as fast?

If a formula that is not difficult to implement produces the result as fast and as accurately as using memoization, I would certainly prefer the formula since it has constant space complexity.

Originally Posted by laserlight

If a formula that is not difficult to implement produces the result as fast and as accurately as using memoization, I would certainly prefer the formula since it has constant space complexity.

But that formula can only be an approximation; true it depends on the requirements, but in the end iterative, recursive and computed-table are the only ways to implement the original fibonacci series correctly, no?

QuantumPete

Originally Posted by QuantumPete

But that formula can only be an approximation; true it depends on the requirements, but in the end iterative, recursive and computed-table are the only ways to implement the original fibonacci series correctly, no?

Mathematically, the formula is indeed another way to compute the nth number in the original Fibonacci series, but in practice, it is an approximation since we do not have infinite precision floating point arithmetic. On the other hand, the approximation can be accurate, since we are dealing with integers in the end.

Okay, I'm really busted by this one! Short of reading the recommended book, can anyone help explain it? I used the following

Code:

#include <stdio.h>

int fib (int num) {
	int x, y;
	printf("fib: %d\n", num);
	if (num <= 2) {
		return 1;
	}
	x=fib(num-1); y=fib(num-2);
	printf("x: %d y: %d\n", num);
	fflush(stdout);
	return x+y;
}

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

./a.out 3
to fib: 1
fib: 1
answer: 1

to fib: 2
fib: 2
answer: 1

to fib: 3
fib: 3
fib: 2
fib: 1
x: 3 y: 0
answer: 2

How does x end up as 3, y as 0, and the answer as 2?

Because your printf isn't being given the right data:

Code:

printf("x: %d y: %d\n", num);

If it's gcc, -Wall will tell you that you have one too few arguments, even if it is not telling you that num isn't x or y.

--
Mats

Yeah that was dumb. I'm staring at the real output now.

I still don't get it....[later] maybe I do...

to fib: 5 okay
fib: 5 right...
fib: 4
fib: 3
fib: 2
fib: 1
x: 1 y: 1 that makes sense
fib: 2 and this
x: 2 y: 1 so finally x's x is 2 (1+1)
fib: 3 y's x (?)
fib: 2
fib: 1
x: 1 y: 1
x: 3 y: 2 x is 2+1, y is 1+1
answer: 5

Is that right? I'm shaky about the last bit.