Last active
July 28, 2016 13:42
-
-
Save muhammadyaseen/b0c92ce68e3d1bfea9db to your computer and use it in GitHub Desktop.
Linear Equations Solver (Guassian-Jordan elimination) implemented in MIPS assembly language
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Linear Equations Solver using Guassian-Jordan elimination | |
# Syed Usama Jamil CS-037 | |
# Muhammad Yaseen CS-050 | |
# Project ID CA-03 | |
#=========================================================================== | |
.data | |
dimension : .byte 4 | |
#matrix : .float 1.0, 1.0, 2.0, 9.0, 2.0, 4.0, -3.0, 1.0, 3.0, 6.0, -5.0, 0.0 #pg 7 x=1,y=2,z=3 | |
matrix : .float 1.0, 2.0, 3.0, 4.0, 5.0, 2.0, 7.0, 8.0, 9.0, 10.0, 1.0, 12.0, 2.0, 14.0, 5.0, 5.0, 17.0, 18.0, 19.0, 2.0 #pg 7 x=1,y=2,z=3 | |
#matrix : .float 2.0, 1.0, 3.0, 1.0, 2.0, 6.0, 8.0, 3.0, 6.0, 8.0, 18.0, 5.0 #pg 7 x=3/10,y=2/5,z=0 | |
#matrix : .float 1.0, -2.0, 3.0, 7.0, 2.0, 1.0, 1.0, 4.0, -3.0, 2.0, -2.0, -10.0 #pg 7 x=2,y=-1,z=1 | |
results : .space 1000 #reserve 1000 bytes | |
result : .asciiz "Solution is : " | |
newline : .asciiz "\n" | |
zero : .float 0.0 | |
.text | |
main: | |
#get the address of input matrix system | |
la $t0, matrix | |
#get the dimension ( NxN ) of matrix | |
lw $t1, dimension | |
addi $s6,$t1,1 #for offset calc | |
#Loop control variable, goes from 1 to n, named 'j' in c code | |
li $t3, 0 | |
#loop for generation of triangular matrix | |
gen_tri_mat: | |
addi $t3, $t3, 1 #increment control var | |
bgt $t3, $t1, end_gen_tri_mat #if current_dim > dim, then we end loop | |
li $t2, 0 #control var for inner_Loop1,, named 'i' in c code | |
inner_Loop1: #goes from 1 to n | |
addi $t2, $t2, 1 #increment control var | |
bgt $t2, $t1, end_inner_Loop1 | |
sgt $t4, $t2, $t3 #Set $t5 if i > j i.e if $t3 > $t2 | |
beq $t4,$0, inner_Loop1 # we want $t4 to be 1, i.e. NOT equal to zero.. designated ' if (i>j)' in c code | |
#if we reach here , it means that if condition was true i.e i>j is true | |
# c = A[i][j] / A[j][j] or A[t2][t3] / A[t3][t3] | |
# load A[i][j], i = $t2; j = $t3 | |
#now we load the Matrix element A[row][col] | |
#=============================================================================== | |
#generic formula (for NxN matrix) for offset value is : N*s*(row-1) + s*(col-1) | |
# where | |
# N is the matrix dimension | |
# s is the size of ONE element of matrix e.g 4 bytes for int, 1 byte for char | |
#=============================================================================== | |
# in code we have row = $t2, col = $t3 | |
#calc (row - 1) | |
addi $t4, $t2, -1 | |
#calc (col - 1) | |
addi $t5, $t3, -1 | |
# s = 4 bytes for IEEE 754 Single Precision Floating Point | |
# calc s*(col-1) | |
li $t6, 4 | |
mul $t5, $t5, $t6 | |
#calc s*(row-1) | |
mul $t4, $t4,$t6 | |
#calc N*s*(row-1) | |
mul $t4, $t4,$s6 | |
#add the two products | |
add $t7, $t5,$t4 | |
#now $t7 has final offset value to be added to the array starting | |
#Let add the value to start address | |
add $t7,$t7,$t0 | |
#now t7 has correct mem address of element A[r][c], Let's laod it -- A[i][j] loaded | |
l.s $f0, 0($t7) | |
## reset all used intermediate registers so that the next address could be calculated. | |
li $t4, 0 | |
li $t5, 0 | |
li $t7, 0 | |
#=========================================================================== | |
# load A[j][j] ; Here j = t3 # | |
#=========================================================================== | |
#calc (row - 1) | |
addi $t4, $t3, -1 | |
#calc (col - 1) | |
addi $t5, $t3, -1 | |
# s = 4 bytes for IEEE 754 Single Precision Floating Point | |
# calc s*(col-1) | |
li $t6, 4 | |
mul $t5, $t5, $t6 | |
#calc s*(row-1) | |
mul $t4, $t4,$t6 | |
#calc N*s*(row-1) | |
mul $t4, $t4,$s6 | |
#add the two products | |
add $t7, $t5,$t4 | |
#now $t7 has final offset value to be added to the array starting | |
#Let add the value to start address | |
add $t7,$t7,$t0 | |
#now t7 has correct mem address of element A[r][c], Let's laod it -- A[j][j] loaded | |
l.s $f1, 0($t7) | |
## reset all used intermediate registers so that the next address could be calculated. | |
li $t4, 0 | |
li $t5, 0 | |
li $t7, 0 | |
#============================================================== | |
# Now $f0 = A[i][j] AND $f1 = A[j][j] , we need to divide now | |
#============================================================== | |
div.s $f3, $f0, $f1 #this is our 'C' !!! Causing NaN | |
# second inner loop , goes from k=1 to n+1 | |
addi $s0,$t1, 1 #set s0 to n+1 | |
li $s1, 0 #loop control var | |
inner_Loop2: | |
addi $s1, $s1, 1 | |
bgt $s1,$s0, end_inner_Loop2 #compare with n+1 | |
# A[i][k]=A[i][k]-c*A[j][k]; | |
#tast breakdown | |
# 1. Load A[i][k] and A[j][k] | |
# 2. calc C*A[j][k] | |
# 3. calc x = A[i][k]-c*A[j][k] | |
# 4. store x on A[i][k] ... for this we need Address of A[i][k]th element | |
# task 1 : Load A[i][k] ; i = t2 k = s1 | |
#calc (row - 1) | |
addi $t4, $t2, -1 | |
#calc (col - 1) | |
addi $t5, $s1, -1 | |
# s = 4 bytes for IEEE 754 Single Precision Floating Point | |
# calc s*(col-1) | |
li $t6, 4 | |
mul $t5, $t5, $t6 | |
#calc s*(row-1) | |
mul $t4, $t4,$t6 | |
#calc N*s*(row-1) | |
mul $t4, $t4,$s6 | |
#add the two products | |
add $t7, $t5,$t4 | |
#now $t7 has final offset value to be added to the array starting | |
#Let add the value to start address | |
add $t7,$t7,$t0 | |
#now t7 has correct mem address of element A[r][c], Let's laod it | |
l.s $f4, 0($t7) | |
#save address of A[i][k], bcz we have to store it back | |
move $s7, $t7 | |
## reset all used intermediate registers so that the next address could be calculated. | |
li $t4, 0 | |
li $t5, 0 | |
li $t7, 0 | |
#==== loaded A[i][k] === | |
# load A[j][k] | |
#calc (row - 1) | |
addi $t4, $t3, -1 | |
#calc (col - 1) | |
addi $t5, $s1, -1 | |
# s = 4 bytes for IEEE 754 Single Precision Floating Point | |
# calc s*(col-1) | |
li $t6, 4 | |
mul $t5, $t5, $t6 | |
#calc s*(row-1) | |
mul $t4, $t4,$t6 | |
#calc N*s*(row-1) | |
mul $t4, $t4,$s6 | |
#add the two products | |
add $t7, $t5,$t4 | |
#now $t7 has final offset value to be added to the array starting | |
#Let add the value to start address | |
add $t7,$t7,$t0 | |
#now t7 has correct mem address of element A[r][c], Let's laod it | |
l.s $f5, 0($t7) | |
## reset all used intermediate registers so that the next address could be calculated. | |
li $t4, 0 | |
li $t5, 0 | |
li $t7, 0 | |
# now $f4 = A[i][k] and $f5 = A[j][k] | |
# 2. calc C*A[j][k] | |
#mul.s $f6, $f4, $f5 #possible error : $f4 shoud be $f3 | |
mul.s $f6, $f3, $f5 #attempt at rectifying error | |
# 3. calc x = A[i][k]-c*A[j][k] | |
sub.s $f7, $f4,$f6 | |
# 4. store x on A[i][k] ... for this we need Address of A[i][k]th element. s7 has addr of A[i][k] | |
s.s $f7, 0($s7) | |
b inner_Loop2 | |
end_inner_Loop2: | |
b inner_Loop1 | |
end_inner_Loop1: | |
b gen_tri_mat | |
end_gen_tri_mat: | |
## reset all used intermediate registers so that the next address could be calculated. | |
## (added this as precaution, following 3 lines were NOT present in initial attempt | |
li $t4, 0 | |
li $t5, 0 | |
li $t7, 0 | |
# Now we're done with generation of Upper triangular matrix, it's time to substitute back in! | |
# Back substitution code | |
# === START code for caclulating X[n] ===== | |
# calc x[n]=A[n][n+1]/A[n][n], where n is the dimension | |
# load A[n][n] ... n is in t1 | |
#calc (row - 1) | |
addi $t4, $t1, -1 | |
#calc (col - 1) | |
addi $t5, $t1, -1 | |
# s = 4 bytes for IEEE 754 Single Precision Floating Point | |
# calc s*(col-1) | |
li $t6, 4 | |
mul $t5, $t5, $t6 | |
#calc s*(row-1) | |
mul $t4, $t4,$t6 | |
#calc N*s*(row-1) | |
mul $t4, $t4,$s6 | |
#add the two products | |
add $t7, $t5,$t4 | |
#now $t7 has final offset value to be added to the array starting | |
#Let add the value to start address | |
add $t7,$t7,$t0 | |
#now t7 has correct mem address of element A[r][c], Let's laod it | |
l.s $f9, 0($t7) | |
## reset all used intermediate registers so that the next address could be calculated. | |
li $t4, 0 | |
li $t5, 0 | |
li $t7, 0 | |
#======================== | |
# load A[n][n+1] | |
#======================== | |
addi $s2, $t1, 1 #set s2 to n+1 | |
#calc (row - 1) | |
addi $t4, $t1, -1 | |
#calc (col - 1) | |
addi $t5, $s2, -1 | |
# s = 4 bytes for IEEE 754 Single Precision Floating Point | |
# calc s*(col-1) | |
li $t6, 4 | |
mul $t5, $t5, $t6 | |
#calc s*(row-1) | |
mul $t4, $t4,$t6 | |
#calc N*s*(row-1) | |
mul $t4, $t4,$s6 | |
#add the two products | |
add $t7, $t5,$t4 | |
#now $t7 has final offset value to be added to the array starting | |
#Let add the value to start address | |
add $t7,$t7,$t0 | |
#now t7 has correct mem address of element A[r][c], Let's laod it | |
l.s $f10, 0($t7) | |
## reset all used intermediate registers so that the next address could be calculated. | |
li $t4, 0 | |
li $t5, 0 | |
li $t7, 0 | |
#perform division (this ONLY performs the division op, but DOESNOT store result back in x[n] | |
div.s $f11, $f10, $f9 | |
# Let $t9 be the starting addr of result vector | |
la $t9, results | |
#offset = s*(i-1) | |
#for this step i = n = dimension = $t1 | |
add $t8, $0, $t1 | |
addi $t8, $t8, -1 | |
mul $t8, $t8, 4 | |
#add offset to starting addr of results vector | |
add $t8, $t8, $t9 | |
#store X[n] | |
s.s $f11,0($t8) | |
#reset t8 | |
li $t8, 0 | |
# === END code for caclulating X[n] ===== | |
## Usama Work Start | |
# backward substitution | |
#reset two control vars , this clears values which COULD be present | |
li $t2, 0 | |
li $t3, 0 | |
#Loop control variable, goes from n-1 to 1, named 'i' in c code | |
addi $t2,$t1,0 | |
#loop for backward substitution | |
back_sub: | |
addi $t2, $t2, -1 #decrement control var | |
blt $t2, 1, end_back_sub #if loop control variable is less than 1, then we end loop | |
# j = i + 1, $t3 = $t2 + 1 | |
li $t3, 0 | |
addi $t3, $t2, 0 #control var for inner_Loop1,, named 'j' in c code | |
#li $f15,0 #will contain sum of sum <-- sum+A[i][j]*x[j] | |
#add.s $f15,$0,$0 | |
#commented above two lines, assume $f15 has 0 already | |
#sum = 0 | |
l.s $f15, zero | |
inner_Loop_Us: #goes from i+1 to n | |
addi $t3, $t3, 1 #increment control var | |
bgt $t3, $t1, end_inner_Loop_Us | |
# sum=sum+A[i][j]*x[j] or A[t2][t3]*x[t3] | |
# load A[i][j], i = $t2; j = $t3 | |
#now we load the Matrix element A[row][col] | |
#=============================================================================== | |
#generic formula (for NxN matrix) for offset value is : N*s*(row-1) + s*(col-1) | |
# where | |
# N is the matrix dimension | |
# s is the size of ONE element of matrix e.g 4 bytes for int, 1 byte for char | |
#=============================================================================== | |
# in code we have row = $t2, col = $t3 | |
#calc (row - 1) | |
addi $t4, $t2, -1 | |
#calc (col - 1) | |
addi $t5, $t3, -1 | |
# s = 4 bytes for IEEE 754 Single Precision Floating Point | |
# calc s*(col-1) | |
li $t6, 4 | |
mul $t5, $t5, $t6 | |
#calc s*(row-1) | |
mul $t4, $t4,$t6 | |
#calc N*s*(row-1) | |
mul $t4, $t4,$s6 | |
#add the two products | |
add $t7, $t5,$t4 | |
#now $t7 has final offset value to be added to the array starting | |
#Let add the value to start address | |
add $t7,$t7,$t0 | |
#now t7 has correct mem address of element A[r][c], Let's laod it -- A[i][j] loaded | |
l.s $f20, 0($t7) | |
## reset all used intermediate registers so that the next address could be calculated. | |
li $t4, 0 | |
li $t5, 0 | |
li $t7, 0 | |
#=========================================================================== | |
# multiply A[i][j]*x[j] ; Here j = t3 # | |
#=========================================================================== | |
#load x[j] | |
# Let $t9 be the starting addr of result vector | |
la $t9, results | |
#4 bytes = 1 SP FP num | |
li $t8, 4 | |
#offset = size*number | |
mul $t8, $t8, $s6 | |
#add offset to starting addr of results vector | |
add $t8, $t8, $t9 | |
l.s $f13,0($t8) # load address of $t3 in $f13 | |
# ======================= TEST CODE FOR x[j] loading ========================= | |
# Let $t9 be the starting addr of result vector | |
la $t9, results | |
#offset = s*(j-1) | |
#for this step j = $t3 | |
add $t8, $0, $t3 | |
addi $t8, $t8, -1 | |
mul $t8, $t8, 4 | |
#add offset to starting addr of results vector | |
add $t8, $t8, $t9 | |
#load X[n] | |
l.s $f13,0($t8) | |
#reset t8 | |
li $t8, 0 | |
# ======================== end test code ===================================== | |
mul.s $f14,$f20,$f13 # $s2 stores the product of two | |
# now performing 'sum=sum+A[i][j]*x[j]' where sum is represented by $s0 | |
add.s $f15,$f15,$f14 | |
#reset t8 | |
li $t8, 0 | |
b inner_Loop_Us | |
end_inner_Loop_Us: #inner_loop ends | |
# TODO: x[i]=(A[i][n+1]-sum)/A[i][i], | |
# where n is the dimension | |
# i = t2 | |
# sum = $s2 | |
#x[i]=(A[i][n+1]-sum)/A[i][i]; | |
#tast breakdown | |
# 1. Load A[i][i] and A[i][n+1] | |
# 2. calc (A[i][n+1]-sum) | |
# 3. calc x[i] = (A[i][n+1]-sum)/A[i][i] | |
# task 1 : Load A[i][i] and A[i][n+1] ; i = t2 | |
#======================== | |
# load A[i][i] | |
#======================== | |
#calc (row - 1) | |
addi $t4, $t2, -1 | |
#calc (col - 1) | |
addi $t5, $t2, -1 | |
# s = 4 bytes for IEEE 754 Single Precision Floating Point | |
# calc s*(col-1) | |
li $t6, 4 | |
mul $t5, $t5, $t6 | |
#calc s*(row-1) | |
mul $t4, $t4,$t6 | |
#calc N*s*(row-1) | |
mul $t4, $t4,$s6 | |
#add the two products | |
add $t7, $t5,$t4 | |
#now $t7 has final offset value to be added to the array starting | |
#Let add the value to start address | |
add $t7,$t7,$t0 | |
#now t7 has correct mem address of element A[r][c], Let's laod it | |
l.s $f16, 0($t7) | |
## reset all used intermediate registers so that the next address could be calculated. | |
li $t4, 0 | |
li $t5, 0 | |
li $t7, 0 | |
#======================== | |
# load A[i][n+1] | |
#======================== | |
addi $s2, $t1, 1 #set s2 to n+1 | |
#calc (row - 1) | |
addi $t4, $t2, -1 | |
#calc (col - 1) | |
addi $t5, $s2, -1 | |
# s = 4 bytes for IEEE 754 Single Precision Floating Point | |
# calc s*(col-1) | |
li $t6, 4 | |
mul $t5, $t5, $t6 | |
#calc s*(row-1) | |
mul $t4, $t4,$t6 | |
#calc N*s*(row-1) | |
mul $t4, $t4,$s6 | |
#add the two products | |
add $t7, $t5,$t4 | |
#now $t7 has final offset value to be added to the array starting | |
#Let add the value to start address | |
add $t7,$t7,$t0 | |
#now t7 has correct mem address of element A[r][c], Let's laod it | |
l.s $f17, 0($t7) | |
## reset all used intermediate registers so that the next address could be calculated. | |
li $t4, 0 | |
li $t5, 0 | |
li $t7, 0 | |
# task 2 : calc (A[i][n+1]-sum) | |
# sum = f15 | |
sub.s $f18,$f17,$f15 | |
# task 3 : calc x[i] = (A[i][n+1]-sum)/A[i][i] | |
#perform division, f19 has x[i] | |
div.s $f19, $f18, $f16 | |
# ======================= TEST CODE FOR x[i] SAVING ========================= | |
# Let $t9 be the starting addr of result vector | |
la $t9, results | |
#offset = s*(i-1) | |
#for this step i = $t2 | |
add $t8, $0, $t2 | |
addi $t8, $t8, -1 | |
mul $t8, $t8, 4 | |
#add offset to starting addr of results vector | |
add $t8, $t8, $t9 | |
#store X[n] | |
s.s $f19,0($t8) | |
#reset t8 | |
li $t8, 0 | |
# ======================== end test code ===================================== | |
#prints out statement | |
#li $v0, 4 | |
#la $a0, result | |
#syscall | |
##MY added lines | |
#li $v0, 2 | |
#mov.s $f12,$f19 | |
#syscall | |
##MY added lines end | |
b back_sub | |
end_back_sub: | |
# Now finally printing the results | |
# output prompt | |
li $v0, 4 | |
la $a0, result #prints out statement | |
syscall | |
#print new line | |
li $v0, 4 | |
la $a0, newline | |
syscall | |
#printing results loop | |
li $t2, 0 #control var for inner_Loop1,, named 'i' in c code | |
Output_Loop: #goes from 1 to n | |
addi $t2, $t2, 1 #increment control var | |
bgt $t2, $t1, End_Output_Loop | |
# print result | |
# ======================= TEST CODE FOR x[j] loading ========================= | |
# Let $t9 be the starting addr of result vector | |
la $t9, results | |
#offset = s*(j-1) | |
#for this step j = $t2 | |
add $t8, $0, $t2 | |
addi $t8, $t8, -1 | |
mul $t8, $t8, 4 | |
#add offset to starting addr of results vector | |
add $t8, $t8, $t9 | |
#load X[n] | |
l.s $f22,0($t8) | |
li $v0, 2 | |
mov.s $f12, $f22 | |
syscall | |
#reset t8 | |
li $t8, 0 | |
# ======================== end test code ===================================== | |
#print new line | |
li $v0, 4 | |
la $a0, newline | |
syscall | |
b Output_Loop | |
End_Output_Loop: | |
jr $ra |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment