Computer Arithmetic

What is the main effect of using radix-4 Booth's algorithm (Booth encoding) in a multiplier?

  1. AIt guarantees that products are computed exactly, without rounding
  2. BSigned-digit recoding roughly halves the partial products
  3. CIt makes signed multiplication impossible in exchange for a smaller circuit
Show answer and explanation

Answer: B. Signed-digit recoding roughly halves the partial products

Ordinary multiplication produces one partial product per multiplier bit, so n bits require summing n partial products. Radix-4 Booth encoding recodes the multiplier two bits at a time (examining overlapping 3-bit groups) into digits −2, −1, 0, +1 and +2, reducing the partial products to about n/2. Doubling is a one-bit shift and negatives are formed with two's complement, so the circuitry is simple. Fewer partial products make the summing logic smaller and faster, and signed multiplication is handled naturally.

  • A. Integer multiplication is already exact; that is not Booth's goal.
  • B. Correct. It roughly halves the number of partial products.
  • C. Booth's method handles signed multiplication naturally.
Practice this topic Back to topic

More Computer Arithmetic questions

  1. When two unsigned 8-bit numbers are multiplied, how many bits are needed to represent the result without overflow?
  2. Which expression multiplies an integer x by 10 using shifts and additions instead of a multiply instruction?
  3. Why do typical integer dividers (restoring or non-restoring, producing one quotient bit at a time) tend to be slower than multipliers?
  4. What is the result of arithmetic right-shifting the 8-bit signed integer −8 (1111 1000) by one bit?
  5. In C, what are the results of −7 / 2 and −7 >> 1 (with an arithmetic shift) for int?