Lab 3: Multiplication and Exponent Solution

Description

Submission timestamps will be checked and enforced strictly by the CourseWeb; late submissions will not be accepted. Check the due date of this lab on the CourseWeb. Remember that, per the course syllabus, if you are not marked by your recitation instructor as having attended a recitation, your score will be cut in half.

In this lab, you are going to learn how to use bit-wise operations to achieve faster multiplication.

Multiplication

For this lab, you are not allowed to use any multiplication instruction. In other words, you must implement a multiplication algorithm. A simple way to calculate x y is by using addition. Since x y is equal to x + x + : : : + x (y times), we can use a simple loop to calculate x y. However, if y is a large number, this algorithm requires a large number of iterations.

As we discussed in class, since binary is a base-number system, we can use long multiplication method of decimal to calculate binary multiplication. Consider 9 11 in 4-bit binary (unsigned):

1001
1011	x
—-
1001
1001
0000	+

1001

——-

1100011

=======

Recall that 1100011₂ in unsigned binary is 99 in decimal. Note that instead of 11 addition opera-tions, the above long multiplication only requires 4 addition operations. The number of addition operations required by this method does not depend on the value of a multiplier. It only depends on the number of bits of multiplicand and multiplier. For a 16-bit unsigned numbers x and y, to calculate x y only requires 16 addition operations.

This multiplication algorithm can be easily implemented using shift, bit-wise, comparison, and addition operations. Now, consider 9 11 in 4-bit binary (unsigned) one more time:

1001
1011	x
—-
1001		<– (1001 << 0)		*	1	where 1 is the LSB of the multiplier
1001		<– (1001	<< 1)	*	1
0000	+	<– (1001	<< 2)	*	0
1001		<– (1001	<< 3)	*	1	where 1 is the MSB of the multiplier
——-
1100011
=======

As you may notice, we accumulate the result (starting from 0) using a series of addition opera-tions. The rst addition operation depends on the multiplier shifted left by 0, the second addition operation depends on the multiplier shifted left by 1, and so on. Whether too add 0 or non-zero

Lab 3: Multiplication and Exponent

to the result at a step, it depends on a certain bit of the multiplier. The rst addition depends on the LSB (bit 0) of the multiplier, the second addition depends on bit 1 of the multiplier, and so on. To check whether a bit of a number is 0 or 1 can be easily done using shift and/or bit-wise AND operations.

Exponent

For this lab, you just have to implement a simple exponent algorithm. Simply use the fact that x^y is equal to x x x : : : x (y times). This algorithm is not e cient, however, we will not test your algorithm with a large number since the result may not t in a 32-bit register. Note that your are not allowed to use any multiplication instruction. You MUST use your implementation of multiplication as described in previous section.

What to do?

Write an assembly program named lab03.asm that asks a user to enter a positive integer for x and another positive integer for y. If a user enter a negative number, ask the user to enter a new number. Once a user enter both number, simply display the result of x y and x^y as shown below:

Please make sure that output of your program is similar to the above example. Note that we will enter a couple of large numbers to check your multiplication algorithm but we will ignore the result of exponent since it may be larger than a 32-bit value. When we test your exponent algorithm, we will use a couple of small numbers.

Submission

Submit your lab03.asm le via CourseWeb before the due date stated on the CourseWeb.

CS/COE 0447 | Computer Organization and Assembly Language Page 2