Huge Fibonacci modulo m optimization in Python 3

Question

I'm doing some an Algorithm Design online course as a way of learning algorithms and Python as well. One of these challenges requires that I write code for finding a "Huge Fibonacci Number Modulo m". The code works, but for some inputs (such as 99999999999999999 100000), it exceeds the allocated time limit. However, I can't see a way of improving performance.

Here is the problem description:

Problem Introduction

The Fibonacci numbers are defined as follows:

F(0) = 0, F(1) = 1, and F(i) = F(i−1) + F(i−2) for i ≥ 2.

Problem Description

Task: Given two integers n and m, output F(n) mod m (that is, the remainder of F(n) 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 F(n) mod m

Time Limits:C: 1 sec, C++: 1 sec, Java: 1.5 sec, Python: 5 sec. C#: 1.5 sec, Haskell: 2 sec, JavaScript: 3 sec, Ruby: 3 sec, Scala: 3 sec. Memory Limit: 512 Mb

Sample:

Input:

    281621358815590 30524

Output:

    11963

Here is the code:

#!/usr/bin/python3

from sys import stdin              

def get_fibonacci_huge(n, m):
    fibonacciNumbers = [0, 1, 1]
    pisanoNumbers = [0, 1, 1]
    pisanoPeriod = 3

    for i in range(2, n):
        if pisanoNumbers[i - 1] == 0 and pisanoNumbers[i] == 1:
            pisanoPeriod = i - 1
            break;

        nextFibonacci = fibonacciNumbers[i - 1] + fibonacciNumbers[i];

        fibonacciNumbers.append(nextFibonacci)
        pisanoNumbers.append(nextFibonacci % m)
    else:
        pisanoPeriod = None # If we exhausted all values up to n, then the pisano period could not be determined. 

    if pisanoPeriod is None:
        return pisanoNumbers[n]
    else:
        return pisanoNumbers[n % pisanoPeriod]

if __name__ == '__main__':
    dataEntry = stdin.readline()
    n, m = map(int, dataEntry.split())
    print(get_fibonacci_huge(n, m))

For an input of 99999999999999999 100000, it takes around 5.10 seconds, and the maximum allowed time is 5.00 seconds.

As a complete Python and algorithms newbie, any input is appreciated.

Answer 1

Fibonacci numbers grow exponentially. It means that the number of bits representing them grows linearly, and so does the complexity of computing nextFibonacci. It results in the overall quadratic complexity of your loop.

Good news is that you don't need to compute Fibonacci numbers at all. You only need to compute Pisano numbers. They obey the similar recurrence,

    p[n+1] = (p[n] + p[n-1]) % m

and by virtue of the modulo they never exceed m. A complexity of an individual addition stays constant, and the overall complexity becomes linear.

(Tiny additional: \$ (a + b)\ \textrm{mod}\ c\equiv a\ \textrm{mod}\ c\ + a\ \textrm{mod}\ c\$)

Answer 2

Let's suppose that you've implemented the suggestion made by vnp, so that the line now reads:

nextFibonacci = (fibonacciNumbers[i - 1] + fibonacciNumbers[i]) % m

Could there still be an improvement? The Pisano period modulo \$m\$ is at most \$6m\$ and so the period-finding approach takes \$O(m)\$ steps, each of which involves the addition of numbers with \$O(\log m)\$ digits, for an overall runtime of \$O(m\log m)\$.

There is an alternative approach, which is to compute the \$n\$th Fibonacci number modulo \$m\$ using the recurrence $$ \eqalign{F_{2n−1} &= F_{n}^2 + F_{n−1}^2 \\ F_{2n} &= (2F_{n−1} + F_{n}) F_{n}}. $$ This can be implemented efficiently using recursion and memoization, for example you could use the @functools.lru_cache decorator, like this:

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_modulo(n, m):
    """Return the nth Fibonacci number modulo m."""
    if n <= 1:
        return n
    elif n % 2:
        a = fibonacci_modulo(n // 2, m)
        b = fibonacci_modulo(n // 2 + 1, m)
        return (a * a + b * b) % m
    else:
        a = fibonacci_modulo(n // 2 - 1, m)
        b = fibonacci_modulo(n // 2, m)
        return (2 * a + b) * b % m

This takes \$O((\log n)^2)\$ multiplications of numbers with \$O(\log m)\$ digits, for an overall runtime of \$O((\log n \log m)^2)\$. So this approach would be an improvement on period-finding in cases where $$(\log n)^2\log m ≪ m.$$ For example, in the case \$n=10^{17}-1, m=10^5\$ given in the question, we have \$(\log n)^2\log m \approx 6000\$ and on this test case fibonacci_modulo is much faster than get_fibonacci_huge:

>>> n = 10**17 - 1
>>> m = 10**5
>>> timeit(lambda:get_fibonacci_huge(n, m), number=1)
0.09250206896103919
>>> fibonacci_modulo.cache_clear()
>>> timeit(lambda:fibonacci_modulo(n, m), number=1)
0.0001637069508433342

(Note the use of cache_clear to ensure that we have an empty cache and so the timing comparison is fair.)