Calculating the Square-root of Floating Numbers using Newton's Method
#; Program description: Utilize the MIPS assembly language to write four required
#; functions. Each function will have different purpose. In the end, this program
#; would be able to calculate the value using Newton's method and sort the list data
#; in an ascending order!
.data
#; System Service Codes
SYSTEM_EXIT = 10
SYSTEM_PRINT_INTEGER = 1
SYSTEM_PRINT_FLOAT = 2
SYSTEM_PRINT_STRING = 4
#; Function Input Data
squareRootValue1: .word 1742
squareRootValue2: .word 4566
floatSquareRootValue1: .float 15135.0
floatSquareRootValue2: .float 911560.50
floatTolerance1: .float 0.01
floatTolerance2: .float 0.001
printArray: .word 1, 1, 1, 1, 1, 1
.word 1, 0, 0, 0, 0, 1
.word 1, 0, 0, 0, 0, 1
.word 1, 0, 0, 0, 0, 1
.word 1, 0, 0, 0, 0, 1
.word 1, 1, 1, 1, 1, 1
.word 1, 1
PRINT_ARRAY_LENGTH = 38
arrayValues: .word 377, 148, 641, -486, 828, 456, 192, -742, -658, -139
.word 801, -946, 325, 916, 982, 902, -809, 858, -510, -713
.word -309, 515, 587, 320, 994, 528, -617, -515, -123, 294
.word 644, -339, 842, -441, -557, 58, 773, 694, 78, -744
.word -350, -424, -514, -679, 402, -924, -178, 315, 509, 173
.word 44, -80, -340, 905, -840, -210, 671, -755, -809, 731
.word -936, -414, 627, -565, -749, -804, -456, -236, 933, 961
.word -675, -9, 653, 581, -567, 916, 738, 343, 684, -184
.word -789, -400, -941, 145, 933, 230, -236, 880, 646, -926
.word 982, 221, -451, -783, 331, -157, 193, 940, -818, 270
ARRAY_LENGTH = 100
#; Labels
endLabel: .asciiz ".\n"
newLine: .asciiz "\n"
space: .asciiz " "
squareRootLabel1: .asciiz "The square root of 1742 is "
squareRootLabel2: .asciiz "The square root of 4566 is "
squareRootFloatLabel1: .asciiz "The square root of 15135.0 is "
squareRootFloatLabel2: .asciiz "The square root of 911560.50 is "
printArrayLabel: .asciiz "\nPrint Array Test:\n"
unsortedLabel: .asciiz "\nUnsorted List:\n"
sortedLabelAscending: .asciiz "\nSorted List (Ascending):\n"
.text
#; Function 1: Integer Square Root Estimation
#; Estimates the square root using Newton's Method
#; Argument 1 ($a0): Integer value to find the square root of
#; Returns: The estimated square root as an integer
.globl estimateIntegerSquareRoot
.ent estimateIntegerSquareRoot
estimateIntegerSquareRoot:
#; New Estimate = (Old + Value/Old)/2
move $t0, $a0 # Old Estimate
estimationLoop:
divu $t1, $a0, $t0 # Value/Old
add $t1, $t1, $t0 # Value/Old + Old
div $t1, $t1, 2 # (Value/Old + Old)/2
sub $t2, $t0, $t1 # Difference
move $t0, $t1 # old = new
# Only exit if |difference| <= 1
blt $t2, -1, estimationLoop
bgt $t2, 1, estimationLoop
move $v0, $t0
jr $ra
.end estimateIntegerSquareRoot
#; Function 2: Float Square Root Estimation
#; Estimates the square root using Netwon's Method
#; Argument 1 ($f12): Float value to find the square root of
#; Argument 2 ($f14): Float value representing the tolerance level to stop at
#; Returns: The estimated square root as a float
#; Floating Point Comparison
#; Use c.lt.s FRsrc1, FRsrc2 to set the comparison flag
#; Use bc1t label to branch if the comparison was true
#; Example:
#; c.lt.s $f0, $f1
#; bc1t estimateLoop #; Branch if $f0 < $f1
#; In this version of MIPS, there is no greater than comparisons
.globl estimateFloatSquareRoot
.ent estimateFloatSquareRoot
estimateFloatSquareRoot:
#; New Estimate = (Old + Value/Old)/2
mov.s $f0, $f12 # Old estimate
li $t0, 2 # load 2
mtc1 $t0, $f2 # move to f2
cvt.s.w $f2, $f2 # convert to float
fltEstLoop:
div.s $f1, $f12, $f0 # Value/ Old
add.s $f1, $f1, $f0 # Value/ Old + Old
div.s $f1, $f1, $f2 # (Value/Old + Old)/2
sub.s $f3, $f0, $f1 # difference
mov.s $f0, $f1 # old = new
# Only exit if |difference| <= tolerance
abs.s $f3, $f3 # take absolute value
c.lt.s $f14, $f3
bc1t fltEstLoop
jr $ra
.end estimateFloatSquareRoot
#; Function 3: Print Integer Array
#; Prints the elements of the array to the terminal
#; On each line, output a number of values equal to the square root of the total number of elements
#; Use estimateIntegerSquareRoot to determine how many elements should be printed on each line
#; Argument 1: Address of array to print
#; Argument 2: Integer count of the number of elements in the array
.globl printIntegerArray
.ent printIntegerArray
printIntegerArray:
#; Remember to push and pop $ra for non-leaf functions
addi $sp, $sp, -16 # allocate space for pushing registers
sw $ra, 0($sp) # push ra
sw $s0, 4($sp) # push s0
sw $s1, 8($sp) # push s1
sw $s2,12($sp) # push s2
move $s0, $a0 # preserve array pointer
move $s1, $a1 # preserve number of elements
move $a0, $a1 # pass count of elements
jal estimateIntegerSquareRoot # estimate number of elements in line
move $s2, $v0 # save in s2
move $t2, $s2 # start counter for rows
printRow:
move $t3, $s2 # start counter for columns
printCol:
lw $a0, 0($s0) # load value from array
li $v0, SYSTEM_PRINT_INTEGER # print the integer
syscall
addi $s0, $s0, 4 # advance to next element
li $v0, SYSTEM_PRINT_STRING # print a space
la $a0, space
syscall
addi $s1, $s1, -1 # decrement values to print
addi $t3, $t3, -1 # decrement columns to print
bnez $t3, printCol # repeat while not zero
li $v0, SYSTEM_PRINT_STRING # print a newline
la $a0, newLine
syscall
addi $t2, $t2, -1 # decrement rows to print
bnez $t2, printRow # repeat while not zero
beqz $s1, printEnd # if no more values to print, return
printLast:
lw $a0, 0($s0) # load value from array
li $v0, SYSTEM_PRINT_INTEGER # print the integer
syscall
li $v0, SYSTEM_PRINT_STRING # print a space
la $a0, space
syscall
addi $s0, $s0, 4 # advance to next element
addi $s1, $s1, -1 # decrement values to print
bnez $s1, printLast # repeat loop if not zero
li $v0, SYSTEM_PRINT_STRING # print a newline
la $a0, newLine
syscall
printEnd:
lw $ra, 0($sp) # pop ra
lw $s0, 4($sp) # pop s0
lw $s1, 8($sp) # pop s1
lw $s2,12($sp) # pop s2
addi $sp, $sp, 16 # remove allocated space
jr $ra
.end printIntegerArray
#; Function 4: Integer Comb Sort (Ascending)
#; Uses the comb sort algorithm to sort a list of integer values in ascending order
#; Argument 1: Address of array to sort
#; Argument 2: Integer count of the number of elements in the array
#; Returns: Nothing
.globl sortList
.ent sortList
sortList:
move $t4, $a1 # gapsize = n
sortLoop:
mul $t4, $t4, 10 # gapsize = gapsize*10
divu $t4, $t4, 13 # gapsize = gapsize*10/13
bnez $t4, skip # if(gapsize == 0)
li $t4, 1 # gapsize = 1
skip:
li $t5, 0 # swapsDone = 0
li $t6, 0 # i = 0
sub $t7, $a1, $t4 # t7 = n - gapsize
move $t2, $a0 # t2 = &array[0]
sll $t3, $t4, 2 # t3 = gapsize * 4
add $t3, $t3, $t2 # t3 = &array[gapsize]
for: # for ( i = 0, i < n – gapsize, i++ )
bge $t6, $t7, endfor # i >= n - gapsize, end for
lw $t0, 0($t2) # temp = array[i]
lw $t1, 0($t3) # load array[i + gapsize]
ble $t0, $t1, next # if(array[i] > array[i+gapsize])
# swap
sw $t1, 0($t2) # array[i] = array[i + gapsize]
sw $t0, 0($t3) # array[i + gapsize] = temp
addi $t5, $t5, 1 # swapsDone++
next:
addi $t2, $t2, 4 # advance to array[i+1]
addi $t3, $t3, 4 # advance to array[i+gapsize+1]
addi $t6, $t6, 1 # i++
b for # repeat for
endfor:
# if(gapsize == 1 and swapsDone == 0)
bne $t4, 1, sortLoop
bnez $t5, sortLoop
jr $ra
.end sortList
#; ----------------------------------------------------------------------------------------
#; ------------------------------------DO NOT CHANGE MAIN----------------------------------
#; ----------------------------------------------------------------------------------------
.globl main
.ent main
main:
#; Square Root Test 1
li $v0, SYSTEM_PRINT_STRING
la $a0, squareRootLabel1
syscall
lw $a0, squareRootValue1
jal estimateIntegerSquareRoot
move $a0, $v0
li $v0, SYSTEM_PRINT_INTEGER
syscall
li $v0, SYSTEM_PRINT_STRING
la $a0, endLabel
syscall
#; Square Root Test 2
li $v0, SYSTEM_PRINT_STRING
la $a0, squareRootLabel2
syscall
lw $a0, squareRootValue2
jal estimateIntegerSquareRoot
move $a0, $v0
li $v0, SYSTEM_PRINT_INTEGER
syscall
li $v0, SYSTEM_PRINT_STRING
la $a0, endLabel
syscall
#; Float Square Root Test 1
li $v0, SYSTEM_PRINT_STRING
la $a0, squareRootFloatLabel1
syscall
l.s $f12, floatSquareRootValue1
l.s $f14, floatTolerance1
jal estimateFloatSquareRoot
li $v0, SYSTEM_PRINT_FLOAT
mov.s $f12, $f0
syscall
li $v0, SYSTEM_PRINT_STRING
la $a0, endLabel
syscall
#; Float Square Root Test 2
li $v0, SYSTEM_PRINT_STRING
la $a0, squareRootFloatLabel2
syscall
l.s $f12, floatSquareRootValue2
l.s $f14, floatTolerance2
jal estimateFloatSquareRoot
li $v0, SYSTEM_PRINT_FLOAT
mov.s $f12, $f0
syscall
li $v0, SYSTEM_PRINT_STRING
la $a0, endLabel
syscall
#; Print Array Test
li $v0, SYSTEM_PRINT_STRING
la $a0, printArrayLabel
syscall
la $a0, printArray
li $a1, PRINT_ARRAY_LENGTH
jal printIntegerArray
#; Print Unsorted Array
li $v0, SYSTEM_PRINT_STRING
la $a0, unsortedLabel
syscall
la $a0, arrayValues
li $a1, ARRAY_LENGTH
jal printIntegerArray
#; Print Sorted Array (Ascending)
li $v0, SYSTEM_PRINT_STRING
la $a0, sortedLabelAscending
syscall
la $a0, arrayValues
li $a1, ARRAY_LENGTH
jal sortList
la $a0, arrayValues
li $a1, ARRAY_LENGTH
jal printIntegerArray
#; End Program
li $v0, SYSTEM_EXIT
syscall
.end main