6

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

StefanL19
  • 1,476
  • 2
  • 14
  • 29
  • 2
    `long long array_fib[final_period]` uses a g++ language extension (namely C99 variadiac arrays). In standard C++ use `std::vector array_fib(final_period)`. This is not your logic problem but I thought I should mention it: better post standard code that everyone can try. – Cheers and hth. - Alf Apr 17 '16 at 10:16
  • I know that the mistake should be at the moment when I obtain the number mod period, – StefanL19 Apr 17 '16 at 10:26
  • What fails? Run time error? Wrong result? What is your output? – Ely Apr 17 '16 at 10:39
  • 2
    What is your result? What is the expected result? – Ely Apr 17 '16 at 10:41
  • Add that to your question, I'd suggest. – Ely Apr 17 '16 at 10:42
  • You confirm that `m` is the Fibonacci index and `n` is the Fibonacci number? If so, then that's wrong I think. – Ely Apr 17 '16 at 11:17
  • Probably relevant: https://www.reddit.com/r/puremathematics/comments/yc6hv/i_have_solved_the_pisano_periods_a_250_year_old/ – Cheers and hth. - Alf Apr 17 '16 at 11:55

1 Answers1

2

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).
maxim1000
  • 6,297
  • 1
  • 23
  • 19