CODEWITHSUNDEEP
c++c++17fibonacci
Reza Afra
Reza Afra

Reputation: 185

Calculating mod m for large Fibonacci numbers

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';
}

Upvotes: 0

Views: 722

Answers (1)

Christina Jacob
Christina Jacob

Reputation: 685

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.

Upvotes: 1

Related Questions