-1

How can one calculate nth Fibonacci number in C/C++? The Fibonacci number can contain upto 1000 digits. I can generate numbers upto 2^64 (unsigned long long). Since that is the limit of numbers, so I am guessing there has to be some other way of doing it - which I do not know of.

EDIT:

Also, it has to be done without using any external libraries.

Born Again
  • 2,139
  • 4
  • 25
  • 27
  • 3
    What have you already tried? – Seg Fault Oct 18 '13 at 12:44
  • 1
    Use a BigInt library? See e.g. http://stackoverflow.com/questions/1055661/bigint-bigbit-library – Paul R Oct 18 '13 at 12:45
  • 1
    What problems have you run up against? – John Oct 18 '13 at 12:45
  • 2
    It's not a good idea to look for solution for [Project Euler problems](http://projecteuler.net/problem=25). It's against their policy. – Yu Hao Oct 18 '13 at 12:48
  • See this too: http://stackoverflow.com/questions/4907806/class-for-calculating-arbitrarily-large-numbers – Cretzu Oct 18 '13 at 12:50
  • @YuHao I do not solve Project Euler problems. It is a question I found somewhere else. Anyway, the question you have mentioned is not exactly the same. – Born Again Oct 18 '13 at 12:51
  • Use the awesome power of mathematics! Seriously, how would you do it using a pencil and a piece of paper? – Skizz Oct 18 '13 at 13:02
  • @YuHao I *thought* it looked familiar ... – John Oct 18 '13 at 13:09
  • http://www.youtube.com/watch?feature=player_detailpage&list=PL37ZVnwpeshF7AHpbZt33aW0brYJyNftx&v=j_EfPW4G-L0 - awesome talk by Angus Croll from twitter on coding in literary styles, using javascript to do Fibonacci in different ways. – Dimitar Christoff Oct 18 '13 at 15:33

2 Answers2

3

I'll give a few hints since you haven't indicated that you've started yet.

A thousand digits is a lot. More than any built-in numeric type in C or C++ can hold.

One way to get around it is to use an arbitrary-precision math library. This will have constructs that will give you basically as many digits as you want in your numbers.

Another way is to roll your own cache-and-carry:

unsigned short int term1[1024];  // 1024 digits from 0-9
unsigned short int term2[1024];  // and another

unsigned short int sum[1024];    // the sum

addBigNumbers(&term1, &term2, &sum);   // exercise for the reader

I'd expect the algorithm for addBigNumbers to go something like this:

Start at the ones digit (index 0)
Add term1[0] and term2[0]
Replace sum[0] with the right digit of term1[0] + term2[0] (which is ... ?)
Keep track of the carry (how?) and use it in the next iteration (how?)
Repeat for each digit

Now, since you're calculating a Fibonacci sequence, you'll be able to re-use these big numbers to get to the next term in the sequence. You might find that it's faster not to copy them around but to just change which ones are the terms and which one is the sum on your repeated calls to addBigNumbers.

John
  • 15,990
  • 10
  • 70
  • 110
  • So after making this add function, I apply the basic Fibonacci formula: a=1, b=1; a+=b; b+=a; ? – Born Again Oct 18 '13 at 12:59
  • More like: a = 1, b = 1, c = a + b, a' = b + c, b' = c + a', etc. – John Oct 18 '13 at 13:11
  • @John: unsigned int, to store a single digit in? `char` is more appropriate, although I would probably try and halve even that ;-) – Jongware Oct 18 '13 at 13:39
  • @Jongware Absolutely correct, and if I were implementing it, I'd do that, too. If C or C++ had a type called `byte` I would have used that in a heartbeat. But for teaching purposes, I felt that using `unsigned short int` was clearer than needing to explain: "You're actually storing the `char` whose value is 0, not the character '0' ... but you *can* store the characters if you want, you just have to remember to subtract 48 from the ASCII value to get the actual digit ..." See what I mean? :) Yeah, I'm wasting space, but I'll let the OP optimize if s/he needs. :) – John Oct 18 '13 at 13:52
1

You could try using GMP for arbitrarily large integers.

Paul Evans
  • 27,315
  • 3
  • 37
  • 54