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.