12.16 Assignment 6 - Question 1

Write a MIPS program to compute the product of two 16-bit signed numbers using *recursive procedure calls. *Note:* You CANNOT use the mult or mul instructions.

Given the multiplicand (md) and multiplier (m) as inputs, write the main and recursion functions to compute the product (p) using the shift and add recursive algorithm for multiplication.

Write the following functions in MIPS.

main

task: initialize product, multiplicand and multiplier registers and call the recursion function with iteration number equal to the size of numbers (16-bit).

Note: If numbers are negative, convert to positive numbers and then multiply. Add sign separately at the end.

recursion

inputs: product (p), multiplicand (md) and multiplier (m) registers and the iteration number (n).

task: compute the nth iterative step of multiplication, call recursion function by decrementing n and return if n = 0.

outputs: updated product (p).

Refer to the binary shift and add multiplication algorithm discussed in class. While writing the code,

Following is a sample C code segment. You may modify the code for the functions, but the task performed should not be changed, i.e., you should use recursive procedure calls.

// multiplier and multiplicand are inputs (For compilable C code, you should use argc and argv for command line inputs) int main(int m, int md) { // Initialization of p, m, md registers int p = 0; // Product initialized to 0 int sign_p = 0; // negate the operands if negative if (m < 0 and md > 0) or (m > 0 and md < 0) sign_p = 1; if (m < 0) m = -m; if (md < 0) md = -md; p = recursion(p, md, m, 16); // 16-bit unsigned multiplication => recursion 16 times if (sign_p == 1) p = - p; // negate if one of the operands is negative } int recursion(int p, int md, int m, int n) { if (n == 0) return(p); else { int m_0 = m & 1; // 0th or least significant bit of multiplier if (m_0 == 1) p = p + md; m = m >> 1; md = md << 1; p = recursion(p, md, m, n-1); // updated values of p, md and m are passed as arguments } 

Registers	Variables
$s0	product
$s1	multiplicand
$s2	multiplier

Example Test: If the values of $s1 and $s2 are initialized in the simulator as:

(Use the '+' button under the Registers display to initialize register values for $s1, $s2.)

Registers	Data
$s0	0
$s1	8000
$s2	15000

The resultant registers are:

Registers	Data
$s0	120000000
$s1	8000
$s2	15000

Grading: Manual score (10 points) will be added after the deadline.

4 automated tests each worth 5 points. The registers $s0, $s1 and $s2 will be checked by the automated tests.

Comments specifying your choice of registers and each line of your code (5 points).

Correct use of Recursive Procedure Calls (5 points).

If you use mult or mul anywhere in the code, you will receive a score of zero, even if the automated tests are successful.