Around 300 BC Euclid described an algorithm to compute the greatest common divisor
of two numbers, which is the largest number that divides evenly into both numbers
without leaving a remainder. However, Euclid’s original algorithm requires use of the
mod (remainder) function, which is an expensive operation. The binary GCD algorithm
avoids the use of the mod operation and only requires subtraction, shift, and Boolean
You can find an iterative C implementation of the binary GCD algorithm at
https://www.geeksforgeeks.org/steins-algorithm-for-finding-gcd/. All numbers are
assumed to be unsigned, and hence the shift operations can be logical shifts.
Convert the iterative C algorithm to a MIPS assembly language function with name
binaryGCD. The function should accept the a and b arguments in registers $a0 and
$a1, and return the result in register $v0. The function should use the $t* (caller
saved) registers beginning with $t0 and hence does not need to save anything on the
You should try to minimize the variety (rather than the number) of assembly language
instructions used since you later have to implement these instructions in simulated
hardware. You should only use core instructions and avoid referencing memory (i.e.
avoid using lw or sw instructions). Looking ahead to Part 3, the ALU Verilog code
provided supports only the following instructions: sll (only by 1), srl (only by 1), sub,
subi, slt, or, ori, beq, bne, add, addi, and, andi, and lui.
These instructions allow arbitrary control flow, loading constants into registers, and
performing simple arithmetic / Boolean / shift operations on unsigned numbers. The
body of your binaryGCD function (except for the final “jr $ra” instruction) should try to
limit itself to these instructions. The main function can use any instructions including
pseudo instructions since main code will not be executed in ModelSim. You should be
able tocreate an unconditional branch (effectively a jump) using beq.
Test the binaryGCD algorithm with at least the following arguments:
1. gcd(12, 780) = 12
2. gcd(780, 12) = 12
3. gcd(2048, 16384) = 2048
4. gcd(500005199, 709) = 1
5. gcd(554400, 655200) = 50400
6. gcd(1048576, 131072) = 131072
7. gcd(0, 12345) = 12345
Perform each test by loading the arguments into $a0 and $a1, calling binaryGCD, and
then moving the ith result (stored in $v0) to $si. This allows you and the GTA to quickly
check the correctness of your binaryGCD function by inspecting the contents of $s1 to
$s7 after all tests have been run. Ensure that your binaryGCD function has meaningful
labels and comments that describe the function of each register.
EasyDue™ 支持PayPal, AliPay, WechatPay, Taobao等各种付款方式!
E-mail: firstname.lastname@example.org 微信:easydue