Thread: large Fibonacci numbers

  1. #1
    Registered User
    Join Date
    Sep 2004
    Posts
    99

    large Fibonacci numbers

    I'm trying to calculate the largest Fib. number less than 100 digits long using the general formula: F(n) = F(n-1)+F(n-2). Need to store it in an array one digit per cell. I checked through the search option and I found one really relevant post. But this post is talking about a large number read from a file... I need to calculate it! I'm trying to gather my thoughts first, and my question is whether to conduct the calculation using digits as strings, just like I would read it from a file??? I am kind of lost how to start. Any hints how to start thinking about it?
    Thanks.

  2. #2
    Registered Luser cwr's Avatar
    Join Date
    Jul 2005
    Location
    Sydney, Australia
    Posts
    869
    Well, a quick calculation yields 83108245990870293529395578470112099370436902820065 1613859972830080739980541065544674812034151699525.


    Step 1: Make a char or int array with 100 elements where each element is a digit, initialise it to one. eg. a[99] = 1;

    Step 2: Make a second char or int array with 100 elements where each element is a digit, initialise it to one. eg. b[99] = 1;

    Step 3: Make a third char or int array (c), and add a to b using manual arithmetic you learned in elementary school and store it in c.

    Step 4: assign (copy) b to a, then assign c to b.

    Step 5: go back to step 3 the desired number of times.

  3. #3
    Registered User
    Join Date
    Sep 2004
    Posts
    99
    Oh, you mean like I would be adding two binary numbers with carry-on, but in the decimal system? OK, thanks, that's what was missing... So simple. Thanks.

  4. #4
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Or, best of all, use this:
    Code:
    struct digit {
        unsigned n : 10;  /* 1024 combinations */
    };
    And use n to hold 3 digits.
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. a very large interval of rundom numbers
    By molistok in forum C++ Programming
    Replies: 19
    Last Post: 08-03-2006, 03:58 PM
  2. large numbers
    By Alextheking in forum C++ Programming
    Replies: 13
    Last Post: 01-09-2004, 03:51 PM
  3. How to use "switch" to perform large numbers cases?
    By megablue in forum C Programming
    Replies: 4
    Last Post: 07-09-2003, 10:51 AM
  4. FIBONACCI NUMBERS, please help!
    By JamesAnthony23 in forum C Programming
    Replies: 5
    Last Post: 09-26-2002, 03:39 PM
  5. A (complex) question on numbers
    By Unregistered in forum C++ Programming
    Replies: 8
    Last Post: 02-03-2002, 06:38 PM