Thread: fibonacci sequence

  1. #16
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by QuantumPete View Post
    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);
    	}
    }
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  2. #17
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    Quote Originally Posted by MK27 View Post
    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
    Last edited by QuantumPete; 10-16-2008 at 10:40 AM.
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

  3. #18
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I think we are ALL saying the same thing: don't use recursion alone to calculate fibonaccie sequences. If you only need the ONE value, then calculate it iteratively - it's almost instant for small and large n (at least as long as n is 32-bit integer). If you want a list of the first X numbers, then you will need to store the results as you go along into an array. I wrote a recursive array variant:
    Code:
    #define SIZE 5000000
    
    int fibarr[SIZE];
    int maxn = -1;
    
    
    int fib2(int n)
    {
        if (n <= maxn)
        {
    	return fibarr[n];
        }
        if (n == 0)
    	return fibarr[0] = 0;
    
        if (n <= 2)
        {
    	fibarr[n] = 1;
    	return 1;
        }
        fibarr[n] = fib2(n-1) + fib2(n-2);
        if (maxn < n)
    	maxn = n;
        
        return fibarr[n];
    }
    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #19
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by QuantumPete View Post
    Of course, my code only provides you with a final answer.
    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).

    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.
    Last edited by MK27; 10-16-2008 at 08:33 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #20
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote 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
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #21
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #22
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    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
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

  8. #23
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote 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.

    Quote 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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #24
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    Quote Originally Posted by matsp View Post
    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
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

  10. #25
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote 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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #26
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    Quote Originally Posted by laserlight View Post
    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
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

  12. #27
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote 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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #28
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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?
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  14. #29
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  15. #30
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Yeah that was dumb. I'm staring at the real output now.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Fibonacci Sequence
    By Dogmasur in forum C Programming
    Replies: 15
    Last Post: 08-10-2008, 07:55 AM
  2. Fibonacci sequence
    By MuffanMan123 in forum C++ Programming
    Replies: 6
    Last Post: 02-26-2008, 09:15 AM
  3. Immediate programming help! Please!
    By xMEGANx in forum C++ Programming
    Replies: 6
    Last Post: 02-20-2008, 12:52 PM
  4. Fibonacci sequence output statement
    By chocha7 in forum C++ Programming
    Replies: 10
    Last Post: 11-18-2004, 11:04 PM
  5. Fibonacci sequence
    By girliegti in forum C++ Programming
    Replies: 8
    Last Post: 09-30-2003, 10:40 PM