FINAL NOTES ON MULTIPLICATION

There are three remaining points to be considered.

1. The implementation I (and Hennessy and Patterson) gave is too simple, in that an additional one bit register for the carry out of the ALU is needed. I will illustrate this with an example.

2. We need to deal with multiplication of signed numbers.

3. You might be interested in how the MIPS ISA handles integer multiplication.

1. The implementation I (and Hennessy and Patterson) gave is too simple, in that an additional one bit register for the carry out of the ALU is needed. I will illustrate this with an example. What is involved is that after the addition step (and before the shift), if there is a carry out it must be saved and shifted into the product register when the shift carried out.

Let us consider 1111₂ x 1101₂ in decimal this is 15 x 13 =195. Let us carry out our algorithm, except now I add an additional 1 bit register to hold the carry out of the ALU:

2. We need to deal with multiplication of signed numbers. (See p. 257 of the text).

The most straightforward approach is to:

• Make both multiplier and multiplicand non-negative, and remember signs
• Multiply the non-negative values using the unsigned algorithm
• Is signs differ, negate product by taking its two's complement.

This is conceptually simple but, in the worst case involves taking a two's complement of one of the inputs, and the two's complement of the double width product register. So in practice other schemes are used; one is Booth's algorithm (pp. 259-263 of text; by the way, you will not be responsible for knowing Booth's algorithm). Other's make use of value = (b₃₁×-2³¹) + (b₃₀×2³⁰) + ...+ (b₁×2¹) + (b₀×2⁰). Note that except for bit 31, the numbers are the same as the unsigned numbers for the same bits. So, very roughly speaking, you use the unsigned algorithm and fudge it depending on what the "sign" bits are. If the multiplicand is negative you have to use sign extension when you shift the product register; if the multiplier is negative you have to apply a correction at the end.

3. You might be interested in how the MIPS ISA handles integer multiplication.

Multiply in MIPS (p. 264)

• The product is returned in two special registers Hi, and Lo.
• Separate move instructions copy from Hi and Lo into general purpose registers
• There is a pseudoinstruction which with all general registers as operands for small products; e.g.,

mul rdst, rsrc1, rsrc2