Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

Fibonacci number overflow in c++

I am a c++ newbie, and start learning it by learning algorithm at the same time. However, I encountered some problem when writing this algorithm — the number overflows, which is quite different to the overflow I thought. To solve the problem, I searched for a long time, but end up in no use. Here is my code:

#include <iostream>
using namespace std;

long long Fs[101];
long long F(int N) {
    if (Fs[N] != -1) {
        return Fs[N];
    }
    int res = F(N - 1) + F(N - 2);
    Fs[N] = res;
    return res;
}

void main() {
    // initialize Fs array
    for (auto& item : Fs) {
        item = -1;
    }
    Fs[0] = 0;
    Fs[1] = 1;
    cout << F(60) << endl;
    cout << endl;
    for (auto& item : Fs) {
        cout << item << endl;
    }
}

Part of the result is shown here:

165580141
267914296
433494437
701408733
1134903170
1836311903
-1323752223
512559680
-811192543

Question:
You can see that the overflow number is quite small than the minimum value of long long type. Why this happened?

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel


Appendix
I found some way to print the overflow index of unsigned type when generating fibonacci, here is the code:

#include <iostream>
#include <limits>
using namespace std;
 
#define outFibonacci(nType) { int i = 1;\
    while (i++)\
        if (Fibonacci<nType>(i+1)==Fibonacci<nType>(i+2)){\
            cout<<"F("<<i<<")\t= "<<Fibonacci<nType>(i)<<endl;\
            break;\
        }\
    cout<< "Max Num\t= " << numeric_limits<nType>::max() << endl << endl;\
    }
 
template<typename _T> _T Fibonacci(_T n){
    _T f, f1, f2;
    f = f1 = f2 = 1;
    for (auto i=3; i<=n; ++i){
        f = f1 + f2;
        if (f<f2){ // Set overflow condition
            f=-1;
            break;
        }
        f1 = f2;
        f2 = f;
    }
    return f;
}
 
int main(void)
{   
    outFibonacci(unsigned short);
    
    outFibonacci(unsigned int);
    outFibonacci(unsigned long);
    
    outFibonacci(unsigned long long);
    outFibonacci(size_t);
    
    return 0;
}

and here is my result:

F(24)   = 46368
Max Num = 65535

F(47)   = 2971215073
Max Num = 4294967295

F(47)   = 2971215073
Max Num = 4294967295

F(93)   = 12200160415121876738
Max Num = 18446744073709551615

F(93)   = 12200160415121876738
Max Num = 18446744073709551615

>Solution :

This line in your function int res = F(N – 1) + F(N – 2); makes your result an int, which is then casted to long long. so the overflow occurs here. Should be flagged by some compilers flags tho.

long long F(int N) {
    if (Fs[N] != -1) {
        return Fs[N];
    }
    // int res = F(N - 1) + F(N - 2); // HERE !
    long long res = F(N - 1) + F(N - 2);
    Fs[N] = res;
    return res;
}
Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading