Recursive Fibonacci with integer overflow

Question

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.

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
– Botje, Commented Sep 6, 2019 at 7:33
FYI, since the only operation you use is addition, it's very easy to implement large numbers yourself (as vector<int>). 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. — user2956272
– user2956272, Commented Sep 6, 2019 at 7:42

user10242112 · Accepted Answer · 2019-09-06 07:37:32Z

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.

answered Sep 6, 2019 at 7:37

user10242112

Sign up to request clarification or add additional context in comments.

1 Comment

gcasar Over a year ago

20th or 200th is a big difference

Hari Bharathi · Accepted Answer · 2019-09-06 12:29:12Z

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.

answered Sep 6, 2019 at 12:29

Hari Bharathi

4515 silver badges8 bronze badges

Comments

RAHUL · Accepted Answer · 2019-09-08 03:17:43Z

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

answered Sep 8, 2019 at 3:17

RAHUL

545 bronze badges

Collectives™ on Stack Overflow

Recursive Fibonacci with integer overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related