Calculating mod m for large Fibonacci numbers

Question

I am getting two warning (narrowing conversion && control may reach end of non-void function) with the following code. The code compiles however, when I run it it gives this message : Process finished with exit code 139 (interrupted by signal 11: SIGSEGV)

The code is compiled using CLion on Ubuntu

// calculate F(n) mod m   

#include <iostream>
#include <cmath>

long long Fiobonacci(long long n) { // Fast calculation of Fibonacci number using 'fast doubling'

    if (n == 0)
        return 0;
    else if (n % 2 == 0)
        return Fiobonacci(n / 2) * (2 * Fiobonacci(n / 2 + 1) - Fiobonacci(n / 2));
    else
        return std::pow(Fiobonacci((n + 1) / 2), 2) + std::pow(Fiobonacci((n - 1) / 2), 2);
}

long long GetPissanoPeriod(long long m){
    for (long long i = 0; i <= 6 * m ; ++i){
        if (Fiobonacci(i) % m == 0){ // if an element is zero it might be followed by a 1
            if(Fiobonacci(i+1) % m == 1)
                return i+1;
        }
    }
}

int main() {
    long long n, m;
    std::cin >> n >> m;
    long long period = GetPissanoPeriod(m);
    long long res = Fiobonacci(n % period) % m;
    std::cout << res << 'n';
}

You realize that if `m` is a prime, you can do all the math in Zm (aka integers mod m) and get the same result. If `m` isn't prime, I think you could decompose it into primes and use the Chinese Remainder Theorem to get the result after doing the calculation in each Zp. — Omnifarious, Jun 24 '19 at 02:20
@RezaAfra `return std::pow(Fiobonacci((n + 1) / 2), 2)` -- [Do not use pow() for integer exponentiation](https://stackoverflow.com/questions/25678481/why-does-pown-2-return-24-when-n-5-with-my-compiler-and-os) — PaulMcKenzie, Jun 24 '19 at 03:14
In addition, you could take advantage of [memoization](https://en.wikipedia.org/wiki/Memoization), instead of having to recompute `Fibonacci` for the same inputs. Storing the precomputed values of `Fibonacci(n)` in a table, and then use that as the cache would probably speed up this code. — PaulMcKenzie, Jun 24 '19 at 03:17
I should've seen that! *slaps forehead* Yeah, in general, if you're doing math with integers and you need to `#include $` for something, you're probably doing something wrong. Almost everything in ` ` is for `float` or `double`.$ — Omnifarious, Jun 24 '19 at 03:17
The compile errors are straight-forward and the messages should tell you where they occur. (Well, it is kind of obvious that `GetPissanoPeriod` is the function that can fail to return a value, as there is no `return` after the loop.) As for your crash, try stepping through your code with a debugger, which should reveal the infinite recursion that occurs. — JaMiT, Jun 24 '19 at 03:45

Christina Jacob · Answer 1 · 2019-06-25T03:53:54.430

See the modified code below.

 #include <iostream>
 #include <cmath>
 using namespace std;
 long long pow2(long long x)
 {
     return x * x;
  }
 long long Fibonacci(long long n) { // Fast calculation of Fibonacci number using 'fast doubling'

         if (n == 0)
                 return 0;
         else if(n <= 2)
                 return 1;
         else if (n % 2 == 0)
                 return Fibonacci(n / 2) * (2 * Fibonacci(n / 2 + 1) - Fibonacci(n / 2));
        else
                 return pow2(Fibonacci((n/2 + 1) / 2), 2) + pow2(Fibonacci((n / 2)), 2);
}

 long long GetPisanoPeriod(long long m){
         for (long long i = 2; i <= m * m ; ++i){
                 if (Fibonacci(i) % m == 0){ // if an element is zero it might be followed by a 1
                         if(Fibonacci(i+1) % m == 1){
                                return i - 1;
                         }
                 }
         }
 return 1;
 }
 int main() {
         long long n, m;
         std::cin >> n >> m;
         long long period = GetPisanoPeriod(m);
         long long res = Fibonacci(n % period) % m;
         std::cout << "res" << res<<endl;
 }

control may reach end of non-void function error is due to not returning value from GetPisanoPeriod. as pointed out by @JaMiT

The segmentation fault was due to the incorrect termination condition of function Fibonacci. Fibonacci series is defined as below.

  Fn = Fn-1 + Fn-2

with seed values

  F0 = 0 and F1 = 1

Meaning there should be a termination condition for n = 0 and n = 1. For n = 2 You don't have to call recursion can simply return 1.

Other than that, There were corrections in Fibonacci calculation formula as you can see. In GetPisanoPeriod The control has to start from 2. otherwise it would always return 0.

don't put line numbers in code, that'll prevent others from copying the code to try — phuclv, Jun 24 '19 at 04:27
And `::std::pow` should also be avoided here. It is templatized in C++11, but the result is still always a floating point type of some kind, which may work in this context, but mostly by accident. — Omnifarious, Jun 24 '19 at 19:58
FYI, [this is your code](http://coliru.stacked-crooked.com/a/a12ceac7b032d8be) with the `std::pow` removed, plus the cache optimizations. Since there was no test data, I am assuming this code works correctly (but no guarantee). — PaulMcKenzie, Jun 25 '19 at 03:12

Calculating mod m for large Fibonacci numbers

1 Answers1