Question

MIPS

Using the Collatz conjecture, which is based on this sequence of values of n:

given any positive integer n,

while n != 1,

if n is even n ← (n/2)

else

n ← 3n + 1

The conjecture is that for every given initial n, the sequence will end in 1. In fact, if n > 2, it will end in the sequence 4, 2 and 1

Write a MIPS program to allow the user to try out the conjecture. The user will enter an initial n as the first argument on the command line, as such:

$ ./collatz 42

To get that argument (argv[1] in C or C++) from the command line, remember that main() follows the MIPS convention for arguments and that there’s a function atoi() in the standard C library that converts a char * to an int. Use unsigned arithmetic. Print out n (one value per line with no extra text or spaces) on each iteration of the loop. Print an error message on standard output if the argument is missing or if there is more than one argument. Be sure to stop the program and print an error message if the unsigned value of 3n + 1 cannot be represented in 32 bits, since that would be an error in the calculation. How would you test for this?

Answer 1

collatz_common.s

.data
spaceStr: .asciiz " "
newlineStr: .asciiz "\n"
inputStr: .asciiz "Enter the number to start the Collatz function: "
inputErrorStr: .asciiz "The number entered is invalid. Please enter a positive number.\n"
outputStr: .asciiz "\nStopping time: "
savedErrorStr: .asciiz "Warning: Value of saved registers were not preserved across function call.\n"
dneStr: .asciiz "You should not be executing common.s! Program exiting.\n"

.text
# Don't run this file!
la $a0, dneStr
li $v0, 4
syscall
li $v0, 10
syscall
  
# Prints the value in $a0, followed by a space. May be useful in debugging.
print_value:
   li $v0, 1
   syscall
   la $a0, spaceStr
   li $v0, 4
   syscall
   jr $ra

# Reads an int (>0) and returns it in $v0
read_input:
   la $a0, inputStr   # Read integer
   li $v0, 4
   syscall
   li $v0, 5
   syscall
   li $t0, 1
   slt $t1, $v0, $t0   # Check that integer is positive
   bne $t1, $0, invalid_input
   jr $ra
invalid_input:           # If input invalid, print error msg and exit
   la $a0, inputErrorStr
   li $v0, 4
   syscall
   li $v0, 10
   syscall

# $a0 = number (>0), $a1 = function ptr
execute_function:
   # Store return address
   addiu $sp, $sp, -4
   sw $ra, 0($sp)
   # Put values in saved registers
   li $s0, -11
   li $s1, -12
   li $s2, -13
   li $s3, -14
   li $s4, -15
   li $s5, -16
   li $s6, -17
   move $s7, $sp
  
   jalr $a1       # Call function
   move $t0, $v0       # Store number of iterations in $t0
   la $a0, outputStr
   li $v0, 4
   syscall
   move $a0, $t0       # Print number of iterations
   li $v0, 1
   syscall
   la $a0, newlineStr
   li $v0, 4
   syscall
  
   # Check that values in saved registers have been preserved
   li $t0, -11
   bne $s0, $t0, saved_not_equal
   li $t0, -12
   bne $s1, $t0, saved_not_equal
   li $t0, -13
   bne $s2, $t0, saved_not_equal
   li $t0, -14
   bne $s3, $t0, saved_not_equal
   li $t0, -15
   bne $s4, $t0, saved_not_equal
   li $t0, -16
   bne $s5, $t0, saved_not_equal
   li $t0, -17
   bne $s6, $t0, saved_not_equal
   bne $s7, $sp, saved_not_equal
  
   # Return to parent function
   lw $ra, 0($sp)
   addiu $sp, $sp, 4
   jr $ra          
saved_not_equal:
   la $a0, savedErrorStr
   li $v0, 4
   syscall
   lw $ra, 0($sp)
   addiu $sp, $sp, 4
   jr $ra

.globl main
.include "collatz_common.s"

main:
   jal read_input           # Get the number we wish to try the Collatz conjecture on
   move $a0, $v0           # Set $a0 to the value read
   la $a1, collatz_recursive   # Set $a1 as ptr to the function we want to execute
   jal execute_function       # Execute the function
   li $v0, 10           # Exit
   syscall
  

# Returns the stopping time of the Collatz function (the number of steps taken till the number reaches one)
# using an RECURSIVE approach. This means that if the input is 1, your function should return 0.
#
# The current value is stored in $a0, and you may assume that it is a positive number.
#
# Make sure to follow all function call conventions.
collatz_recursive:
   start:
       addi $sp $sp -8 # save space for two words
       sw $ra 4($sp) # save return address
       sw $s0 0($sp) # save $s0
       addi $t0 $0 1 # $t0 = 1
       addi $t1 $0 3 # $t1 = 3
       add $s0 $0 $0 # $s0 = 0
       beq $a0 $t0 fin # if $a0 = $t0 = 1, goto fin
       andi $t3 $a0 0x00000001 # $t0 = last digit of $a0
       bne $t3 $0 odd # if $t3 = 1, goto odd, otherwise continue to even
   even:
       srl $a0 $a0 1 # $a0 = $a0 / 2
       jal collatz_recursive # collatz_recursive($a0)
       add $s0 $v0 $0 # $s0 = collatz_recursive($a0)
       addi $s0 $s0 1 # $s0 += 1
       j fin # jump to fin
   odd:
       mult $a0 $t1 # $a0 * 3
       mflo $a0 # $a0 = $a0 * 3
       addi $a0 $a0 1 # $a0 += 1
       jal collatz_recursive # collatz_recursive($a0)
       add $s0 $v0 $0 # s0 += collatz_recursive($a0)
       addi $s0 $s0 1 # $s0 += 1
   fin:
       add $v0 $0 $s0 # $v0 = $s0
       lw $s0 0($sp) # restore $s0
       lw $ra 4($sp) # restore return address
       addi $sp $sp 8 $ # pop the stack frame
       jr $ra # return to caller