0

I used memoization to reduce the time took to complete recursive fibonacci.

But problem is that it cause integer overflow so the numbers are not complted after 50thish number.

so how can i prevent integer overflow both in recursive and iterative?

i have heard that operator overload can solve it..? but i have no clue how to do it.

int recursiveFib(int n) {
if (n <= 1)
    return n;
else if (memo[n]!=0) 
    return memo[n];
else 
    return memo[n] = recursiveFib(n - 1) + recursiveFib(n - 2);
}

int iterativeFib(int n) {
int x = 0, y = 1, z = 0;
for (int j = 0; j < n; j++) {
    z = x + y;
    x = y;
    y = z;
}
return x;
}

int main() {
for (int n=0; n<=200; n+=10){
    cout << "when n equals to " << n << ", Recursive Fibonacci : \n";
    for (int i = 0; i <= n; i++) {
        cout << recursiveFib(i)<<" ";
}

for (int n = 0; n <= 200; n += 10) {
    cout << "when n equals to " << n << ", Iterative Fibonacci : \n";
    for (int i = 0; i <= n; i++) {
        cout << iterativeFib(i) << " ";
}

}

The result should be printing fibonacci with every increment of n+10, both recursive and iterative in 30 minutes.

Jihoon Kim
  • 1
  • 2
  • 3
    The 200th fibonacci number is 453973694165307953197296969697410619233826, around 2^138. The largest number that the C++ standard library provides is a uint64_t, or 2^64. If you want to handle larger numbers, you need an arbitrary precision library such as libgmp. – Botje Sep 06 '19 at 07:33
  • 3
    FYI, since the only operation you use is addition, it's very easy to implement large numbers yourself (as `vector`). No need to reinvent the wheel, but, 1) it may be a useful experience; 2) if it's an assignment, implementing large numbers may be a part of it. –  Sep 06 '19 at 07:42

3 Answers3

1

The 200th Fibonacci number (and even the 50th) is larger that 2^32 (the int limit). I suggest you to use unsigned long long instead of int, or even create a big integer type using arrays , like here.

1

Before you adding up the two numbers (in iterative x, y and in recursive the method's return values) which should be checked, whether the addition may cause integer overflow or not. For more info kindly check this post. It may helps you to figure it out.

Hari Bharathi
  • 431
  • 5
  • 8
0
#include<boost/multiprecision/cpp_int.hpp>

using namespace boost:: multiprecision;

 // just add these two lines , now you can use big int type of size 2^1024

//Declaration as same as normal int

int1024_t  X=0; // can holds values upto 2^1024
RAHUL
  • 54
  • 5