Matrix Exponentiation import timeit class Matrix: def initself, arg: if isinstancearg, list:   Initializes a matrix identical to the one provided. self.t  arg self.n  lenarg else:   Initializes a square matrix of the given size and set values to zero. self.n  arg self.t  0 for  in rangeself.n for  in rangeself.n def mulself, b: matrix  Matrixself.n for i in rangeself.n: for j in rangeself.n: for k in rangeself.n: matrix.tij  self.tik  b.tkj return matrix def modularexponentiationa, b: matrix  Matrix1, 0, 0, 1 while b  0: if b  1: matrix  a a  a b  1 return matrix def fibonacciwithmatrixexponentiationn, f1, f2: Trivial Cases if n  1: return f1 elif n  2: return f2 matrix  Matrix1, 1, 1, 0 matrix  modularexponentiationmatrix, n  2 return f2  matrix.t00  f1  matrix.t01 def simplefibonaccin, f1, f2: Trivial Cases if n  1: return f1 elif n  2: return f2 fn1  f1 fn2  f2 n  2 while n  0: fn1, fn2  fn1  fn2, fn1 n  1 return fn1 def matrixexponentiationtime: setup   from random import randint from main import fibonacciwithmatrixexponentiation code  simplefibonaccirandint1,70000, 1, 1 exectime  timeit.timeitsetupsetup, stmtcode, number100 print Without matrix exponentiation the average execution time is , exectime  100  return exectime def main: matrixexponentiationtime simplefibonaccitime if name  main: main
import timeit

"""
Matrix Exponentiation is a technique to solve linear recurrences in logarithmic time.
You read more about it here:
https://zobayer.blogspot.com/2010/11/matrix-exponentiation.html
https://www.hackerearth.com/practice/notes/matrix-exponentiation-1/
"""


class Matrix:
    def __init__(self, arg):
        if isinstance(arg, list):  # Initializes a matrix identical to the one provided.
            self.t = arg
            self.n = len(arg)
        else:  # Initializes a square matrix of the given size and set values to zero.
            self.n = arg
            self.t = [[0 for _ in range(self.n)] for _ in range(self.n)]

    def __mul__(self, b):
        matrix = Matrix(self.n)
        for i in range(self.n):
            for j in range(self.n):
                for k in range(self.n):
                    matrix.t[i][j] += self.t[i][k] * b.t[k][j]
        return matrix


def modular_exponentiation(a, b):
    matrix = Matrix([[1, 0], [0, 1]])
    while b > 0:
        if b & 1:
            matrix *= a
        a *= a
        b >>= 1
    return matrix


def fibonacci_with_matrix_exponentiation(n, f1, f2):
    # Trivial Cases
    if n == 1:
        return f1
    elif n == 2:
        return f2
    matrix = Matrix([[1, 1], [1, 0]])
    matrix = modular_exponentiation(matrix, n - 2)
    return f2 * matrix.t[0][0] + f1 * matrix.t[0][1]


def simple_fibonacci(n, f1, f2):
    # Trivial Cases
    if n == 1:
        return f1
    elif n == 2:
        return f2

    fn_1 = f1
    fn_2 = f2
    n -= 2

    while n > 0:
        fn_1, fn_2 = fn_1 + fn_2, fn_1
        n -= 1

    return fn_1


def matrix_exponentiation_time():
    setup = """
from random import randint
from __main__ import fibonacci_with_matrix_exponentiation
"""
    code = "fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)"
    exec_time = timeit.timeit(setup=setup, stmt=code, number=100)
    print("With matrix exponentiation the average execution time is ", exec_time / 100)
    return exec_time


def simple_fibonacci_time():
    setup = """
from random import randint
from __main__ import simple_fibonacci
"""
    code = "simple_fibonacci(randint(1,70000), 1, 1)"
    exec_time = timeit.timeit(setup=setup, stmt=code, number=100)
    print(
        "Without matrix exponentiation the average execution time is ", exec_time / 100
    )
    return exec_time


def main():
    matrix_exponentiation_time()
    simple_fibonacci_time()


if __name__ == "__main__":
    main()
