Booths Algorithm

Integer Multiplication
and Division
Shah Murtaza Rashid Al Masud
Unsigned Multiplication
Signed Multiplication
Faster Multiplication
Unsigned Division
Signed Division
Multiplication and Division in MIPS
Unsigned Multiplication
Paper and Pencil Example:
Multiplicand
11002 = 12
Multiplier
11012 = 13
1100
0000
1100
1100
Product
100111002 = 156
m-bit multiplicand n-bit multiplier = (m+n)-bit product
Accomplished via shifting and addition
Consumes more time and more chip area
Binary multiplication is easy

0 multiplicand = 0
1 multiplicand = multiplicand
Initialize Product = 0
Multiplicand is zero extended
Start
=1
shift left
Multiplicand
=0
1a. Product = Product + Multiplicand
64 bits
add
64-bit ALU
Multiplier[0]?
2. Shift the Multiplicand Left 1 bit
64 bits
write
Product
Control
3. Shift the Multiplier Right 1 bit
64 bits
shift right
Multiplier
32 bits
32nd Repetition?
Yes
Multiplier[0]
Done
4
No
Consider: 11002 11012 , Product = 100111002

4-bit multiplicand and multiplier are used in this example
Multiplicand is zero extended because it is unsigned
Signed Multiplication
Version 1 of Signed Multiplication
Convert multiplier and multiplicand into positive numbers
If negative then obtain the 2's complement and remember the sign
Perform unsigned multiplication

Compute the sign of the product
If product sign < 0 then obtain the 2's complement of the product
Refined Version:
Use the refined version of the unsigned multiplication hardware
When shifting right, extend the sign of the product
If multiplier is negative, the last step should be a subtract
Case 1: Positive Multiplier

Multiplicand
Multiplier
11002 = -4
01012 = +5
11111100
111100
Product
111011002 = -20
Case 2: Negative Multiplier

Multiplicand
Multiplier
11002 = -4
11012 = -3
11111100
111100
00100
(2's complement of 1100)
Product
000011002 = +12
Similar to Unsigned Multiplier

ALU produces a 33-bit result
Multiplicand and HI are sign-extended
Sign is the sign of the result
Start
LO=Multiplier, HI=0
Multiplicand
32 bits
=1
32 bits
33-bit ALU
add, sub
First 31 iterations: HI = HI + Multiplicand

Last iteration: HI = HI Multiplicand
33 bits
sign
32 bits
=0
LO[0]?
shift right
HI
LO
64 bits
write
Control
LO[0]
Shift Right Product = (HI, LO) 1 bit
32nd Repetition?
Yes
Done
No
Consider: 11002 (-4) 11012 (-3), Product = 000011002

Multiplicand and HI are sign-extended before addition
Last iteration: add 2's complement of Multiplicand
Unsigned Division
10
First Division Algorithm & Hardware

Start
Initialize:
Remainder = Dividend (0-extended)
Load Upper 32 bits of Divisor
1. Shift the Divisor Right 1 bit

Shift the Quotient Left 1 bit
Difference = Remainder Divisor
Quotient = 0
shift right
Divisor
0
64 bits
64-bit ALU
Remainder
<0
sub
2. Remainder = Difference
Set least significant bit of Quotient
sign
Difference
Difference?
write
Control
64 bits
shift left
Quotient
32 bits
32nd Repetition?
Yes
set lsb
Done
11
No
Consider: 11102 / 00112 (4-bit dividend & divisor)

Quotient = 01002 and Remainder = 00102
8-bit registers for Remainder and Divisor (8-bit ALU)
12
Observations on Version 1 of Divide

Version 1 of Division hardware can be optimized
Instead of shifting divisor right,
Shift the remainder register left
Has the same net effect and produces the same
results
Reduce Hardware:
Divisor register can be reduced to 32 bits (instead of 64
bits)
ALU can be reduced to 32 bits (instead of 64 bits)
Remainder and Quotient registers can be combined
13
Refined Division Hardware

Observation:
Start
Shifting remainder left does the

same as shifting the divisor right
Initialize:
1. Shift (Remainder, Quotient) Left

Difference = Remainder Divisor
Quotient = Dividend, Remainder = 0
Divisor
Difference?
<0
32 bits
2. Remainder = Difference
Set least significant bit of Quotient
sub
32-bit ALU
sign
Difference
write
Remainder Quotient
32 bits
32 bits
Control
shift left
set lsb
32nd Repetition?
Yes
Done
14
No
Same Example: 11102 / 00112 (4-bit dividend & divisor)

Quotient = 01002 and Remainder = 00102
4-bit registers for Remainder and Divisor (4-bit ALU)
15
Signed Division
Simplest way is to remember the signs
Convert the dividend and divisor to positive
Obtain the 2's complement if they are negative
Do the unsigned division

Compute the signs of the quotient and remainder
Quotient sign = Dividend sign XOR Divisor sign
Remainder sign = Dividend sign
Negate the quotient and remainder if their sign is

negative
Obtain the 2's complement to convert them to negative
16
1.
Positive Dividend and Positive Divisor

Example: +17 / +3
1.
Quotient = 5
Remainder = +2
Negative Dividend and Positive Divisor

Example: 17 / +3
1.
Remainder = +2
Positive Dividend and Negative Divisor

Example: +17 / 3
1.
Quotient = +5
Quotient = 5
Remainder = 2
Negative Dividend and Negative Divisor

Example: 17 / 3
Quotient = +5
Remainder = 2
The following equation must always hold:

Dividend = Quotient Divisor + Remainder
17
Multiplication in MIPS
Two Multiply instructions
mult
$s1,$s2Signed multiplication
multu $s1,$s2Unsigned multiplication
32-bit multiplication produces a 64-bit Product
$0
$1
..
Separate pair of 32-bit registers

HI = high-order 32-bit
$31
LO = low-order 32-bit
Multiply
Result of multiplication is always in HI & LO
Moving data from HI/LO to MIPS registers

mfhi Rd (move from HI to Rd)
Divide
HI
mflo Rd (move from LO to Rd)

18
LO
Division in MIPS
Two Divide instructions
div
$s1,$s2
divu $s1,$s2
Signed division
Unsigned division
Division produces quotient and remainder
$0
$1
..
Separate pair of 32-bit registers

HI = 32-bit remainder
LO = 32-bit quotient
If divisor is 0 then result is unpredictable
Moving data to HI/LO from MIPS registers

mthi Rs (move to HI from Rs)
$31
Multiply
Divide
HI
mtlo Rs (move to LO from Rs)

19
LO
Booth's multiplication algorithm

Booth's algorithm involves repeatedly adding one of two predetermined values A
and S to a product P, then performing a rightward arithmetic shift on P. Let m and
r be the multiplicand and multiplier, respectively; and let x and y represent the
number of bits in m and r.
Determine the values of A and S, and the initial value of P. All of these numbers
should have a length equal to (x+y+1).
A: Fill the most significant (leftmost) bits with the value of m. Fill the remaining (y+1) bits
with zeros.
S: Fill the most significant bits with the value of (m) in two's complement notation. Fill
the remaining (y+1) bits with zeros.
P: Fill the most significant x bits with zeros. To the right of this, append the value of r. Fill
the least significant (rightmost) bit with a zero.
Determine the two least significant (rightmost) bits of P.

If they are 01, find the value of P+A. Ignore any overflow.
If they are 10, find the value of P+S. Ignore any overflow.
If they are 00, do nothing. Use P directly in the next step.
If they are 11, do nothing. Use P directly in the next step.
Arithmetically shift the value obtained in the 2nd step by a single place to the right.
Let P now equal this new value.
Repeat steps 2 and 3 until they have been done y times.
Drop the least significant (rightmost) bit from P. This is the product of m and r.
20
Example1
Find 3 4, with m = 3 and r = 4, and x = 4 and y = 4:
A = 0011 0000 0
S = 1101 0000 0
P = 0000 1100 0
Perform the loop four times:
P = 0000 1100 0. The last two bits are 00.
P = 0000 0110 0. Arithmetic right shift.


P = 1101 0011 0. P = P + S.

The product is 1111 0100, which is 12.

21
Example2
The above mentioned technique is inadequate when the multiplicand is
the largest negative number that can be represented (i.e. if the multiplicand has 8 bits
then this value is 128). One possible correction to this problem is to add one more bit
to the left of A, S and P. Below, we demonstrate the improved technique by multiplying
8 by 2 using 4 bits for the multiplicand and the multiplier:
A = 1 1000 0000 0
S = 0 1000 0000 0
P = 0 0000 0010 0
Perform the loop four times:
P = 0 0000 0010 0. The last two bits are 00.
P = 0 0000 0001 0. Right shift.

P = 0 1000 0001 0. P = P + S.
P = 0 0100 0000 1. Right shift.

P = 1 1100 0000 1. P = P + A.
P = 1 1110 0000 0. Right shift.

P = 0 1111 0000 0. Right shift.
The product is 11110000 (after discarding the first and the last bit) which is 16.
22
Booth's multiplication algorithm

Procedure
If x is the count of bits of the multiplicand, and y is the count of bits of the multiplier :
Draw a grid of three lines, each with squares for x + y + 1 bits. Label the lines
respectively A (add), S
(subtract), and P (product).
In two's complement notation, fill the first x bits of each line with :
A: the multiplicand
S: the negative of the multiplicand
P: zeroes
Fill the next y bits of each line with :
A: zeroes
S: zeroes
P: the multiplier
Fill the last bit of each line with a zero.
Do both of these steps y times :
1. If the last two bits in the product are...
00 or 11: do nothing.
01: P = P + A. Ignore any overflow.
10: P = P + S. Ignore any overflow.
2. Arithmetically shift the product right one position.
Drop the last bit from the product for the final result.
23
Example
Find 3 -4:
A = 0011 0000 0
S = 1101 0000 0
P = 0000 1100 0
Perform the loop four times :
P = 0000 0110 0. A right shift.
P = 0000 0011 0. A right shift.
P = 1101 0011 0. P = P + S.
P = 1110 1001 1. A right shift.
P = 1111 0100 1. A right shift.
The product is 1111 0100, which is -12.

24

Booths Algorithm

Uploaded by

Copyright:

Available Formats

Booths Algorithm

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Booths Algorithm

Uploaded by

Copyright:

Available Formats

Integer Multiplication

Shah Murtaza Rashid Al Masud

Binary multiplication is easy

1a. Product = Product + Multiplicand

2. Shift the Multiplicand Left 1 bit

3. Shift the Multiplier Right 1 bit

Consider: 11002 11012 , Product = 100111002

Shah Murtaza Rashid Al Masud

Perform unsigned multiplication

Case 1: Positive Multiplier

Case 2: Negative Multiplier

Similar to Unsigned Multiplier

First 31 iterations: HI = HI + Multiplicand

Shift Right Product = (HI, LO) 1 bit

Shah Murtaza Rashid Al Masud

Consider: 11002 (-4) 11012 (-3), Product = 000011002

Shah Murtaza Rashid Al Masud

Shah Murtaza Rashid Al Masud

First Division Algorithm & Hardware

1. Shift the Divisor Right 1 bit

Shah Murtaza Rashid Al Masud

Consider: 11102 / 00112 (4-bit dividend & divisor)

Shah Murtaza Rashid Al Masud

Observations on Version 1 of Divide

Refined Division Hardware

Shifting remainder left does the

1. Shift (Remainder, Quotient) Left

Quotient = Dividend, Remainder = 0

Same Example: 11102 / 00112 (4-bit dividend & divisor)

Shah Murtaza Rashid Al Masud

Do the unsigned division

Negate the quotient and remainder if their sign is

Positive Dividend and Positive Divisor

Negative Dividend and Positive Divisor

Positive Dividend and Negative Divisor

Negative Dividend and Negative Divisor

The following equation must always hold:

multu $s1,$s2Unsigned multiplication

32-bit multiplication produces a 64-bit Product

Separate pair of 32-bit registers

Result of multiplication is always in HI & LO

Moving data from HI/LO to MIPS registers

mflo Rd (move from LO to Rd)

Division produces quotient and remainder

Separate pair of 32-bit registers

Moving data to HI/LO from MIPS registers

mtlo Rs (move to LO from Rs)

Booth's multiplication algorithm

Determine the two least significant (rightmost) bits of P.

P = 0000 0110 0. The last two bits are 00.

P = 0000 0011 0. The last two bits are 10.

P = 1110 1001 1. The last two bits are 11.

The product is 1111 0100, which is 12.

P = 0 0000 0001 0. The last two bits are 10.

P = 0 0100 0000 1. The last two bits are 01.

P = 1 1110 0000 0. The last two bits are 00.

Shah Murtaza Rashid Al Masud

Booth's multiplication algorithm

Shah Murtaza Rashid Al Masud