Incorrect Fibonacci Modulo Results

[StMick]

Im trying to write a program that reads in a Fibonacci number (n) and a modulo number(m) and then returns that Fibonacci numbers modulus (if the numbers are within the constraints defined in the constraints function). However there are 2 issues here.

1. The program is too slow
2. The answer provided on very large numbers is incorrect.

Any suggestions on how to speed up this program or in how to solve this with a different algorithm would be greatly appreciated!

using namespace std;

bool constraints(long long unsigned int x, long long unsigned int y)
{
   long long unsigned int maxi_x = pow(10,18);
   long long unsigned int maxi_y = pow(10,5);
   long long unsigned int mini_x = 1;
   long long unsigned int mini_y = 2;

   if(x<mini_x || x>maxi_x)             // To test if x is above the max or lower than the floor.
   {
       return false;
   }
   if (y<mini_y || y>maxi_y)            // To test if y is above the max or lower than the floor.
   {
       return false;
   }
    return true;                        // Else x & y are within the constraints.

}
int main()
{
    long long unsigned int n,m;
    long long unsigned int answer = 0;
    long long unsigned int i;
    bool flag = true;
    cin >> n >> m;                          // read in Fibonacci number (n) and the modulo number (m).

    flag = constraints(n,m);                // To test if the numbers meet the specified constraints.
    if (flag == false)
    {
        cout << "Flag is False" << endl;
        return 0;                           // If numbers outside constraints end the program.
    }

    long long unsigned int arr[n];
    arr[0] = 0;
    arr[1] = 1;

    for (i = 2; i<(n+2); i++)
    {
        arr[i] = ((arr[i-1] + arr[i-2])%m);     // Creates each Fibonacci number and inserts the modulus of it into the array.
    }

    answer = arr[n];
    cout << answer;                             // prints the answer to the screen.

    return 0;
}

[tpb]

You are using a variable-length array, which is not allowed in standard C++. Also, you go outside the bounds of that array.

But you don't need to keep an array of every single fibonacci number that you've calculated. Just the last two or three.

Your constraints don't make sense to me. There's no way you're going to calculate the billion-billionth fibonacci number, or even just it's last digit unless there's a formula for that.

You need to describe exactly what you are trying to do.

[jonnin]

1) lookup the golden ratio. After the first few values, you can directly compute them and don't need a loop or anything. Roundoff messes up the first few, is all.

2) this is like factorials. They overflow very, very quickly, even with 64 bit ints you run dry fairly quickly. You need a large integer class after a bit.