fibonacci sequence

This is a discussion on fibonacci sequence within the C Programming forums, part of the General Programming Boards category; I still don't get it....[later] maybe I do... to fib: 5 okay fib: 5 right... fib: 4 fib: 3 fib: ...

  1. #31
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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.
    Last edited by MK27; 10-16-2008 at 09:49 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

  2. #32
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    You probably want to instrument each of the return lines to show what they are actually returning, but 2 + 3 is fib(3) + fib(4) -> fib(5).

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

  3. #33
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by matsp View Post
    You probably want to instrument each of the return lines to show what they are actually returning
    Wouldn't that be x+y?
    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

  4. #34
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by MK27 View Post
    Wouldn't that be x+y?
    Yes, or 1.

    --
    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. #35
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Alright, I finally solved this for myself and anyone else who may have been baffled by QuantumPete's wizardry.

    Using:
    Code:
    #include <stdio.h>
    
    int fib (int num, char *side) {
    	int x=-1, y=-1;
    	printf("fib: %d %s\n", num, side);
    	if (num <= 2) {
    		printf("done %s\n", side);	
    		return 1;
    	}
    	x=fib(num-1,"X"); y=fib(num-2,"Y");
    	printf("x: %d y: %d %s\n", x, y, side);
    	return x+y;
    }
    
    int main (int argc, char *argv[]) {
    	printf("answer: %d\n", fib(atoi(argv[1]), "start"));
    }
    ./a.out 5

    Code:
    fib: 5 start	calculation of fib(5)
    fib: 4 X            recursion for X: fib(5-1) 
    fib: 3 X		recursion for x of X: fib(4-1)
    fib: 2 X		recursion for x of x of X: fib(3-1)
    done  X	        equals 2, return 1 for x of X.
    fib: 1 Y            y of x of X
    done  Y		...will be 1
    x: 1 y: 1 X       so x of X is 2 
    fib: 2 Y            
    done  Y		and y of X is 1
    x: 2 y: 1 X	so X will be 3
    fib: 3 Y      	recursion for Y: fib(5-2)
    fib: 2 X		recursion for x of Y: fib(3-1)	
    done X		is 2, so return 1
    fib: 1 Y		recursion for y of Y: fib(3-2)
    done Y		returns 1 also
    x: 1 y: 1 Y	so Y will be 2
    x: 3 y: 2 start
    answer: 5		okay!
    No wonder it takes so long -- it's essentially adding 1+1+1+1+1+1...
    Last edited by MK27; 10-16-2008 at 11:09 AM.

  6. #36
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    I am looking at some equations for calculating arbitrary fibonacci numbers and I am not seeing anything terribly like the one which you are using. Your equation itself is wrong. That is why your output is wrong. And as its been said several times over, iteratively calculating these numbers is not a terrible chore and it need only be done once, tabled, and used on-demand.

  7. #37
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by master5001 View Post
    I am looking at some equations for calculating arbitrary fibonacci numbers and I am not seeing anything terribly like the one which you are using. Your equation itself is wrong. That is why your output is wrong. And as its been said several times over, iteratively calculating these numbers is not a terrible chore and it need only be done once, tabled, and used on-demand.

    You're a nut. None of the output from any of these solutions was ever wrong and nobody ever claimed that either...
    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

  8. #38
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    I was talking to the original poster, and I never said I was a nut, but I am saying I am not wrong. The OP asked how come his output was wrong, and I am stating why.

  9. #39
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by master5001 View Post
    I was talking to the original poster, and I never said I was a nut, but I am saying I am not wrong. The OP asked how come his output was wrong, and I am stating why.
    All apologies. And by "nut" I meant interesting...
    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

  10. #40
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Well I am a nut. And its all good. I took out my calculator and tried some stuff with his equation by hand, and it doesn't even calculate the third number correctly

  11. #41
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,310
    I took out my calculator and tried some stuff with his equation by hand, and it doesn't even calculate the third number correctly
    Good for you. I couldn't even get it to compile since M_E is undefined for me

    That said, going by the webpage referenced, the formula is correct (though that webpage's formula is itself an approximation, not the full formula).
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #42
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,230
    Quote Originally Posted by QuantumPete View Post
    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:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  13. #43
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    #include <math.h>, laserlight. I will double check, but unless I did something else wrong, I didn't get the formula to work correctly. The point is moot though, since its not the most efficient way of solving this. Plus it would only be beneficial to use a formula like this to solve an arbitrarily high number, which cannot be done due to accuracy issues, apparently.

    [edit]Wtf... *#include <float.h> I mean[/edit]

  14. #44
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    I am still not getting this to work. I get what the derivation is saying and all, and it looks fascinating. Perhaps I am just not doing it correctly. asinh() is a bastard to do on my calc.. But still, I did it correctly -_-

  15. #45
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,310
    I will double check, but unless I did something else wrong, I didn't get the formula to work correctly.
    Perhaps you would like to try this, using just square root computation instead of a trigonometric function:
    Code:
    #include <math.h>
    #include <stdio.h>
    
    unsigned int fib(unsigned int n)
    {
        double sqrt5 = sqrt(5.0);
        double phi = (1.0 + sqrt5) / 2.0;
        return (unsigned int)((pow(phi, n) / sqrt5) + 0.5);
    }
    
    int main(void)
    {
        int x;
    
        for (x = 0; x < 48; ++x)
        {
            printf("&#37;u: %u\n", x, fib(x));
        }
    
        return 0;
    }
    Ideally, we should only compute sqrt5 and phi once, but anyway...

    The point is moot though, since its not the most efficient way of solving this.
    That depends on what factors you are considering for efficiency.

    Plus it would only be beneficial to use a formula like this to solve an arbitrarily high number, which cannot be done due to accuracy issues, apparently.
    Yes, and it is not as efficient as memoization when you want to generate all the Fibonacci numbers up to some limit, like what cph was trying to do.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Page 3 of 4 FirstFirst 1234 LastLast
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, 08:15 AM
  3. Immediate programming help! Please!
    By xMEGANx in forum C++ Programming
    Replies: 6
    Last Post: 02-20-2008, 11:52 AM
  4. Fibonacci sequence output statement
    By chocha7 in forum C++ Programming
    Replies: 10
    Last Post: 11-18-2004, 10:04 PM
  5. Fibonacci sequence
    By girliegti in forum C++ Programming
    Replies: 8
    Last Post: 09-30-2003, 10:40 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21