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.

• vnp: Could you add the problem statement, so that we don't need to reverse engineer the code?
• greybeard: Given the problem statement and the code you presented: Is that your code? We cannot review code written by other programmers.

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\$)

• maxb: One thing to note is that Pisano numbers are cyclical, meaning that you only have to calculate until you reach a cycle, and then the rest is trivial.
• vnp: @maxb The cycle could be very large; so large that you can't find it within problem limits.
• maxb: Of course, but by simply keeping track of the last two values, and checking if they are 0 and 1 shouldn't slow the program down by very much, while providing a possible performance increase.

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 \6ドルm\$ 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 % m
 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.)

• Oscar Smith: this answer should be the accepted, as it is exponentially faster, and the code isn't much longer.
• Gareth Rees: @OscarSmith: It's not faster in all cases: if \$m ≪ (\log n)^2\log m\$ then period-finding is faster. The ideal solution would choose the appropriate algorithm according to the arguments. (Some careful measurement would be needed to determine the exact criteria.)