Exercise 3.6 In this exercise we will look at a couple of other ways to improve the performance of multiplication, based primarily on doing more shifts and fewer arithmetic operations. The following table shows pairs of hexadecimal numbers.

A B

a. 24 c9

b. 41 18 3.6.1 [20] <3.3> As discussed in the text, one possible performance enhancement is to do a shift and add instead of an actual multiplication. Since 9 × 6, for example, can be written (2 × 2 × 2 + 1) × 6, we can calculate 9 × 6 by shifting 6 to the left three times and then adding 6 to that result. Show the best way to calculate A × B using shifts and adds/subtracts. Assume that A and B are 8-bit unsigned integers.

3.6.2 [20] <3.3> Show the best way to calculate A × B using shift and adds, if A and B are 8-bit signed integers stored in sign-magnitude format.

3.6.3 [60] <3.3> Write a MIPS assembly language program that performs a multiplication on signed integers using shift and adds, as described in 3.6.1 .

The following table shows further pairs of hexadecimal numbers.

A B

a. 42 36

b. 9F 8E 3.6.4 [30] <3.3> Booth’s algorithm is another approach to reducing the number of arithmetic operations necessary to perform a multiplication. This algorithm has been around for years, and details about how it works are available on the Web.

Basically, it assumes that a shift takes less time than an add or subtract, and uses this fact to reduce the number of arithmetic operations necessary to perform a multiply. It works by identifying runs of 1s and 0s, and performing shifts during the runs. Find a description of the algorithm and explain in detail how it works.

3.6.5 [30] <3.3> Show the step-by-step result of multiplying A and B, using Booth’s algorithm. Assume A and B are 8-bit two’s-complement integers, stored in hexadecimal format.

3.6.6 [60] <3.3> Write a MIPS assembly language program to perform the multiplication of A and B using Booth’s algorithm.