Calculate Huge Fibonacci number modulo M in C++

Question

Problem statement : Given two integers n and m, output Fn mod m (that is, the remainder of Fn when divided by m).

Input Format. The input consists of two integers n and m given on the same line (separated by a space). Constraints. 1 ≤ n ≤ 10^18, 2 ≤ m ≤ 10^5

Output Format. Output Fn mod m.

I tried the following program and it didn't work. The method pi is returning the right Pisano period though for any number as per http://webspace.ship.edu/msrenault/fibonacci/fiblist.htm

#include <iostream>

long long pi(long long m) {
    long long result = 2;
    for (long long fn2 = 1, fn1 = 2 % m, fn = 3 % m;
    fn1 != 1 || fn != 1;
        fn2 = fn1, fn1 = fn, fn = (fn1 + fn2) % m
        ) {
        result++;
    }
    return result;
}

long long get_fibonaccihuge(long long n, long long m) {
    long long periodlength = pi(m);
    int patternRemainder = n % periodlength;    

    long long *sum = new long long[patternRemainder];

    sum[0] = 0;
    sum[1] = 1;
    for (int i = 2; i <= patternRemainder; ++i)
    {
        sum[i] = sum[i - 1] + sum[i - 2];
    }   
    return sum[patternRemainder] % m;
}

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

The exact program/logic is working well in python as expected. What's wrong withthis cpp program ? Is it the data types ?

*I tried the following program and it didn't work* is not a very good description. You need to tell us the inputs, outputs and expected outputs. Also have to stepped through the code to see where things start to go wrong? — NathanOliver, May 03 '16 at 16:43
Calculate the remainder after each step, or you'll have an overflow in between. — gnasher729, May 03 '16 at 16:45
And while you're at it, Fn should always be positive, so I don't see any reason to be using *signed* `long long` values. — WhozCraig, May 03 '16 at 16:47
a side note you can solve the question using matrix exponentiation. For more details have a look here : https://math.stackexchange.com/questions/1102452/modulus-of-sum-of-sequence-of-fibonacci-numbers/1102494#1102494 — advocateofnone, May 03 '16 at 16:48
@sasha http://mathoverflow.net/questions/40816/fibonacci-series-mod-a-number is more relevant for OP's question. — Holt, May 03 '16 at 16:52
Can you use the closed form expression for the nth Fibonacci number? There is a nice one which is `Round(phi^n/Sqrt(5))`. The exponentiation can be decomposed using [addition chains](https://en.wikipedia.org/wiki/Addition-chain_exponentiation). You'll want to perform the multiplication modulo `m*Sqrt(5)` so that you can divide by `Sqrt(5)` at the end. The worst case is 50 multiplications, so floating point precision hopefully won't be an issue. — Jared Goguen, May 03 '16 at 17:03
@JaredGoguen Floating point precision will be a huge issue. You're looking for the last 5 digits of a number that potentially has around a sextillion digits. — btilly, May 03 '16 at 18:54
Possible duplicate of [Fast Computation of Pisano Period](https://stackoverflow.com/questions/38658745/fast-computation-of-pisano-period) — Lesair Valmont, Aug 08 '18 at 20:47

score 3 · Answer 1 · edited May 23 '17 at 11:52

3

Performing 10^18 additions isn't going to be very practical. Even on a teraflop computer, 10^6 seconds is still 277 hours.

But 10^18 ~= 2^59.8 so there'll be up to 60 halving steps.

Calculate (a,b) --> (a^2 + b^2, 2ab + b^2) to go from (n-1,n)th to (2n-1,2n)th consecutive Fibonacci number pairs in one step.

At each step perform the modulus calculation for each operation. You'll need to accommodate integers up to 3*10¹⁰ &leq; 2³⁵ in magnitude (i.e. up to 35 bits).

(cf. a related older answer of mine).

edited May 23 '17 at 11:52

Community

1
1

answered May 03 '16 at 17:10

Will Ness

70,110
9
98
181

1

This is the right approach. Note that you need to take the number and half it repeatedly, subtracting 1 where needed, to figure out the sequence to go the other way. Then you work your way back up using the above to double, and `(a, b) -> (b, a+b)` for the +1 steps. – btilly May 03 '16 at 19:00

score 1 · Accepted Answer · answered Feb 04 '21 at 11:53

This was my solution for this problem, it works well and succeeded in the submission test ...

i used a simpler way to get the pisoano period ( pisano period is the main tricky part in this problem ) ... i wish to be helpful

#include <iostream>
using namespace std;

unsigned long long get_fibonacci_huge_naive(unsigned long long n, unsigned long long m)
{
    if (n <= 1)
        return n;

    unsigned long long previous = 0;
    unsigned long long current = 1;

    for (unsigned long long i = 0; i < n - 1; ++i)
    {
        unsigned long long tmp_previous = previous;
        previous = current;
        current = tmp_previous + current;
    }

    return current % m;
}

long long get_pisano_period(long long m)
{
    long long a = 0, b = 1, c = a + b;
    for (int i = 0; i < m * m; i++)
    {
        c = (a + b) % m;
        a = b;
        b = c;
        if (a == 0 && b == 1)
        {
            return i + 1;
        }
    }
}
unsigned long long get_fibonacci_huge_faster(unsigned long long n, unsigned long long m)
{
    n = n % get_pisano_period(m);
    unsigned long long F[n + 1] = {};
    F[0] = 0;
    F[-1] = 1;

    for (int i = 1; i <= n; i++)
    {
        F[i] = F[i - 1] + F[i - 2];
        F[i] = F[i] % m;
    }
    return F[n];
}

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

Calculate Huge Fibonacci number modulo M in C++

2 Answers2