Pisano Period in C++

The Pisano period, denoted as π(n), is the period with which the sequence of Fibonacci numbers taken modulo n repeats. This article explores the concept of the Pisano period and provides a C++ implementation to calculate it for a given integer 'n'.

Fundamental Concepts / Prerequisites

Before diving into the implementation, it's essential to understand the following:

• Fibonacci Numbers: The sequence of numbers where each number is the sum of the two preceding ones, starting from 0 and 1 (i.e., 0, 1, 1, 2, 3, 5, 8, ...).
• Modulo Operation: The modulo operation (represented by the symbol %) finds the remainder after division of one number by another. For example, 7 % 3 = 1.

Core Implementation

#include <iostream>

using namespace std;

// Function to calculate the Pisano period for a given number 'm'
long long pisanoPeriod(long long m) {
    long long a = 0, b = 1, c = a + b;
    for (long long i = 0; i < m * m; i++) {
        c = (a + b) % m;
        a = b;
        b = c;
        if (a == 0 && b == 1) return i + 1;
    }
    return -1; // Should ideally not reach here; included for safety.
}

// Function to calculate the nth Fibonacci number modulo m
long long fibonacciModulo(long long n, long long m) {
    long long pisano = pisanoPeriod(m);
    n = n % pisano;

    long long a = 0, b = 1, c = n;
    for (long long i = 1; i <= n; i++) {
        c = (a + b) % m;
        a = b;
        b = c;
    }
    return a;
}


int main() {
    long long n, m;
    cout << "Enter n: ";
    cin >> n;
    cout << "Enter m: ";
    cin >> m;

    cout << "Fibonacci(" << n << ") mod " << m << " = " << fibonacciModulo(n, m) << endl;
    return 0;
}

Code Explanation

The code consists of two main functions:

pisanoPeriod(long long m):

This function calculates the Pisano period for a given integer m. It works by iterating through the Fibonacci sequence modulo m until the pair (0, 1) reappears, which indicates the start of the repeating pattern. The number of iterations needed to reach (0, 1) is the Pisano period. The loop iterates up to m*m, which provides a good upper bound; it guarantees that the Pisano period will be found within that limit. The function returns the Pisano period.

fibonacciModulo(long long n, long long m):

This function calculates the nth Fibonacci number modulo m. It first calculates the Pisano period for m. Then it reduces n modulo the Pisano period. This reduction is crucial because F(n) mod m = F(n mod pisano_period(m)) mod m. After the reduction, it computes the Fibonacci number at the reduced index using a loop and returns the result modulo m. By using the reduced index, the computational cost is drastically reduced when the value of `n` is significantly high.

Complexity Analysis

Time Complexity:

• pisanoPeriod(m): The loop iterates at most m*m times. Therefore, the time complexity is O(m²).
• fibonacciModulo(n, m): It depends on the pisanoPeriod(m) and then iterates up to n % pisanoPeriod(m). The complexity is O(m² + pisanoPeriod(m)). Since `pisanoPeriod(m)` is bounded by m*m, the overall complexity is O(m²). Because the calculation of the period is necessary, this function cannot be faster than O(m²).

Space Complexity:

Both functions have a constant space complexity, O(1), as they only use a few variables to store intermediate values regardless of the input size.

Alternative Approaches

An alternative approach could involve using the matrix exponentiation method to calculate Fibonacci numbers modulo m. This involves representing the Fibonacci sequence as a matrix and using repeated squaring to efficiently compute the nth power of the matrix. While more complex to implement, matrix exponentiation can improve the time complexity for calculating Fibonacci numbers, although calculating the Pisano period itself would still require similar logic.

Conclusion

The Pisano period provides an efficient way to calculate Fibonacci numbers modulo a given integer. The C++ implementation presented here demonstrates a straightforward approach to compute the Pisano period and then uses it to calculate the Fibonacci number modulo m, effectively handling large values of n. Understanding and utilizing the Pisano period optimizes calculations and prevents potential overflow issues when working with Fibonacci numbers.