Python/maths/matrix_exponentiation.py at master · manmita/Python · GitHub

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
"""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):
# 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):
# Trivial Cases
ifn==1:
returnf1
elifn==2:
returnf2

fn_1=f1
fn_2=f2
n-=2

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

returnfn_1


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()
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
"""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):
# 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):
# Trivial Cases
ifn==1:
returnf1
elifn==2:
returnf2

fn_1=f1
fn_2=f2
n-=2

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

returnfn_1


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()
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
"""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):
# 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):
# Trivial Cases
ifn==1:
returnf1
elifn==2:
returnf2

fn_1=f1
fn_2=f2
n-=2

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

returnfn_1


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()
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
"""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):
# 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):
# Trivial Cases
ifn==1:
returnf1
elifn==2:
returnf2

fn_1=f1
fn_2=f2
n-=2

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

returnfn_1


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()
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
"""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):
# 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):
# Trivial Cases
ifn==1:
returnf1
elifn==2:
returnf2

fn_1=f1
fn_2=f2
n-=2

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

returnfn_1


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()
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
"""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):
# 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):
# Trivial Cases
ifn==1:
returnf1
elifn==2:
returnf2

fn_1=f1
fn_2=f2
n-=2

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

returnfn_1


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()
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
"""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):
# 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):
# Trivial Cases
ifn==1:
returnf1
elifn==2:
returnf2

fn_1=f1
fn_2=f2
n-=2

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

returnfn_1


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()
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
"""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):
# 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):
# Trivial Cases
ifn==1:
returnf1
elifn==2:
returnf2

fn_1=f1
fn_2=f2
n-=2

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

returnfn_1


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()