matrix exponentiation Algorithm
Matrix exponentiation algorithm is a powerful technique used for solving linear recurrence relations, which arise in various mathematical problems and real-world applications such as dynamic programming, combinatorics, and graph theory. The core idea behind the algorithm is to represent the relation as a matrix and raise it to a required power to compute the desired values efficiently. This method helps in reducing the time complexity of solving such problems from the traditional O(N) or O(logN) to O(logK), where N is the number of terms in the sequence, and K is the index of the term we want to compute.
Matrix exponentiation involves two main steps: matrix construction and matrix exponentiation. In the first step, matrix construction, we represent the linear recurrence relation as a matrix called the transformation matrix. This matrix, when multiplied with the initial state vector (which contains the initial values of the sequence), produces the next state vector. In the second step, matrix exponentiation, we compute the matrix power using an efficient algorithm called exponentiation by squaring (also known as binary exponentiation), which allows us to raise the matrix to a large power in logarithmic time. This step is crucial in obtaining the desired term of the sequence with minimal time complexity. Once the transformation matrix is raised to the required power, we multiply it with the initial state vector to get the desired term in the sequence.
"""Matrix Exponentiation"""
import timeit
"""
Matrix Exponentiation is a technique to solve linear recurrences in logarithmic time.
You read more about it here:
http://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 the 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()
