Matrix power without Numpy for 3x3 Matrix-CodePudding

I am trying to calculate Matrix raised to power 'n' without using Numpy for a 3x3 matrix (without using any library functions)

Here is the code that I have written so far:

   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)

This works fine for smaller numbers of 'n', but it fails with the following error when applied to large numbers:

 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

Seems like it is reaching Recursion Stack depth when tried for large numbers, is there a way to implement power in an optimised way, without using libraries?

CodePudding user response：

When using recursion, the heap creates a new record in memory to store the return register, so that each time you call the function matpow, the program knows which register to return to when the condition is met. Therefore, instead of using recursion, I'd use iteration.

Use a while/for loop instead to iterate over until you find the correct value.

CodePudding user response：

If the power argument is really huge, then use an iterative solution, by iterating the binary bits of the power:

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