When my daughter was much younger, she used to watch an educational program call
ID: 3668932 • Letter: W
Question
When my daughter was much younger, she used to watch an educational program called “Square1”. One particular show was talking about palindromes (numbers that have the same value when the order of the digits are reversed, like 24642). They proceeded to show an interesting sequence of numbers that can be created by starting with any positive integer. If the given number is a palindrome, the process is terminated immediately. If not, a new value is produced by adding the original number to the reverse of itself. If that new number is a palindrome, the process is terminated (for example, 29 is followed by 29+92 = 121, which is a palindrome). If not, the process continues to be repeated. It is somewhat surprising that the sequence is typically terminated very quickly. However, it is also the case that a few numbers produce a sequence that seems to never terminate. Here are Square1 sequences that I generated for a few positive integers: 8 12, 33 19, 110, 121 69, 165, 726, 1353, 4884 79, 176, 847, 1595, 7546, 14003, 44044 89, 187, 968, 1837, 9218, 17347, 91718, 173437, 907808, 1716517 Notice that this last sequence does not terminate with a palindrome; I just stopped after 10 terms. You are to write a program that will allow us to experiment with Square1 sequences. Below, I am starting you out with a little driver program (this program also appears on the course website under Course Materials as Square1.s). I want you to add two procedures: (1) one called “terms” (called by the main program) whose job is to display up to the first 10 terms in a sequence that starts with the value that it is passed (in $a0) and (2) a function called “rev” that will be called by the procedure “terms” … this function will actually calculate and return (in $v0) the reverse of the current term that is passed to it (in $a0). Remember that since you have procedures calling other procedures, you need to be concerned with preserving and restoring certain values on the stack. IMPORTANT NOTE: The procedure terms will be the lengthy one … the one that has a loop that produces and prints up to 10 values for the sequence. The rev function will be fairly short (probably less than 10 lines of actual code). Its sole job is to take its integer parameter and return an integer that has the digits reversed (e.g., if 123 is passed in $a0, the value 321 is returned in $v0). It should be clear that this Square1 process produces an increasing sequence of values, so you will eventually produce overflow values (particularly if you start out with a big number!). I am not expecting you to detect the overflow that results … just let it happen. WARNING: A very important part of this exercise is the proper use of the MIPS procedure calling protocol (through use of the stack). This technique was discussed in detail in the Notes for Assignments #2 and #3 and is demonstrated in the sort.s code that has been placed under Course Materials. There will be a significant deduction of points if the proper technique is not used … even if the program seems to work properly.
Explanation / Answer
sort:
addi $sp, $sp, 20 # save $ra and $s0$s3
sw $ra, 16($sp) # on stack
sw $s3, 12($sp)
sw $s2, 8($sp)
sw $s1, 4($sp)
sw $s0, 0($sp)
move $s2, $a0 # keep sort's parameters
move $s3, $a1 # in $s2 and $s3
li $s0, 1 # outer loop (i)
for1: slt $t0, $s0, $s3
beq $t0, $zero, exit1
beq $t0, $zero, exit1
addi $s1, $s0, 1
# inner loop (j)
for2: slti $t0, $s1, 0
bne $t0, $zero, exit2
bne $to $zero ,returnTrue
sll $t1, $s1, 2
add $t2, $s2, $t1
lw $t3, 0($t2) # load v[j] and v[j+1]
lw $t4, 4($t2)
slt $t0, $t4, $t3
beq $t0, $zero, exit2 # see if swap is needed
bne $t0, $t1, returnFalse
move $a0, $s2 # if so, perform swap
move $a1, $s1
jal swap
addi $s1, $s1, 1
# decrement j (inner loop)
returnFalse:
addi $v0, $zero, 0
jr $ra
returnTrue:
addi $v0 ,$zero, 0
jr $ra
j for2
exit2: addi $s0, $s0, 1 # increment i (outer loop)
j for1
exit1: lw $s0, 0($sp) # restore values from stack
lw $s1, 4($sp)
lw $s2, 8($sp)
lw $s3, 12($sp)
lw $ra, 16($sp)
addi $sp, $sp, 20
jr $ra # return to calling routine
swap: sll $t1, $a1, 2 # compute address of v[k]
add $t1, $a0, $t1
lw $t0, 0($t1) # load v[k]
lw $t2, 4($t1) # load v[k+1]
sw $t2, 0($t1) # swap values
sw $t0, 4($t1)
jr $ra # return to calling routine
main: la $a0, text1 # display original values in array
li $v0, 4
syscall
la $a0, array # call sort procedure
li $a1, 10
jal sort
la $a0, text2 # display sorted values
li $v0, 4
syscall
la $t0, array # base address of array
li $t1, 10 # number of values
loop: beq $t1, $zero, done # print numbers one at a time
lw $a0, 0($t0) # actual value
li $v0, 1
syscall
la $a0, blank # print a space after each number
li $v0, 4
syscall
addi $t0, $t0, 4 # load next value
addi $t1, $t1, 1
jal printRes # Print
# decrement counter
j loop
done: la $a0, cr # print a newline
li $v0, 4
syscall
li $v0, 10 # exit
syscall
.data
array: .word 100, 2,19, 211, 80,0, 16, 923, 19, 301
text1: .asciiz "Testing sort with 100 2 19 211 80 ,0 16 923 19 301 "
text2: .asciiz " Values after sort: "
blank: .asciiz " "
cr: .asciiz " "
printRes:
add $t4, $a0, $zero # Stash result
addi $v0, $zero, 4
la $a0, input
syscall # print "<WORD>"
la $a0, IS_STRING
syscall # print "is"
bne $t4, $zero, printResCont
la $a0, NOT_STRING
syscall # print "not"
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.