Thread: fibonacci sequence

  1. #1
    Registered User cph's Avatar
    Join Date
    Sep 2008
    Location
    Indonesia
    Posts
    86

    fibonacci sequence

    hello, I wrote a code that prints a fibonacci sequence
    Code:
    #include <math.h>
    #include <stdio.h>
    
    /* 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));
    }
    
    int main (void)
    {
        int x;  /* counter */
    
        for (x = 0; x < 100; ++x) {
            printf("%5d%40.0f\n", x, fib(x));
        }
    
        return(0);
    }
    the problem is, when x=71 it prints incorrect result (f[n] != f[n-1] + f[n-2]), it also prints incorrect result for x=76 and after x=79.

    can anyone help me with this problem?

  2. #2
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    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
    "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. #3
    Registered User cph's Avatar
    Join Date
    Sep 2008
    Location
    Indonesia
    Posts
    86
    Quote Originally Posted by QuantumPete View Post
    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
    actually I've tried that (slow) recursive fibonacci algorithm (and the problem is it's too slow).

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    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.

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    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.

  6. #6
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by cph View Post
    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
    Last edited by MK27; 10-16-2008 at 07:03 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

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by MK27 View Post
    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
    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.

  8. #8
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by matsp View Post
    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.
    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

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by MK27 View Post
    I think what matsp means is that he's on the machine, and it took him ten minutes.
    No, my machine takes 10 minutes for the first 50 numbers, when using the trivial recursive method. Iteratively, it is very much faster.

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

  10. #10
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    Quote Originally Posted by matsp View Post
    No, my machine takes 10 minutes for the first 50 numbers, when using the trivial recursive method. Iteratively, it is very much faster.

    --
    Mats
    Probably due to the overhead of creating stack frames and the like. I'm guessing what the OP is trying to do is to generate an approximation to the right number.

    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

  11. #11
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quantum Pete and I are in the same iterative boat, I think.

    What would the "trivial recursive method" look like?
    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

  12. #12
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    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
    "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

  13. #13
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    [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.
    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. #14
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    Quote Originally Posted by MK27 View Post
    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
    "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

  15. #15
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    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
    "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

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