Question

Explain booths algorithm with example

Answer 1

Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation. The algorithm was invented by Andrew Donald Booth in 1950 while doing research on crystallography at Birkbeck College in Bloomsbury, London.[1] Booth's algorithm is of interest in the study of computer architecture.


Find 3 × (−4), with m = 3 and r = −4, and x = 4 and y = 4:

m = 0011, -m = 1101, r = 1100

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 = 0000 0110 0. The last two bits are 00.

P = 0000 0011 0. Arithmetic right shift.

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

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

P = 1110 1001 1. Arithmetic right shift.

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

P = 1111 0100 1. Arithmetic right shift.

The product is 1111 0100, which is −12.