Python: Compute a Huge Fibonacci Number Modulo m

Question

# Uses python3
# Given two integers n and m, output Fn mod m (that is, the remainder of Fn when divided by m
def Huge_Fib(n,m):

    if n == 0 : return 0
    elif n == 1: return 1
    else:
        a,b = 0,1
        for i in range(1,n):
            a, b = b, (a+b) % m
        print(b);

n,m = map(int, input().split());   
Huge_Fib(n,m);

The code works very well. However, when I run a case as n = 99999999999999999, m = 2, it takes me much time. Do you have any better solutions?

Answer 1

Here is my solution, you don't have to go through 99999999999999999 iterations if you find the pisano period.

I also recommend that you watch this video: https://www.youtube.com/watch?v=Nu-lW-Ifyec

# Uses python3
import sys

def get_fibonacci_huge(n, m):
    if n <= 1:
        return n

    arr = [0, 1]
    previousMod = 0
    currentMod = 1

    for i in range(n - 1):
        tempMod = previousMod
        previousMod = currentMod % m
        currentMod = (tempMod + currentMod) % m
        arr.append(currentMod)
        if currentMod == 1 and previousMod == 0:
            index = (n % (i + 1))
            return arr[index]

    return currentMod

if __name__ == '__main__':
    input = sys.stdin.read();
    n, m = map(int, input.split())
    print(get_fibonacci_huge(n,m))

Answer 2

# Uses python3
# Given two integers n and m, output Fn mod m (that is, the remainder of Fn when divided by m
def Huge_Fib(n,m):

    # Initialize a matrix [[1,1],[1,0]]    
    v1, v2, v3 = 1, 1, 0  
    # Perform fast exponentiation of the matrix (quickly raise it to the nth power)
    for rec in bin(n)[3:]:
        calc = (v2*v2) % m
        v1, v2, v3 = (v1*v1+calc) % m, ((v1+v3)*v2) % m, (calc+v3*v3) % m
        if rec == '1': v1, v2, v3 = (v1+v2) % m, v1, v2
    print(v2);        

n,m = map(int, input().split());   
Huge_Fib(n,m);

This is a superfast solution refer to https://stackoverflow.com/a/23462371/3700852

Answer 3

I solved it in Python 3. This the fastest algorithm to compute a huge Fibonacci number modulo m.For example for n =2816213588, m = 239, it took Max time used: 0.01/5.00, max memory used: 9424896/536870912.)

     def pisanoPeriod(m): 
        previous, current = 0, 1
        for i in range(0, m * m): 
            previous, current = current, (previous + current) % m 
            # A Pisano Period starts with 01 
            if (previous == 0 and current == 1): 
                return i + 1

    def calc_fib(n,m):
        p = pisanoPeriod(m)
        n = n % p
        if (n <= 1):
            return n
        else:
          previous,current = 0,1
          for i in range(2,n+1):
            previous,current = current,(previous+current)
        return current%m

    n,m =map(int,input().split(" "))
    print(calc_fib(n,m))

Answer 4

In the below code we are using two concepts of Fibonacci series:

1. Pisano periods follows a Fibonacci sequence and hence each repetition(pattern) begins with 0 and 1 appearing consecutively one after the other.

2. fib(n) divides fib(m) only when n divides m which means if fib(4)%3==0,then fib(4+4)%3==0,fib(4+4+4)%3==0 and so on.This helps us in finding the Pisano period.

To know about Pisano periods,I recommend that you watch this video: https://www.youtube.com/watch?v=Nu-lW-Ifyec

#python3
def pisano_length(m):
    i=2
    while(fib(i)%m!=0):
        i+=1
    if(fib(i+1)%m!=1):
        while(fib(i+1)%m!=1):
            i+=i
    print("The pisano length for mod {} is: {}".format(m,i))
    return(i)
def fib(n):
    a,b=0,1
    if(n==0 or n==1):
        return n
    else:
        for i in range(2,n+1):
            b,a=a+b,b
    return(b)
#we want to calculate fib(n)%m for big numbers
n,m=map(int,input().split())
remainder=n%pisano_length(m)
print(fib(remainder)%m)

Answer 5

You should look up Pisano periods. https://en.wikipedia.org/wiki/Pisano_period and http://webspace.ship.edu/msrenault/fibonacci/fibfactory.htm should give you a good understanding of what they are.

edit: Just googling "fibonacci modulo" gives you those two as the top two results.

Answer 6

For any integer m>=2, the sequence fn modulo m is periodic - Pisano Period. So no need to store and find fn. Instead, find a repeating pattern for given m.

Answer 7

This is how i have done by calculating the pisano period.(Java)

public static long get_pisano_period(long m) {
    long a = 0, b = 1;
    long c;
    for (int i = 0; i < m * m; i++) {
        c = (a + b) % m;
        a = b;
        b = c;
        if (a == 0 && b == 1)
            return i + 1;
    }
    return 0;
}

public static BigInteger get_fibonacci_huge(long n,long m) {
    long remainder = n % get_pisano_period(m);

    BigInteger first = BigInteger.valueOf(0);
    BigInteger second=BigInteger.valueOf(1);
    BigInteger m1=BigInteger.valueOf(m);
    BigInteger res = BigInteger.valueOf(remainder);

    for (long i = 1; i < remainder; i++) {
        res = (first.add(second)).mod(m1);
        first = second;
        second = res;
    }
    return res.mod(m1);
}