Home > Mobile >  Fibonacci number overflow in c
Fibonacci number overflow in c

Time:05-18

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?


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

CodePudding user response:

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;
}
  • Related