Question

Euclid’s Elements (300 BC) shows that the greatest common divisor of two integers does not change if the smaller is subtracted from the larger.

Write a program (in MIPS assembly) that implements this algorithm to find the GCD of two integers. Follow this algorithm:

1. Call the two integers a and b.

2. If a and b are equal: stop: a is the GCD.

3. Subtract the smaller from the larger. Replace the larger with the result

4. Repeat steps 2 thru 4

The program asks the user for each of two integers (use exception handler services), then use the algorithm to compute the GCD, then write out the GCD. Then use service 10 to halt the program. You may wish to write the program in C first or perhaps create a structured flow chart before you write the assembler program. Assume that the user enters two positive integers:

Enter First Integer: 3791 Enter Second Integer: 8687 The GCD is: 17

Set MIPS settings to the following:

OFF Bare Machine OFF Enable Delayed Loads OFF Enable Delayed Branches ON Load Exception Handler OFF Enable Mapped IO ON Accept Pseudo Instructions

Set these options as specified or QtSpim will start up with options you don’t want. You may have to set the options, close QtSpim, and then restart it for the options to have an effect. Use only those instructions that have been discussed in the notes through chapter 22.

Include a register use table in the documentation at the top of your source program. The source program should be nicely formatted. Labels (symbolic addresses) should start in column one. Nearly every line of the program will have a meaningful comment. Labels start in column one. All mnemonics start in the same column, perhaps column 10. All comments should start in the same column, perhaps column 40. Make sure that the source file has no tab characters in it.

Answer 1

Requirement: As per the problem, we need to write a program (in MIPS assembly) that implements this algorithm to find the GCD of two integers.

Understanding: We need to follow below algorithm to find the GCD of two integers:

1. Call the two integers a and b.

2. If a and b are equal: stop: a is the GCD.

3. Subtract the smaller from the larger. Replace the larger with the result

4. Repeat steps 2 thru 4

The program asks the user for each of two integers (use exception handler services), then use the algorithm to compute the GCD, then write out the GCD. Then use service 10 to halt the program.

Solution: Below is the implementation of above problem.

# Start with data declarations
#
   .data
str1: .asciiz "Enter first integer n1: "
str2: .asciiz "Enter first integer n2: "
str3: .asciiz "The greatest common divisor of n1 and n2 is "
newline: .asciiz "\n"

.align 2

.globl main
.text

main:

# ---------------------------------------------------------
# Receiving two integer inputs from user
# ---------------------------------------------------------
    la $a0, str1           # load str1 address into $a0
    li $v0, 4              # load I/O code for string output
    syscall                # output str1

    li $v0, 5              # load I/O code for integer input
    syscall                # input integer n1 into $v0
    add $a1, $v0, $zero    # store n1 in $a1

    la $a0, str2           # load str2 address into $a0
    li $v0, 4              # load I/O code for string output
    syscall                # output str2

    li $v0, 5              # load I/O code for integer input
    syscall                # input integer n2 into $v0
    add $a2, $v0, $zero    # store n2 in $a2

# ---------------------------------------------------------
# Calling gcd
# ---------------------------------------------------------
    addi $sp, $sp, -8      # adjust stack for 2 items
    sw $a1, 4($sp)         # save argument1
    sw $a2, 0($sp)         # save argument2
    jal gcd                # jump to subroutine 'gcd'
    lw $a2, 0($sp)         # load argument2
    lw $a1, 4($sp)         # load argument1
    addi $sp, $sp, 4       # pop 1 item from the stack; reuse stack space for $s0
    add $s0, $v0, $zero    # $s0 = result from gcd
    sw $s0, 0($sp)         # save the result from gcd

# ---------------------------------------------------------
# Outputting Results
# ---------------------------------------------------------
    la $a0, str3           # load str3 address into $a0
    li $v0, 4              # load I/O code for string output
    syscall                # output str3
    li $v0, 1              # load I/O code for integer output
    add $a0, $s0, $zero    # $a0 = $s0; put gcd result in $a0 for output
    syscall                # output result from gcd
    la $a0, str4           # load str4 address into $a0
    li $v0, 4              # load I/O code for string output
    syscall                # output a newline

    li $v0, 10             # load code for terminating program
    syscall                # terminate program

# ---------------------------------------------------------
# Calculates the greatest common divisor
# ---------------------------------------------------------
gcd:
    addi $sp, $sp, -8      # adjust stack for 2 items
    sw $ra, 4($sp)         # save the return address
# ---------------------------------------------------------
# Recursive Step (Part 1)
    div $a1, $a2           # divide arg1 by arg2; remainder in $HI
    mfhi $s0               # $s0 = arg 1 % arg2
    sw $s0, 0($sp)         # save the remainder
    bne $s0, $zero, L1     # recurse if $s0 != 0
# ---------------------------------------------------------
# Base Case
    add $v0, $a2, $zero   # argument2 holds result, store in $v0
    addi $sp, $sp, 8      # pop 2 items from stack
    jr $ra                # return
# ---------------------------------------------------------
# Recursive Step (Part 2)
L1:
    add $a1, $a2, $zero   # set arg1 to arg2
    lw $s0, 0($sp)        # load remainder
    add $a2, $s0, $zero   # set arg2 to remainder
    jal gcd               # recursive call
# ---------------------------------------------------------
# Exit Recursion
    lw $ra, 4($sp)        # load previous return address
    addi $sp, $sp, 8      # pop 2 items from the stack
    jr $ra                # return