How to store output of very large Fibonacci number

问题:

I am making a program for nth Fibonacci number. I made the following program using recursion and memoization. The main problem is that the value of n can go up to 10000 which means that the Fibonacci number of 10000 would be more than 2000 digit long.

With a little bit of googling, I found that i could use arrays and store every digit of the solution in an element of the array but I am still not able to figure out how to implement this approach with my program.

#include<iostream>

using namespace std;

long long int memo[101000];
long long int n;
long long int fib(long long int n)
{
    if(n==1 || n==2)
        return 1;
    if(memo[n]!=0)
        return memo[n];
    return memo[n] = fib(n-1)  + fib(n-2);
}
int main()
{
    cin>>n;
    long long int ans = fib(n);
    cout<<ans;
}

How do I implement that approach or if there is another method that can be used to achieve such large values?

回答1:

One thing that I think should be pointed out is there's other ways to implement fib that are much easier for something like C++ to compute

consider the following pseudo code

function fib (n) {
  let a = 0, b = 1, _;
  while (n > 0) {
    _ = a;
    a = b;
    b = b + _;
    n = n - 1;
  }
  return a;
}

This doesn't require memoisation and you don't have to be concerned about blowing up your stack with too many recursive calls. Recursion is a really powerful looping construct but it's one of those fubu things that's best left to langs like Lisp, Scheme, Kotlin, Lua (and a few others) that support it so elegantly.

That's not to say tail call elimination is impossible in C++, but unless you're doing something to optimise/compile for it explicitly, I'm doubtful that whatever compiler you're using would support it by default.

As for computing the exceptionally large numbers, you'll have to either get creative doing adding The Hard Way or rely upon an arbitrary precision arithmetic library like GMP. I'm sure there's other libs for this too.

---

Adding The Hard Way™

Remember how you used to add big numbers when you were a little tater tot, fresh off the aluminum foil?

5-year-old math

  1259601512351095520986368
+   50695640938240596831104
---------------------------
                          ?

Well you gotta add each column, right to left. And when a column overflows into the double digits, remember to carry that 1 over to the next column.

                 ... <-001
  1259601512351095520986368
+   50695640938240596831104
---------------------------
                  ... <-472

The 10,000th fibonacci number is thousands of digits long, so there's no way that's going to fit in any integer C++ provides out of the box. So without relying upon a library, you could use a string or an array of single-digit numbers. To output the final number, you'll have to convert it to a string tho.

(woflram alpha: fibonacci 10000)

Doing it this way, you'll perform a couple million single-digit additions; it might take a while, but it should be a breeze for any modern computer to handle. Time to get to work !

---

Here's an example in of a Bignum module in JavaScript

const Bignum =
  { fromInt: (n = 0) =>
      n < 10
        ? [ n ]
        : [ n % 10, ...Bignum.fromInt (n / 10 >> 0) ]

  , fromString: (s = "0") =>
      Array.from (s, Number) .reverse ()

  , toString: (b) =>
      b .reverse () .join ("")  

  , add: (b1, b2) =>
    {
      const len = Math.max (b1.length, b2.length)
      let answer = []
      let carry = 0
      for (let i = 0; i < len; i = i + 1) {
        const x = b1[i] || 0
        const y = b2[i] || 0
        const sum = x + y + carry
        answer.push (sum % 10)
        carry = sum / 10 >> 0
      }
      if (carry > 0) answer.push (carry)
      return answer
    }
  }

We can verify that the Wolfram Alpha answer above is correct

const { fromInt, toString, add } =
  Bignum

const bigfib = (n = 0) =>
{
  let a = fromInt (0)
  let b = fromInt (1)
  let _
  while (n > 0) {
    _ = a
    a = b
    b = add (b, _)
    n = n - 1
  }
  return toString (a)
}

bigfib (10000)
// "336447 ... 366875"

Expand the program below to run it in your browser

const Bignum =
  { fromInt: (n = 0) =>
      n < 10
        ? [ n ]
        : [ n % 10, ...Bignum.fromInt (n / 10 >> 0) ]
        
  , fromString: (s = "0") =>
      Array.from (s) .reverse ()
      
  , toString: (b) =>
      b .reverse () .join ("")  
      
  , add: (b1, b2) =>
    {
      const len = Math.max (b1.length, b2.length)
      let answer = []
      let carry = 0
      for (let i = 0; i < len; i = i + 1) {
        const x = b1[i] || 0
        const y = b2[i] || 0
        const sum = x + y + carry
        answer.push (sum % 10)
        carry = sum / 10 >> 0
      }
      if (carry > 0) answer.push (carry)
      return answer
    }
  }
  
const { fromInt, toString, add } =
  Bignum

const bigfib = (n = 0) =>
{
  let a = fromInt (0)
  let b = fromInt (1)
  let _
  while (n > 0) {
    _ = a
    a = b
    b = add (b, _)
    n = n - 1
  }
  return toString (a)
}

console.log (bigfib (10000))

回答2:

Try not to use recursion for a simple problem like fibonacci. And if you'll only use it once, don't use an array to store all results. An array of 2 elements containing the 2 previous fibonacci numbers will be enough. In each step, you then only have to sum up those 2 numbers. How can you save 2 consecutive fibonacci numbers? Well, you know that when you have 2 consecutive integers one is even and one is odd. So you can use that property to know where to get/place a fibonacci number: for fib(i), if i is even (i%2 is 0) place it in the first element of the array (index 0), else (i%2 is then 1) place it in the second element(index 1). Why can you just place it there? Well when you're calculating fib(i), the value that is on the place fib(i) should go is fib(i-2) (because (i-2)%2 is the same as i%2). But you won't need fib(i-2) any more: fib(i+1) only needs fib(i-1)(that's still in the array) and fib(i)(that just got inserted in the array).
So you could replace the recursion calls with a for loop like this:

int fibonacci(int n){
    if( n <= 0){
        return 0;
    }

    int previous[] = {0, 1};      // start with fib(0) and fib(1)
    for(int i = 2; i <= n; ++i){
        // modulo can be implemented with bit operations(much faster): i % 2 = i & 1
        previous[i&1] += previous[(i-1)&1];   //shorter way to say: previous[i&1] = previous[i&1] + previous[(i-1)&1]
    }
    //Result is in previous[n&1]
    return previous[n&1];
}

Recursion is actually discommanded while programming because of the time(function calls) and ressources(stack) it consumes. So each time you use recursion, try to replace it with a loop and a stack with simple pop/push operations if needed to save the "current position" (in c++ one can use a vector). In the case of the fibonacci, the stack isn't even needed but if you are iterating over a tree datastructure for example you'll need a stack (depends on the implementation though). As I was looking for my solution, I saw @naomik provided a solution with the while loop. That one is fine too, but I prefer the array with the modulo operation (a bit shorter).

Now concerning the problem of the size long long int has, it can be solved by using external libraries that implement operations for big numbers (like the GMP library or Boost.multiprecision). But you could also create your own version of a BigInteger-like class from Java and implement the basic operations like the one I have. I've only implemented the addition in my example (try to implement the others they are quite similar).

The main idea is simple, a BigInt represents a big decimal number by cutting its little endian representation into pieces (I'll explain why little endian at the end). The length of those pieces depends on the base you choose. If you want to work with decimal representations, it will only work if your base is a power of 10: if you choose 10 as base each piece will represent one digit, if you choose 100 (= 10^2) as base each piece will represent two consecutive digits starting from the end(see little endian), if you choose 1000 as base (10^3) each piece will represent three consecutive digits, ... and so on. Let's say that you have base 100, 12765 will then be [65, 27, 1], 1789 will be [89, 17], 505 will be [5, 5] (= [05,5]), ... with base 1000: 12765 would be [765, 12], 1789 would be [789, 1], 505 would be [505]. It's not the most efficient, but it is the most intuitive (I think ...)
The addition is then a bit like the addition on paper we learned at school:

1. begin with the lowest piece of the BigInt
2. add it with the corresponding piece of the other one
3. the lowest piece of that sum(= the sum modulus the base) becomes the corresponding piece of the final result
4. the "bigger" pieces of that sum will be added ("carried") to the sum of the following pieces
5. go to step 2 with next piece
6. if no piece left, add the carry and the remaining bigger pieces of the other BigInt (if it has pieces left)

For example:

9542 + 1097855 = [42, 95] + [55, 78, 09, 1]
    lowest piece = 42 and 55 --> 42 + 55 = 97 = [97]
                ---> lowest piece of result = 97 (no carry, carry = 0)
    2nd piece = 95 and 78 --> (95+78) + 0 = 173 = [73, 1]
                ---> 2nd piece of final result = 73
                ---> remaining: [1] = 1 = carry (will be added to sum of following pieces)
    no piece left in first `BigInt`! 
     --> add carry ( [1] ) and  remaining pieces from second `BigInt`( [9, 1] )  to final result 
     --> first additional piece: 9 + 1 = 10 = [10]  (no carry) 
     --> second additional piece: 1 + 0 = 1 = [1]   (no carry)
==> 9542 + 1 097 855 = [42, 95] + [55, 78, 09, 1] = [97, 73, 10, 1] = 1 107 397

Here is a demo where I used the class above to calculate the fibonacci of 10000 (result is too big to copy here)

Good luck!

PS: Why little endian? For the ease of the implementation: it allows to use push_back when adding digits and iteration while implementing the operations will start from the first piece instead of the last piece in the array.