GATE CSE 1996 | Question: 1.23

Question

Booth’s algorithm for integer multiplication gives worst performance when the multiplier pattern is

• A. $101010\ldots1010$

• B. $100000\ldots 0001$

• C. $111111\ldots 1111$

• D. $011111\ldots1110$

Comments

@Arjun sir,,can you explain option A and B?i m little confused

---

Best case is only 0's or 1's.

Answer 1

Answer: A

The worst case of an implementation using Booth’s algorithm is when pairs of $01$s or $10$s occur very frequently in the multiplier.

Comments

Booth's algo is used for multiplication of two signed numbers, then what does above question actually mean?

---

Booth multiplication can be used for both signed and unsigned...

Answer 2

$\text{Booth Multiplication}:$ Booth multiplication is used to reduce the number of additions. Peformance of Booth Algorithm depends on number of Additions and Subtractions.

$\text{Booth Recoding}:$ 

Operand $X_i$	Operand $X_{i-1}$	Recoded Version $Y_i$
$0$	$0$	$0$
$0$	$1$	$1$
$1$	$0$	$-1$
$1$	$1$	$0$

 

So Option $A$