Fibonacci mod number c++

Question

I have the following problem: I should compute a fibonacci number mod another given number. I know about the Pisano period and i am trying to implement it here. This is the code:

#include <iostream>
#include <cstdlib>
long long get_fibonaccihuge(long long n, long long m) {
    long long period = 0;
    if (m % 2 == 0) {
        if(m / 2 > 1)
        period = 8 * (m / 2) + 4;
        else
        period = 3; 
    }
    else{
        if(((m + 1) / 2) > 1)
        period = 4 * ((m + 1) / 2);
        else
        period = 1;
    }

    long long final_period = n % period;



    long long array_fib[final_period];
    array_fib[0] = 1;
    array_fib[1] = 1;
    for (long long i = 2; i < final_period; ++i) {
        array_fib[i] = (array_fib[i-1] + array_fib[i-2]) % m;
    }

    return array_fib[final_period - 1];
}

int main() {
    long long n, m;
    std::cin >> n >> m;
    std::cout << get_fibonaccihuge(n, m) << '\n';
}

It works well for small tests but the problem is that it fails the following test:

281621358815590 30524

I do not know why. Any suggestions about the algorithm, I referred to this page. When I was constructing it.

The error which I receive is: wrong result.

Expected: 11963 My result: 28651

Answer 1

Unless your task is to use Pisano periods, I would suggest you to use a more common known way to calculate n-th Fibonacci number in log2(n) steps (by computing powers of 2*2 matrix: https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form).

There are two reasons:

1. It's a simpler algorithm and that means that it will be easier to debug the program
2. For the numbers you mentioned as an example it should be faster (log2(n) is somewhere about 50 and m/2 is significantly more).