HW3: Advanced MIPS and Faster Multiplication

This assignment gives more practice with MIPS instructions and using logic to write

assembly language solutions to problems. You should complete this assignment

with your same partner. Make sure that both of your names are at the top of

your file in comments, and that you comment well in general.

Deliverables: The file username1_username2.asm containing your solution program.

Faster Multiplication of Positive Integers

Given the limited instructions available to use, you probably wrote your

multiplication program in HW1 using some variation of the following algorithm:

to multiply x * y:

set result to 0

add x to result y times

This works just fine, however it is not very efficient. In fact it is O(y), or in other

words it requires executing c*y instructions where c is some constant. Much more

efficient is to use the algorithm you would use if multiplying 2 large numbers by

hand, which involves summing up the partial results created by multiplying one

number by each digit of the 2nd number individually. For example, you could break

down the multiplication of 2 3-digit numbers in the decimal system as follows:

XYZ * ABC = XYZ*C + XYZ*B*10 + XYZ*A*100

Note that the *10 and *100 for the 2nd and 3rd partial results are the same as adding

the appropriate number of extra 0’s to the end of each, as you do when actually

multiplying by hand. In essence you actually shift each partial result to the left, with

the first partial result shifted left 0 digits, and each further partial result shifted left

1 more digit than the previous.

This method of multiplication works the same no matter what base number system

you are using, so you can use the exact same technique to multiply 2 binary

numbers. However, even if you use shifting instead of multiplying by 10 and 100,

the above equation still uses multiplication itself to get each partial result, while our

goal is to use only addition. This is where the binary number system makes things

simpler. Try writing out the multiplication of the base-10 numbers 234 and 1,011

by hand using the above method. Make sure you put 1,011 as the 2nd number in the

multiplication. What pattern do you see?

234*1,011 = 234*1 + 234*1*10 + 234*0*100 + 234*1*1,000

= 234 + 2340 + 0 + 234000

Since in binary the only possible digits are 1 and 0, you’ll only ever be multiplying by

a 1 or a 0 to get the next partial sum, and then shifting it left the appropriate number

of digits. This means that each term in the final equation will either be 234 shifted

left some number of digits, or simply 0. You don’t actually need to do any

multiplying, but can use logic and conditionals along with shifting to determine the

value of each term.

This faster method is just O(# digits in the 2nd operand): at most 32 digits in MIPS.

Your Task

Write a program in MIPS that performs multiplication using this faster method.

Most of the credit will be given for a solution that works correctly and runs in O(#

digits) time as described above, however for full credit you should make your

solution efficient and correctly handle edge cases. For example, to be efficient you

should loop as few times as possible, and you should minimize the number of basic

instructions executed each time through the loop (somewhere around 10 is fine,

though you can do it with less). Edge cases include 0 or a negative number as one or

both of the operands – ideally you could design an algorithm that works for any case

without needing extra checks. You do NOT have to check for overflow in this

program, though it’s useful to think about how you would.

I highly recommend you come up with an algorithm in pseudo-code first and TEST

IT on some example numbers before trying to debug actual MIPS assembly code.

For this task you may use the following larger subset of MIPS instructions (purple

denotes new instructions added):

– any of the load and store instructions (e.g. lw, sw)

– any of the add and subtract instructions (e.g. add, addi)

– any of the branch/jump instructions (e.g. beq, bne, bgt, j)

– any of the shift instructions (e.g. sll, srl, sllv)

– any of the logical operation instructions (e.g. and, or, nor)

Clearly as before you may NOT use instructions mult or div.

As in the last HW, you should load the 2 numbers to multiply from the first 2

words of the data section of memory and store the result in the 3rd word.

Sale!