I'm trying to implement Strassen's matrix multiplication algorithm in VBScript. However I'm having a lot of issues with the recursion.
In the following recursive algorithm:
Function multiply(matrixA, matrixB)
Dim n
n = UBound(matrixA) + 1
ReDim R(n - 1, n - 1)
If (n = 1) Then
R(0,0) = matrixA(0,0) * matrixB(0,0)
Else
ReDim A11(n/2 - 1, n/2 - 1)
ReDim A12(n/2 - 1, n/2 - 1)
ReDim A21(n/2 - 1, n/2 - 1)
ReDim A22(n/2 - 1, n/2 - 1)
ReDim B11(n/2 - 1, n/2 - 1)
ReDim B12(n/2 - 1, n/2 - 1)
ReDim B21(n/2 - 1, n/2 - 1)
ReDim B22(n/2 - 1, n/2 - 1)
Call PartitionMatrix(matrixA, A11, 0, 0)
Call PartitionMatrix(matrixA, A11, 0, n/2 - 1)
Call PartitionMatrix(matrixA, A21, n/2 - 1, 0)
Call PartitionMatrix(matrixA, A22, n/2 - 1, n/2 - 1)
Call PartitionMatrix(matrixB, B11, 0, 0)
Call PartitionMatrix(matrixB, B12, 0, n/2 - 1)
Call PartitionMatrix(matrixB, B21, n/2 - 1, 0)
Call PartitionMatrix(matrixB, B22, n/2 - 1, n/2 - 1)
Dim M1, M2, M3, M4, M5, M6, M7
M1 = multiply(AddMatrix(A11, A22), AddMatrix(B11, B22))
M2 = multiply(AddMatrix(A21, A22), B11)
M3 = multiply(A11, SubMatrix(B12, B22))
M4 = multiply(A22, SubMatrix(B21, B11))
M5 = multiply(AddMatrix(A11, A12), B22)
M6 = multiply(SubMatrix(A21, A11), AddMatrix(B11, B12))
M7 = multiply(SubMatrix(A12, A22), AddMatrix(B21, B22))
Wscript.Echo UBound(R) 'Returns only 0's in console
Dim C11, C12, C21, C22
C11 = AddMatrix(SubMatrix(AddMatrix(M1, M4), M5), M7)
C12 = AddMatrix(M3, M5)
C21 = AddMatrix(M2, M4)
C22 = AddMatrix(SubMatrix(AddMatrix(M1, M3), M2), M6)
Call JoinMatrix(C11, R, 0 , 0)
Call JoinMatrix(C12, R, 0 , n/2 - 1)
Call JoinMatrix(C21, R, n/2 - 1, 0)
Call JoinMatrix(C22, R, n/2 - 1, n/2 - 1)
End If
multiply = R
End Function
I am assigning the return value of the multiply function into variables M1, M2, and so forth. However, it seems that the variable R that I am returning in multiply is being carried over from the recursive function - as in, it's not declaring a new matrix R. In theory, if R was getting a new memory location every time it was being declared in the function it shouldn't be affected by the recursive calls to the multiply function at all (where I am echo'ing UBound(R)), but it is. How can I make sure R is actually getting a new declaration every time the function is called in the recursion?
R it is not explicitly dimensioned anywhere, so it is implicitly dimensioned out of the function and you just re-dimension it in the function.
Insert Dim R() directly above ReDim R(n - 1, n - 1) to dimension it in the function explicitly and it should work as you expect.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments