3x3 矩阵没有 Numpy 的矩阵幂
Matrix power without Numpy for 3x3 Matrix
我正在尝试计算矩阵的幂'n',而不使用 Numpy 作为 3x3 矩阵(不使用任何库函数)
这是我到目前为止编写的代码:
def matmul(M1, M2):
a1 = (M1[0][0]*M2[0][0]) + (M1[0][1] * M2[1][0]) + (M1[0][2] * M2[2][0])
a2 = (M1[0][0]*M2[0][1]) + (M1[0][1] * M2[1][1]) + (M1[0][2] * M2[2][1])
a3 = (M1[0][0]*M2[0][2]) + (M1[0][1] * M2[1][2]) + (M1[0][2] * M2[2][2])
a4 = (M1[1][0]*M2[0][0]) + (M1[1][1] * M2[1][0]) + (M1[1][2] * M2[2][0])
a5 = (M1[1][0]*M2[0][1]) + (M1[1][1] * M2[1][1]) + (M1[1][2] * M2[2][1])
a6 = (M1[1][0]*M2[0][2]) + (M1[1][1] * M2[1][2]) + (M1[1][2] * M2[2][2])
a7 = (M1[2][0]*M2[0][0]) + (M1[2][1] * M2[1][0]) + (M1[2][2] * M2[2][0])
a8 = (M1[2][0]*M2[0][1]) + (M1[2][1] * M2[1][1]) + (M1[2][2] * M2[2][1])
a9 = (M1[2][0]*M2[0][2]) + (M1[2][1] * M2[1][2]) + (M1[2][2] * M2[2][2])
return [[a1, a2, a3], [a4, a5, a6], [a7, a8, a9]]
def matpow(mat, p):
if p == 1:
return mat
m2 = matpow(mat, p//2)
if p%2 == 0:
return matmul(m2, m2)
else:
return matmul(matmul(m2, m2), mat)
这适用于较小数量的 'n',但在应用于较大数量时会失败并出现以下错误:
File "/workspace/default/solution.py", line 17, in matpow
m2 = matpow(mat, p//2)
File "/workspace/default/solution.py", line 17, in matpow
m2 = matpow(mat, p//2)
[Previous line repeated 990 more times]
File "/workspace/default/solution.py", line 15, in matpow
if p == 1:
RecursionError: maximum recursion depth exceeded in comparison
似乎在尝试大量时达到递归堆栈深度,有没有一种方法可以在不使用库的情况下以优化的方式实现功能?
使用递归时,堆在内存中创建一条新记录来存放return寄存器,这样每次调用函数matpow
,程序就知道要[=19]到哪个寄存器=] 到满足条件时。因此,我不使用递归,而是使用迭代。
使用 while/for 循环来迭代直到找到正确的值。
这应该有效(已测试),
def matpow_iteratively(mat, p):
new_mat = mat
arr = []
while p > 1:
arr.append(p)
p = p // 2
index = len(arr) - 1
while index >= 0:
if arr[index] % 2 == 0:
new_mat = matmul(new_mat, new_mat)
else:
new_mat = matmul(matmul(new_mat, new_mat), mat)
index = index - 1
return new_mat
如果幂参数确实巨大,则使用迭代解决方案,通过迭代幂的二进制位:
def matpow(mat, p):
# Start with the identity matrix. This way it will also work for p==0
# If you are using floats, then make this also with floats:
result = [[1,0,0],[0,1,0],[0,0,1]]
while p > 0:
if p & 1:
result = matmul(result, mat)
mat = matmul(mat, mat)
p >>= 1
return result
我正在尝试计算矩阵的幂'n',而不使用 Numpy 作为 3x3 矩阵(不使用任何库函数)
这是我到目前为止编写的代码:
def matmul(M1, M2):
a1 = (M1[0][0]*M2[0][0]) + (M1[0][1] * M2[1][0]) + (M1[0][2] * M2[2][0])
a2 = (M1[0][0]*M2[0][1]) + (M1[0][1] * M2[1][1]) + (M1[0][2] * M2[2][1])
a3 = (M1[0][0]*M2[0][2]) + (M1[0][1] * M2[1][2]) + (M1[0][2] * M2[2][2])
a4 = (M1[1][0]*M2[0][0]) + (M1[1][1] * M2[1][0]) + (M1[1][2] * M2[2][0])
a5 = (M1[1][0]*M2[0][1]) + (M1[1][1] * M2[1][1]) + (M1[1][2] * M2[2][1])
a6 = (M1[1][0]*M2[0][2]) + (M1[1][1] * M2[1][2]) + (M1[1][2] * M2[2][2])
a7 = (M1[2][0]*M2[0][0]) + (M1[2][1] * M2[1][0]) + (M1[2][2] * M2[2][0])
a8 = (M1[2][0]*M2[0][1]) + (M1[2][1] * M2[1][1]) + (M1[2][2] * M2[2][1])
a9 = (M1[2][0]*M2[0][2]) + (M1[2][1] * M2[1][2]) + (M1[2][2] * M2[2][2])
return [[a1, a2, a3], [a4, a5, a6], [a7, a8, a9]]
def matpow(mat, p):
if p == 1:
return mat
m2 = matpow(mat, p//2)
if p%2 == 0:
return matmul(m2, m2)
else:
return matmul(matmul(m2, m2), mat)
这适用于较小数量的 'n',但在应用于较大数量时会失败并出现以下错误:
File "/workspace/default/solution.py", line 17, in matpow
m2 = matpow(mat, p//2)
File "/workspace/default/solution.py", line 17, in matpow
m2 = matpow(mat, p//2)
[Previous line repeated 990 more times]
File "/workspace/default/solution.py", line 15, in matpow
if p == 1:
RecursionError: maximum recursion depth exceeded in comparison
似乎在尝试大量时达到递归堆栈深度,有没有一种方法可以在不使用库的情况下以优化的方式实现功能?
使用递归时,堆在内存中创建一条新记录来存放return寄存器,这样每次调用函数matpow
,程序就知道要[=19]到哪个寄存器=] 到满足条件时。因此,我不使用递归,而是使用迭代。
使用 while/for 循环来迭代直到找到正确的值。
这应该有效(已测试),
def matpow_iteratively(mat, p):
new_mat = mat
arr = []
while p > 1:
arr.append(p)
p = p // 2
index = len(arr) - 1
while index >= 0:
if arr[index] % 2 == 0:
new_mat = matmul(new_mat, new_mat)
else:
new_mat = matmul(matmul(new_mat, new_mat), mat)
index = index - 1
return new_mat
如果幂参数确实巨大,则使用迭代解决方案,通过迭代幂的二进制位:
def matpow(mat, p):
# Start with the identity matrix. This way it will also work for p==0
# If you are using floats, then make this also with floats:
result = [[1,0,0],[0,1,0],[0,0,1]]
while p > 0:
if p & 1:
result = matmul(result, mat)
mat = matmul(mat, mat)
p >>= 1
return result