Thread: Fibonacci

  1. #1
    Registered User
    Join Date
    Jun 2010
    Posts
    6

    Unhappy Fibonacci

    Hi everyone! This is my first post, and I'm quite a noob at C. I have a homework assingment I have to do, and I've thought on it a lot, but it's confusing me. Here's the exact problem given:

    The Fibonacci number sequence is commonly used in mathematics and is commonly found in nature. Request that the user enter a number between 1 and 100 and have the program respond back which Fibonacci number corresponds. You must use loops and functions to solve this problem. Note, the formula can be found here:

    Fibonacci number - Wikipedia, the free encyclopedia

    For example the sequence is:

    1.1
    2.2
    3.3
    4.5
    5.8
    6.13... etc.
    For example:

    >>>Which Fibonacci number would you like to see?

    >>>Please enter a number: 7

    >>>Fibonacci number 7 is 21.



    I'm guessing I just start it off requesting the user for input and then the number they input be plugged into the formula F(n)=F(n-1)+F(n-2)=F(0)+F(1), but with this if I entered in 10, i'd have to know the Fibonacci numbers for 9 and 8? and it'd be that pattern all way up to 100? Really don't know how I'd do that =(. Can anyone help me here or give me an similar example of some sort?

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    So can you write a loop which generates the Fibonacci sequence?

    Like the first 10 numbers are ... kind of thing?

    Instead of 10, use the number that was input.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Nov 2009
    Location
    Italy
    Posts
    65
    Just use a recursive function

  4. #4
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Actually recursion is much slower than iteration for this. It's certainly shorter but not efficient.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  5. #5
    Novice
    Join Date
    Jul 2009
    Posts
    568
    It would appear that none of the standard datatypes have enough space/precision to store the largest numbers of first 100 Fibonacci numbers. E.g. 573`147`844`013`817`084`101 is the 100th Fibonacci number, but on my system, stored in a long double it is 573`147`844`013`817`084`096.

    Suggestions?

  6. #6
    Registered User
    Join Date
    May 2010
    Location
    Naypyidaw
    Posts
    1,314
    Use multiple precision arithmetic library like gmp.
    or just use bc calculator if you don't need it to be done in C.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by rob90 View Post
    Just use a recursive function
    If you're suggesting what I think you're suggesting, then I hope that was a joke.
    The naieve recursive imlementation of it takes literally hours to calculate a mere fib(50). Reference
    Besides, it says you must use loops.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    Registered User
    Join Date
    Jun 2010
    Posts
    6
    I got it working with a recursive function, but uhm yeah...took forever, so I'll try to do it with the other thing.

  9. #9
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    You can do addition yourself manually using a large array of chars, e.g. Use the digits '0' to '9', do addition digit by digit with carry over the way you might do it by hand. It's not too difficult, I implemented fibonacci in 56 lines using this method, and it only takes 100 ms to calculate the 1000th number.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  10. #10
    Registered User
    Join Date
    Jun 2010
    Posts
    6
    Quote Originally Posted by iMalc View Post
    If you're suggesting what I think you're suggesting, then I hope that was a joke.
    The naieve recursive imlementation of it takes literally hours to calculate a mere fib(50). Reference
    Besides, it says you must use loops.
    I replaced what I had with the iteration function that was on your link. I'm getting an error that says: 'test.c: In function Fibonacci:' 'test.c:23: error: for loop initial declaration used outside C99 mode'

    Code:
    
    
    #include <stdio.h>
    
    unsigned int Fibonacci (unsigned int n);
    
    int main ()
    {
    
    long result;
    long number;
    
    
    printf("Enter an int: ");
    scanf("%ld", &number);
    result=Fibonacci(number);
    printf("Fibonacci(%ld)=%ld/n",number,result);
    return 0;
    }
    
    unsigned int Fibonacci (unsigned int n)
    {
        int previous = -1;
        int result =1;
        for (unsigned int i= 0; i <= n; ++i)
        {
         int const sum=result + previous;
         previous = result;
         result = sum;
    }
    return result;

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    The solution is simple: do not declare variables in the initial statement of a for loop, i.e., write:
    Code:
    unsigned int i;
    for (i = 0; i <= n; ++i)
    instead of:
    Code:
    for (unsigned int i= 0; i <= n; ++i)
    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

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    You're missing the closing curly-bracket of the for-loop as well.
    Otherwise it's looking alright.
    What do you get if you enter 100?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  13. #13
    Registered User
    Join Date
    Jun 2010
    Posts
    6
    dang it. I feel like such a noob

    Code:
    #include <stdio.h>
    
    unsigned int Fibonacci (unsigned int n);
    
    int main ()
    {
    
    long result;
    long number;
    
    
    printf("Enter an int: ");
    scanf("%ld", &number);
    result=Fibonacci(number);
    printf("Fibonacci(%ld)=%ld/n",number,result);
    return 0;
    }
    
    unsigned int Fibonacci (unsigned int n)
    {
    
        int previous= -1;
        int result =1;
        unsigned int i;
        for (unsigned int i=0; i <=n; ++i)
        {
         int const sum=result + previous;
         previous= result;
         result = sum;
      }
    }
     return result;
    Now I'm getting...

    test.c: In function âFibonacciâ:
    test.c:25: error: redeclaration of âiâ with no linkage
    test.c:24: error: previous declaration of âiâ was here
    test.c:25: error: âforâ loop initial declaration used outside C99 mode
    cc1: warnings being treated as errors
    test.c:31: error: control reaches end of non-void function
    test.c: At top level:
    test.c:32: error: expected identifier or â(â before âreturnâ

  14. #14
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Also, note that you are reading the input n in a long and passing it to a function that takes an unsigned int as a parameter. Do NOT mix up signed and unsigned variables.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  15. #15
    Registered User
    Join Date
    Nov 2008
    Location
    China
    Posts
    17
    My English is poor, so I post code directly

    Code:
    #include <stdio.h>  
    
    int main(void)  
    
    {  
    
        int F[46];  
    
        int i;  
    
        F[0] = 0; F[1] = 1;  
    
        for (i = 2; i <= N; i++)  
    
    	F[i] = F[i-1] + F[i-2];  
    
        printf("%d\n", F[8]);  
    
        return 0;  
    
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 12-25-2009, 01:22 AM
  2. fibonacci prime
    By dbzx in forum C Programming
    Replies: 5
    Last Post: 04-17-2009, 11:13 AM
  3. fibonacci using recursion?
    By n3cr0_l0rd in forum C Programming
    Replies: 12
    Last Post: 02-25-2009, 08:49 AM
  4. Recursive Fibonacci, some help needed
    By cwafavre in forum C Programming
    Replies: 8
    Last Post: 11-04-2007, 02:20 PM
  5. void fibonacci() - Is This Possible?
    By Not Yet in forum C++ Programming
    Replies: 3
    Last Post: 11-25-2002, 10:24 PM