Integer overflow in unsigned long long array

Question

I was trying to make cached Fibonacci sequence, but seem to be running into integer overflow (even if the data type is unsigned long long) after nth position = 247, the compiler outputs strange erroneous negative results, which I was not hoping for. Was wondering what a solution to this is, beyond n=247, and how I can increase accurate result up to essentially n= any positive integer if that possible... Thanks.

I was also trying to set the array capacity to the nthPos but it only accepts constant integers (not even constant variables!), was wondering what a way around this is...

#include <iostream>
#include <cstdlib>
#include <string>
#include <time.h>
#include <cmath>

using namespace std;


int FibonacciRecursiveFunc(int nthPos) {
    unsigned long long firstNum = 0; unsigned long long secondNum = 1;
    unsigned long long PastFibonacciCache[300] = { firstNum,secondNum };

    if (find(PastFibonacciCache, end(PastFibonacciCache), nthPos-1) != end(PastFibonacciCache)) {
        return nthPos - 1;
    }
    else {
        for (int i = 2; i < nthPos; i++) {
            PastFibonacciCache[i] = PastFibonacciCache[i - 1] + PastFibonacciCache[i - 2];
            if (i > 300) {
                unsigned long long SecondLastTerm = PastFibonacciCache[299];
                unsigned long long lastTerm = PastFibonacciCache[300];
                PastFibonacciCache[300] = {}; PastFibonacciCache[0] = SecondLastTerm; PastFibonacciCache[1] = lastTerm;
                i - 300;  nthPos - 300;
            }
        }
        return PastFibonacciCache[nthPos%300-1];
    }
}

int main() {
    string inputVAL; int nthPos;
    cout << "Greetings, enter a valid n value | n >= 1\n" << "type exit, quit or break to quit program \n\n" << endl << " ->";
    getline(cin, inputVAL);
    string exit_Methods[3] = { "exit", "quit", "break" };
    while (find(exit_Methods, end(exit_Methods), inputVAL) == end(exit_Methods)) {
        bool exception_caught = true;

        try {
            nthPos = stoi(inputVAL);

            exception_caught = false;
        }
        catch (invalid_argument) {
            cerr << "invalid argument" << endl;
        }
        catch (out_of_range) {
            cerr << "number is too big" << endl;
        }
        catch (exception) {
            cerr << "something went horribly wrong :v" << endl;
        }
        if (!exception_caught) {

            //begintimer for calculation speed
            time_t begin, end;
            time(&begin);
            if (nthPos >= 1) {
                cout << FibonacciRecursiveFunc(nthPos) << endl;
            }
            else {
                cout << "ERR" << endl;
            }


            // measure elapsed time
            time(&end);
            time_t elapsed = end - begin;

            printf("Time measured: %ld seconds.\n\n", elapsed);
        }
        cout << "enter a valid n value | n >= 0 ->";
        getline(cin, inputVAL);
    }
}

you cannot compute the factorial of any integer, because the factorial of the largest integer is larger than the largest integer. No matter what type you choose there is a limit somewhere — 463035818_is_not_an_ai, Feb 01 '22 at 19:59
What's the value for 245 and 246 (or 247 if that's still valid)? How does that compare with 2^64 - 1? If `unsigned long long` is no longer big enough to hold the values, you will need to use (and possibly implement) some sort of multi-precision (integer) arithmetic. There are libraries available to do that — for example, GMP from https://gmplib.org/ (see also MPC from https://www.multiprecision.org/mpc/ and MPFR from https://www.mpfr.org/ — all of these are used by GCC). — Jonathan Leffler, Feb 01 '22 at 19:59
`unsigned long long PastFibonacciCache[300]` => 300 is the SIZE of this array. It is not a valid INDEX, the highest legal index is 299. But you access 300 in several places. — Ben Voigt, Feb 01 '22 at 20:10
@463035818_is_not_a_number: Fibonacci sequence doesn't grow anywhere near as fast as factorial, however the same argument applies. — Ben Voigt, Feb 01 '22 at 20:11
actually the limit is 47... which is kind of a bummer because I hoping for even more :/ — Luv Rathod, Feb 01 '22 at 20:19
@LuvRathod [See this answer](https://stackoverflow.com/questions/67630357/c-factorial-of-number-100/67630658#67630658). It uses factorial, but you get the idea. Also, using Binet's formula, you can get the nth Fibonacci formula using a closed formula without iterating. But you would have to store the values in a floating point variables, not integers. — PaulMcKenzie, Feb 01 '22 at 20:28

score 0 · Answer 1 · answered Feb 01 '22 at 22:01

int FibonacciRecursiveFunc(int nthPos) {

The return type of your function is int. The maximum value representable by int varies between systems, but let's assume that it is 2147483647 on your system.

The 247th fibonacci number is 1152058411884454788302593034206568772452674037325128. This number is greater than 2147483647. You cannot represent so large number with an int.

was wondering what a way around this is

You cannot use fundamental types. You can use arbitrary precision arithmetic.

Integer overflow in unsigned long long array

1 Answers1