Dieser Assemblercode kann die Determinante einer NxN Matrix berechnen. Dabei wird die NxN-Matrix mit Hilfe des Laplaceschen Entwicklungssatzes in N N-1xN-1-Matrixen zerlegt (eine 4×4-Matrix wird in 4 3×4-Matrixen zerlegt, usw).
Das Programm funktioniert leider nicht für “große” Matrixen (z.B. 10×10), weil das Programm dann aus dem Heap raus schreibt. Aber für Matrixen bis 5×5 funktioniert es definitiv, eventuell auch für Größere, das habe ich aber nicht getestet.
.data
dim:
#.word 2
#.word 3
#.word 4
.word 5
#.word 10
matrix:
#2x2-Martrix; solution = -2
#.word 3, 4, 5, 6
#3x3-Matrixx; solution = 4
#.word 3, 4, 5, 9, 4, 9, 1, 2, 2
#4x4-Matrix; solution = -19
#.word 3, 4, 5, 9, 4, 9, 1, 2, 2, 1, 3, 5, 7, 9, 3, 5
#solution = 0
.word 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
#.word -2, 1, 1, -2, -1, -1, -1, 3, -2, -3, 0, -1, -1, -4, -5, -5, 3, 2, -4, 1, 1, 1, 0, 3, 2, 0, 3, 3, 2, 0, 2, -3, 0, -1, 4, -1, -2, -3, 0, -1, 2, -3, -3, -5, -3, -5, -3, -1, -5, 3, 0, -5, 0, -5, -5, -1, 2, 1, -4, -1, -5, -4, 1, 1, -4, 2, 3, 4, -3, -1, 1, -2, 0, -3, 1, -5, 4, 3, -1, -4, -5, 2, -5, -2, -3, -3, 3, -2, 1, -3, 1, -1, -3, 2, 0, -5, 3, 2, 3, -5
det: .asciiz "Die Determinante ist: "
###############################################################################
.text
main:
###################################
###################################
#Hier soll das Programm stehen
#Das Ergebnis muss am Ende in $s6 stehen.
addi $s7, $0, 0x10040000 # initialize default heap pointer
la $a0, matrix
lw $a1, dim
jal calcDet
addi $s6, $v0, 0
j ende
###################################
# Calculates the determinante of a NxN matrix.
# expects: adress of array with N^2 elements in $a0
# dimension of matrix in $a1
# returns det. of given matrix in $v0
###################################
# Documentation
# $a0 -> matrix
# $a1 -> dim
# ----------------
# $s0 -> sum of det. of matrixes
calcDet:
# if
slti $t0, $a1, 2 # if $a1(=dim) < 2
beq $0, $t0, calcDetIf # jump to the if part
# if $t0 == $t1(=1) or
# if 2 < dim
# else
lw $v0, 0($a0)
jr $ra # jump back to caller
calcDetIf: # The if part
# reduce maxtrix and call recursive for each
# reduced matrix
addi $sp, $sp, -4 # get some space on stack
sw $ra, 0($sp) # store return adress in stack
addi $s0, $0, 0 # initialize $s0 (sum) with 0
addi $t0, $0, 0 # initialize $t0 (i) with 0
calcDetLoop: # loop over all sub-matrixes
beq $t0, $a1, calcDetLoopDone
# while $t0(=i) != $a1(=dim)
addi $sp, $sp, -16 # get some space on stack
sw $s0, 0($sp) # store sum
sw $t0, 4($sp) # store $t0 (i)
sw $a0, 8($sp) # store $a0
sw $a1, 12($sp) # store $a1
# dont need to copy any adress
# in $a0 because its already there
# dont need to copy any dimension
# of matrix in $a1 because its already there
addi $a2, $t0, 0 # copy i into $a2
jal reduceMatrix # jump to reduceMatrix
addi $a0, $v0, 0 # copy result adress of reduceMatrix
# into argument register for recursive call
sub $a1, $a1, 1 # $a1 = dim - 1
jal calcDet # call myself recursively
lw $a1, 12($sp) # load $a1
lw $a0, 8($sp) # load $a0
lw $t0, 4($sp) # load $t0 (i)
lw $s0, 0($sp) # load sum
addi $sp, $sp, 16 # clean up the stack
addi $t2, $0, 1 # initialise pow(er) with 1
and $t1, $t0, 1 # $t1 = $t0 & 0x00000001
beq $t1, $0, calcDetLoopJump
# skip one line, if $t0 % 2 = 1
addi $t2, $0, -1 # set power to -1
calcDetLoopJump:
addi $t1, $0, 4 # $t1 = 4 (because one word = 4 bytes)
mult $t0, $t1 # i * $t1(=4)
mflo $t3 # get result in $t3
add $t3, $a0, $t3 # add calulated offset to start adress of matrix
lw $t3, 0($t3) # load value at calulated adress
mult $t2, $t3 # power * (i-th element in matrx (always in first row))
mflo $t4 # get result in $t4
mult $t4, $v0 # multiply calcDet-result with calculated stuff
mflo $t4 # get result in $t4
add $s0, $s0, $t4 # add to sum
addi $t0, $t0, 1 # $t0++ or i++
j calcDetLoop
calcDetLoopDone: # loop finished, calculated all matrixes
addi $v0, $s0, 0 # copy sum into return register
lw $ra, 0($sp) # load return adress from stack
addi $sp, $sp, 4 # get some space on stack
jr $ra
###################################
###################################
# Extracts _one_ (N-1) matrix from a
# NxN matrix. The argument
# $a2 says which (N-1) matrix should
# be returned.
# expects: adress of array with N^2 elements in $a0
# dimension of matrix in $a1
# index of the smaller matrix (0-based) in $a2
# returns adress of (N-1) matrix in $v0
###################################
# Documentation
# $a0 -> matrix
# $a1 -> dim
# $a2 -> index of matrix that should be returned
# ----------------
# $s0 -> dim - 1
# $s1 -> counter for the current position in the SOURCE matrix
# $s2 -> counter for the current position in the TARGET matrix
reduceMatrix:
addi $s0, $a1, -1 # $s0 = dim - 1
mult $s0, $s0 # $s0*$s0 or
# (N-1)^2 or (dim-1)^2
# is also the size of the
# new matrix
mflo $t1 # get result into $t1
# $t1 contains now the number of words required
addi $s1, $a0, 0 # copy start adress of source matrix in $s1
addi $s2, $s7, 0 # save current position of heap pointer in $s2
addi $v0, $s7, 0 # copy target array adress in return register
addi $t0, $0, 4 # set $t0 = 4
mult $t1, $t0 # multiply $t0(=4) * $t1(=(dim-1)^2)
# -> amount of necessary bytes
mflo $t0 # copy result in $t0
add $s7, $s7, $t0 # get (N-1)^2 space of heap
addi $t0, $0, 4 # set $t0 = 4
mult $a1, $t0 # $a1(=dim)*$t0(=4)
# number of bytes that must be skipped to
# skip the first row of source matrix
mflo $t0
add $s1, $s1, $t0 # skip dim-elements or
# skip the first row of source matrix
addi $t0, $s0, 0 # initialize counter for loop 1; used as i
add $t2, $t0, $a2 # $t2 = $t0 + $a2 or
# $t2 = i + index
reduceMatrixLoop1: # loop 1
beq $t2, $t0, reduceMatrixLoop1Done
# while index != i
lw $t1, 0($s1) # load next entry from source matrix in $t1
sw $t1, 0($s2) # store the entry in the target matrix
addi $s1, $s1, 4 # increase pointer $s1 = $s1 + 4
addi $s2, $s2, 4 # increase pointer $s2 = $s2 + 4
addi $t0, $t0, 1 # $t0 = $t0 + 1 or
# $t0++ (i++)
j reduceMatrixLoop1 # jump up to the beginning of the loop
reduceMatrixLoop1Done: # endloop 1
reduceMatrixLoop2: # loop 2
mult $a1, $a1
mflo $t1
beq $t0, $t1, reduceMatrixLoop2Done
# while i < dim^2
addi $s1, $s1, 4 # skip one element in SOURCE matrix
addi $t0, $t0, 1 # $t0 = $t0 + 1 or
# $t0++ or i++
mult $a1, $a1 # $a1^2 or dim^2
mflo $t2 # get the result in $t2
sub $t2, $t2, 1 # sub 1 from $t2, because I want to compare
# it with $t0 (0-based) or
# (dim^2)-1
sub $t2, $t2, $t0 # $t2-$t0 or (dim^2)-1-i
# if
slt $t3, $t2, $s0 # (dim^2)-1-i < dim-1 or
# if $t3 == 1, you reached the last
# row and already skipped
beq $t3, $0, reduceMatrixLoop2Else
# jumps, if (dim-1)^2 - i < dim - 1 is false
# in human words: if the programm
# is NOT in the last row of the source matrix
# if case
# copy the last elements of source into target and exit function! :)
mult $a1, $a1 # dim^2
mflo $t2 # get result in $t2
reduceMatrixLoop2Loop1:
beq $t2, $t0, reduceMatrixLoop2Done
# jump if dim^2-1 == i or jump if
# end of source matrix is reached
lw $t1, 0($s1) # load next entry from source matrix in $t1
sw $t1, 0($s2) # store the entry in the target matrix
addi $s1, $s1, 4 # increase pointer $s1 = $s1 + 4
addi $s2, $s2, 4 # increase pointer $s2 = $s2 + 4
addi $t0, $t0, 1 # $t0 = $t0 + 1 or
# $t0++ or i++
j reduceMatrixLoop2Loop1
# jump up again, because its a loop!
j reduceMatrixLoop2Endif
# leave if case
# never used because if loop is finished
# it will jump to the end of the function
reduceMatrixLoop2Else: # else case
# copy dim - 1 elements
add $t2, $t0, $s0 # $t2 = $t0(=i) + $s0(=dim-1)
reduceMatrixLoop2ElseLoop:
beq $t2, $t0, reduceMatrixLoop2
# if $t2 = $t0 jump to main loop
lw $t1, 0($s1) # load next entry from source matrix in $t1
sw $t1, 0($s2) # store the entry in the target matrix
addi $s1, $s1, 4 # increase pointer $s1 = $s1 + 4
addi $s2, $s2, 4 # increase pointer $s2 = $s2 + 4
addi $t0, $t0, 1 # $t0 = $t0 + 1 or
# $t0++ or i++
j reduceMatrixLoop2ElseLoop
# jump up to the beginning of the loop
reduceMatrixLoop2Endif: # endif
addi $t0, $t0, 1 # $t0 = $t0 + 1 or
# $t0++ or i++
j reduceMatrixLoop2 # jump up to the beginning of the loop
reduceMatrixLoop2Done: # endloop 2
jr $ra # jump to caller function
# return value ($v0) is set at beginning
# of this function
###################################
###################################
###################################
ende:
#Ausgabe
la $a0 det
li $v0 4
syscall
move $a0, $s6
li $v0, 1
syscall
###################################
#Ende
li $v0, 10
syscall
dim:
#.word 2
#.word 3
#.word 4
.word 5
#.word 10
matrix:
#2x2-Martrix; solution = -2
#.word 3, 4, 5, 6
#3x3-Matrixx; solution = 4
#.word 3, 4, 5, 9, 4, 9, 1, 2, 2
#4x4-Matrix; solution = -19
#.word 3, 4, 5, 9, 4, 9, 1, 2, 2, 1, 3, 5, 7, 9, 3, 5
#solution = 0
.word 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
#.word -2, 1, 1, -2, -1, -1, -1, 3, -2, -3, 0, -1, -1, -4, -5, -5, 3, 2, -4, 1, 1, 1, 0, 3, 2, 0, 3, 3, 2, 0, 2, -3, 0, -1, 4, -1, -2, -3, 0, -1, 2, -3, -3, -5, -3, -5, -3, -1, -5, 3, 0, -5, 0, -5, -5, -1, 2, 1, -4, -1, -5, -4, 1, 1, -4, 2, 3, 4, -3, -1, 1, -2, 0, -3, 1, -5, 4, 3, -1, -4, -5, 2, -5, -2, -3, -3, 3, -2, 1, -3, 1, -1, -3, 2, 0, -5, 3, 2, 3, -5
det: .asciiz "Die Determinante ist: "
###############################################################################
.text
main:
###################################
###################################
#Hier soll das Programm stehen
#Das Ergebnis muss am Ende in $s6 stehen.
addi $s7, $0, 0x10040000 # initialize default heap pointer
la $a0, matrix
lw $a1, dim
jal calcDet
addi $s6, $v0, 0
j ende
###################################
# Calculates the determinante of a NxN matrix.
# expects: adress of array with N^2 elements in $a0
# dimension of matrix in $a1
# returns det. of given matrix in $v0
###################################
# Documentation
# $a0 -> matrix
# $a1 -> dim
# ----------------
# $s0 -> sum of det. of matrixes
calcDet:
# if
slti $t0, $a1, 2 # if $a1(=dim) < 2
beq $0, $t0, calcDetIf # jump to the if part
# if $t0 == $t1(=1) or
# if 2 < dim
# else
lw $v0, 0($a0)
jr $ra # jump back to caller
calcDetIf: # The if part
# reduce maxtrix and call recursive for each
# reduced matrix
addi $sp, $sp, -4 # get some space on stack
sw $ra, 0($sp) # store return adress in stack
addi $s0, $0, 0 # initialize $s0 (sum) with 0
addi $t0, $0, 0 # initialize $t0 (i) with 0
calcDetLoop: # loop over all sub-matrixes
beq $t0, $a1, calcDetLoopDone
# while $t0(=i) != $a1(=dim)
addi $sp, $sp, -16 # get some space on stack
sw $s0, 0($sp) # store sum
sw $t0, 4($sp) # store $t0 (i)
sw $a0, 8($sp) # store $a0
sw $a1, 12($sp) # store $a1
# dont need to copy any adress
# in $a0 because its already there
# dont need to copy any dimension
# of matrix in $a1 because its already there
addi $a2, $t0, 0 # copy i into $a2
jal reduceMatrix # jump to reduceMatrix
addi $a0, $v0, 0 # copy result adress of reduceMatrix
# into argument register for recursive call
sub $a1, $a1, 1 # $a1 = dim - 1
jal calcDet # call myself recursively
lw $a1, 12($sp) # load $a1
lw $a0, 8($sp) # load $a0
lw $t0, 4($sp) # load $t0 (i)
lw $s0, 0($sp) # load sum
addi $sp, $sp, 16 # clean up the stack
addi $t2, $0, 1 # initialise pow(er) with 1
and $t1, $t0, 1 # $t1 = $t0 & 0x00000001
beq $t1, $0, calcDetLoopJump
# skip one line, if $t0 % 2 = 1
addi $t2, $0, -1 # set power to -1
calcDetLoopJump:
addi $t1, $0, 4 # $t1 = 4 (because one word = 4 bytes)
mult $t0, $t1 # i * $t1(=4)
mflo $t3 # get result in $t3
add $t3, $a0, $t3 # add calulated offset to start adress of matrix
lw $t3, 0($t3) # load value at calulated adress
mult $t2, $t3 # power * (i-th element in matrx (always in first row))
mflo $t4 # get result in $t4
mult $t4, $v0 # multiply calcDet-result with calculated stuff
mflo $t4 # get result in $t4
add $s0, $s0, $t4 # add to sum
addi $t0, $t0, 1 # $t0++ or i++
j calcDetLoop
calcDetLoopDone: # loop finished, calculated all matrixes
addi $v0, $s0, 0 # copy sum into return register
lw $ra, 0($sp) # load return adress from stack
addi $sp, $sp, 4 # get some space on stack
jr $ra
###################################
###################################
# Extracts _one_ (N-1) matrix from a
# NxN matrix. The argument
# $a2 says which (N-1) matrix should
# be returned.
# expects: adress of array with N^2 elements in $a0
# dimension of matrix in $a1
# index of the smaller matrix (0-based) in $a2
# returns adress of (N-1) matrix in $v0
###################################
# Documentation
# $a0 -> matrix
# $a1 -> dim
# $a2 -> index of matrix that should be returned
# ----------------
# $s0 -> dim - 1
# $s1 -> counter for the current position in the SOURCE matrix
# $s2 -> counter for the current position in the TARGET matrix
reduceMatrix:
addi $s0, $a1, -1 # $s0 = dim - 1
mult $s0, $s0 # $s0*$s0 or
# (N-1)^2 or (dim-1)^2
# is also the size of the
# new matrix
mflo $t1 # get result into $t1
# $t1 contains now the number of words required
addi $s1, $a0, 0 # copy start adress of source matrix in $s1
addi $s2, $s7, 0 # save current position of heap pointer in $s2
addi $v0, $s7, 0 # copy target array adress in return register
addi $t0, $0, 4 # set $t0 = 4
mult $t1, $t0 # multiply $t0(=4) * $t1(=(dim-1)^2)
# -> amount of necessary bytes
mflo $t0 # copy result in $t0
add $s7, $s7, $t0 # get (N-1)^2 space of heap
addi $t0, $0, 4 # set $t0 = 4
mult $a1, $t0 # $a1(=dim)*$t0(=4)
# number of bytes that must be skipped to
# skip the first row of source matrix
mflo $t0
add $s1, $s1, $t0 # skip dim-elements or
# skip the first row of source matrix
addi $t0, $s0, 0 # initialize counter for loop 1; used as i
add $t2, $t0, $a2 # $t2 = $t0 + $a2 or
# $t2 = i + index
reduceMatrixLoop1: # loop 1
beq $t2, $t0, reduceMatrixLoop1Done
# while index != i
lw $t1, 0($s1) # load next entry from source matrix in $t1
sw $t1, 0($s2) # store the entry in the target matrix
addi $s1, $s1, 4 # increase pointer $s1 = $s1 + 4
addi $s2, $s2, 4 # increase pointer $s2 = $s2 + 4
addi $t0, $t0, 1 # $t0 = $t0 + 1 or
# $t0++ (i++)
j reduceMatrixLoop1 # jump up to the beginning of the loop
reduceMatrixLoop1Done: # endloop 1
reduceMatrixLoop2: # loop 2
mult $a1, $a1
mflo $t1
beq $t0, $t1, reduceMatrixLoop2Done
# while i < dim^2
addi $s1, $s1, 4 # skip one element in SOURCE matrix
addi $t0, $t0, 1 # $t0 = $t0 + 1 or
# $t0++ or i++
mult $a1, $a1 # $a1^2 or dim^2
mflo $t2 # get the result in $t2
sub $t2, $t2, 1 # sub 1 from $t2, because I want to compare
# it with $t0 (0-based) or
# (dim^2)-1
sub $t2, $t2, $t0 # $t2-$t0 or (dim^2)-1-i
# if
slt $t3, $t2, $s0 # (dim^2)-1-i < dim-1 or
# if $t3 == 1, you reached the last
# row and already skipped
beq $t3, $0, reduceMatrixLoop2Else
# jumps, if (dim-1)^2 - i < dim - 1 is false
# in human words: if the programm
# is NOT in the last row of the source matrix
# if case
# copy the last elements of source into target and exit function! :)
mult $a1, $a1 # dim^2
mflo $t2 # get result in $t2
reduceMatrixLoop2Loop1:
beq $t2, $t0, reduceMatrixLoop2Done
# jump if dim^2-1 == i or jump if
# end of source matrix is reached
lw $t1, 0($s1) # load next entry from source matrix in $t1
sw $t1, 0($s2) # store the entry in the target matrix
addi $s1, $s1, 4 # increase pointer $s1 = $s1 + 4
addi $s2, $s2, 4 # increase pointer $s2 = $s2 + 4
addi $t0, $t0, 1 # $t0 = $t0 + 1 or
# $t0++ or i++
j reduceMatrixLoop2Loop1
# jump up again, because its a loop!
j reduceMatrixLoop2Endif
# leave if case
# never used because if loop is finished
# it will jump to the end of the function
reduceMatrixLoop2Else: # else case
# copy dim - 1 elements
add $t2, $t0, $s0 # $t2 = $t0(=i) + $s0(=dim-1)
reduceMatrixLoop2ElseLoop:
beq $t2, $t0, reduceMatrixLoop2
# if $t2 = $t0 jump to main loop
lw $t1, 0($s1) # load next entry from source matrix in $t1
sw $t1, 0($s2) # store the entry in the target matrix
addi $s1, $s1, 4 # increase pointer $s1 = $s1 + 4
addi $s2, $s2, 4 # increase pointer $s2 = $s2 + 4
addi $t0, $t0, 1 # $t0 = $t0 + 1 or
# $t0++ or i++
j reduceMatrixLoop2ElseLoop
# jump up to the beginning of the loop
reduceMatrixLoop2Endif: # endif
addi $t0, $t0, 1 # $t0 = $t0 + 1 or
# $t0++ or i++
j reduceMatrixLoop2 # jump up to the beginning of the loop
reduceMatrixLoop2Done: # endloop 2
jr $ra # jump to caller function
# return value ($v0) is set at beginning
# of this function
###################################
###################################
###################################
ende:
#Ausgabe
la $a0 det
li $v0 4
syscall
move $a0, $s6
li $v0, 1
syscall
###################################
#Ende
li $v0, 10
syscall
