Huge Fibonacci modulo m optimization in Python 3 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.
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\$)