Skip to main content

Booth algorithm and 8 × 9

Short answer

M=8=01000, Q=9=01001, -M=11000, 5 bits. Steps: 10 A−M, 01 A+M, 00 no change, 10 A−M, 01 A+M, each with ASR. Result A,Q = 00010 01000 = 72.

Explain the Booth algorithm and multiply Y = 8×9 using Booth's algorithm.

Booth algorithm

Booth's algorithm multiplies two signed numbers in 2's complement form. It looks at the multiplier bit pair (Q0, Q-1) and treats a run of 1s as (next higher power − lowest power), so a block of 1s needs only one subtraction and one addition.

  1. Load M = multiplicand, Q = multiplier, A = 0, Q-1 = 0, SC = n (number of bits).
  2. Look at (Q0, Q-1):
    • 00 or 11: no arithmetic.
    • 10 (start of a run of 1s): A = A − M.
    • 01 (end of a run of 1s): A = A + M.
  3. Arithmetic shift right the combined A, Q, Q-1 by one bit (the sign bit of A is kept).
  4. SC = SC − 1. If SC ≠ 0 go to step 2; otherwise stop.
  5. The 2n-bit product is in A:Q.

Y = 8 × 9

Five bits are used so that both numbers are valid positive signed numbers (9 needs 5 bits).

Multiplicand M = 8 = 01000, multiplier Q = 9 = 01001, -M = 11000, n = 5 bits.

Step  Action               A      Q      Q-1
-     Initial              00000  01001  0
1     Q0Q-1=10: A = A - M  11000  01001  0
      ASR                  11100  00100  1
2     Q0Q-1=01: A = A + M  00100  00100  1
      ASR                  00010  00010  0
3     Q0Q-1=00: no change  00010  00010  0
      ASR                  00001  00001  0
4     Q0Q-1=10: A = A - M  11001  00001  0
      ASR                  11100  10000  1
5     Q0Q-1=01: A = A + M  00100  10000  1
      ASR                  00010  01000  0

Result in A,Q = 00010 01000 = 72.

Answer: 8 × 9 = 72

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Computer Organization and Architecture chapter 5 questions →