Subtopic 7 of 9
4.7Booth's algorithm (radix-2)
The idea
Booth's algorithm multiplies signed numbers by treating a run of 1s in the multiplier as one subtraction at the start and one addition after the end.
Think of it like this: 999 is easier as 1000 − 1: two steps instead of three.
Why it exists
It handles signed numbers directly and is fast when the multiplier has long runs of 1s.
How it works
- Append a 0 to the right of the multiplier (Q₋₁).
- Look at Q₀Q₋₁: 01 → A = A + M; 10 → A = A − M; 00 or 11 → nothing.
- Arithmetic shift right (A, Q, Q₋₁ together).
- Repeat n times; the answer is A:Q.
Worked example: −3 × 5 (5 bits)
Result A:Q = −15.
Now play with it
- →Press Next step and watch which rows add, subtract or do nothing.
- →Try a multiplier of 7 (0111) vs 5 (0101).
| Step | Q₀Q₋₁ | Action | A | Q | Q₋₁ |
|---|---|---|---|---|---|
| init | - | A = 0, Q = multiplier | 00000 | 00101 | 0 |
M = 11101. Rows shown: 1 of 6.
Check yourself
In Booth's algorithm, Q₀Q₋₁ = 10 means:
Remember: 01: add, 10: subtract, 00/11: just shift.
Exam notes (the dense version)
Inspect (Q₀, Q₋₁): 01 → A ← A + M · 10 → A ← A − M · 00 / 11 → no op. Then arithmetic shift right (A,Q,Q₋₁). n iterations. Skips runs of 1s → fast for strings of 1s. Radix-4 (modified Booth) → n/2 steps.
Previous year questions: Number Representation & Computer Arithmetic (19)
PYQs are grouped by topic, so this is the full set for Number Representation & Computer Arithmetic; try the ones that match this subtopic. Open all 19 on the topic page.