Booth Algorithm — Role in Fast Multipliers (2m):

Booth's algorithm enables fast signed (two's complement) multiplication with fewer add/sub operations.

• Standard shift-and-add requires an addition for every 1 in multiplier. Booth recodes multiplier and examines pairs of bits ($Q_0, Q_{-1}$):
  • 00 or 11 → arithmetic right shift only
  • 01 → Add multiplicand (A = A + M)
  • 10 → Subtract multiplicand (A = A - M)
    followed by arithmetic right shift.
• Handles positive and negative operands uniformly without separate sign correction.
• Reduces number of operations for strings of 1s (e.g., 01110 handled with one add and one subtract), speeds up multiplier and naturally supports efficient hardware (Booth recoding, Modified Booth Radix-4).
• Basis for modern high-speed array / Wallace-tree multipliers.