TheAlgorithms_Python/maths/matrix_exponentiation.py at master · mindaugl/TheAlgorithms_Python · GitHub

Name: TheAlgorithms_Python/maths/matrix_exponentiation.py at master · mindaugl/TheAlgorithms_Python · GitHub
Rating: 4.4 (2811 reviews)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
"""Matrix Exponentiation"""

importtimeit

"""
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/
"""


classMatrix:
def__init__(self, arg):
ifisinstance(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= [[0for_inrange(self.n)] for_inrange(self.n)]

def__mul__(self, b):
matrix=Matrix(self.n)
foriinrange(self.n):
forjinrange(self.n):
forkinrange(self.n):
matrix.t[i][j] +=self.t[i][k] *b.t[k][j]
returnmatrix


defmodular_exponentiation(a, b):
matrix=Matrix([[1, 0], [0, 1]])
whileb>0:
ifb&1:
matrix*=a
a*=a
b>>=1
returnmatrix


deffibonacci_with_matrix_exponentiation(n, f1, f2):
"""
 Returns the nth number of the Fibonacci sequence that
 starts with f1 and f2
 Uses the matrix exponentiation
 >>> fibonacci_with_matrix_exponentiation(1, 5, 6)
 5
 >>> fibonacci_with_matrix_exponentiation(2, 10, 11)
 11
 >>> fibonacci_with_matrix_exponentiation(13, 0, 1)
 144
 >>> fibonacci_with_matrix_exponentiation(10, 5, 9)
 411
 >>> fibonacci_with_matrix_exponentiation(9, 2, 3)
 89
 """
# Trivial Cases
ifn==1:
returnf1
elifn==2:
returnf2
matrix=Matrix([[1, 1], [1, 0]])
matrix=modular_exponentiation(matrix, n-2)
returnf2*matrix.t[0][0] +f1*matrix.t[0][1]


defsimple_fibonacci(n, f1, f2):
"""
 Returns the nth number of the Fibonacci sequence that
 starts with f1 and f2
 Uses the definition
 >>> simple_fibonacci(1, 5, 6)
 5
 >>> simple_fibonacci(2, 10, 11)
 11
 >>> simple_fibonacci(13, 0, 1)
 144
 >>> simple_fibonacci(10, 5, 9)
 411
 >>> simple_fibonacci(9, 2, 3)
 89
 """
# Trivial Cases
ifn==1:
returnf1
elifn==2:
returnf2

n-=2

whilen>0:
f2, f1=f1+f2, f2
n-=1

returnf2


defmatrix_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)
returnexec_time


defsimple_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
 )
returnexec_time


defmain():
matrix_exponentiation_time()
simple_fibonacci_time()


if__name__=="__main__":
main()