CS 208: Computer Organization & Architecture

A multiplication subroutine

You may work alone or with a partner on this assignment. If you would like to work with a partner but want to be assigned one, let me know (preferably via the piece of paper I passed around in class on Wednesday).

MIPS has several integer multiplication instructions, typically optimized in the hardware to make them especially fast. That said, multiplication in a computer has some subtleties that aren't obvious at first glance, so there's quite a bit of value in implementing multiplication yourself, once. That's what you're going to do for this assignment: implement 32-bit signed multiplication in MIPS without using the built-in multiplication instructions.

The "mult" subroutine

Your multiplication subroutine must adhere to the following requirements:

• Its name/label is "mult"
• When it is called, mult will treat the contents of $a0 and $a1 as the factors to be multiplied. It will not refer to locations in memory (e.g. "factor1" and "factor2").
• mult will treat $a0 and $a1 as signed integers. Thus, the product will be negative or positive depending on the signs of $a0 and $a1.
• Before mult returns (via "jr $ra"), it puts the 64-bit product of $a0 and $a1 in $v0 and $v1, where $v0 is the low-order word of the product and $v1 is the high-order word of the product. Note that if the product is negative, the sign bit will be the leftmost bit of $v1.

The "print" subroutine

To test your mult subroutine, you will want to be able to print your results. Given that the product consists of two words (64 bits), and may also represent a two-word negative number, this is not as simple as calling print on the two separate words of the product. If you find it simpler, you may write a print subroutine that prints the results as a 16-digit hexadecimal number instead of a long base ten number. (Printing a two-word number in base ten might be interesting, however, so go ahead and do that if you prefer.)

Don't forget that the print subroutine should be called with parameters in the "a" registers, not in the "v" registers. This means that after you call mult, you'll need to copy $v0 and $v1 to $a0 and $a1 before calling print.

The main program

Go ahead and use the main program from bad_mult.asm, adapting the printing section as needed.

A sketch of the algorithm

Here's a rough description of the algorithm I want you to use. Note that for 32-bit integers, this algorithm may take up to 31 iterations of its loop, but no more than that. Thus, this is a vastly superior algorithm to the one in bad_mult.asm, which has the potential to require more than 2 billion iterations.

Note that the variables SIGN, PRODUCT, MULTIPLICAND, and MULTIPLIER are just my names for these numbers. In your code, all four of these quantities will be stored in registers.

Furthermore, note that PRODUCT and MULTIPLICAND must be 64-bit integers, so you'll need to use two registers to represent each of them. You might even want to write a subroutine for adding a 2-register integer to another 2-register integer.

1. Save the sign: Also, set SIGN = 0 if the product should be non-negative, or SIGN = 1 if it should be negative.
2. Initialization: PRODUCT = 0, MULTIPLICAND = abs(factor1), MULTIPLIER = abs(factor2), where abs(x) is the absolute value of x.
3. LoopStart: If MULTIPLIER is odd, PRODUCT = PRODUCT + MULTIPLICAND.
4. Shift MULTIPLICAND left by one bit.
5. Shift MULTIPLIER right by one bit.
6. If MULTIPLIER != 0, go to LoopStart
7. If SIGN = 1, negate PRODUCT.

And of course...

Start early, ask questions, and have fun!