Modulus of nth Fibonacci Number

As part of an assignment I was asked to find an optimized algorithm to find the m modulus of nth Fibonacci number. Sounds pretty easy, until you see the size of the inputs - n has 30 digits in it!

At this stage, basic methods or brute force methods will take eons to finish. I had to go back to mathematics to find the solution. The algorithm came from this StackExchange answer, using a matrix equation for calculating super huge Fibonacci numbers.

What we're trying to achieve is:

F(n) % n # Where F(n) is the nth Fibonacci Number.

Below is the Python code for the solution:

def multiply(A, B, m):
    a = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % m
    b = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % m
    c = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % m
    d = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % m
    return [[a, b], [c, d]]

def power(A, n, m):
    if n == 1:
        return A
    if n % 2 == 0:
        return power(multiply(A, A, m), n//2, m)
    else:
        return multiply(A, power(A, n-1, m), m)

def fibonacci(n, m):
    A = [[1, 1], [1, 0]]
    if n == 0:
        return 0
    A = power(A, n, m)
    return A[1][0]

This matrix-based solution allows us to calculate the modulus of the nth Fibonacci number in O(log n) time, making it feasible even for extremely large inputs.

How It Works

The algorithm uses the property of matrix exponentiation combined with the modular arithmetic to efficiently compute the result. By representing the Fibonacci recurrence relation as a matrix and using the divide-and-conquer approach for matrix exponentiation, we reduce the time complexity dramatically.

Instead of calculating each Fibonacci number in sequence (which would be O(n)), we can directly calculate F(n) mod m in logarithmic time.