--- title: "Booth algorithm and 8 × 9" subject: "Computer Organization and Architecture" chapter: 5 key: "semester_5/computer_organization_and_architecture:booth-8x9" source: https://www.bctengineer.com/q/semester_5/computer_organization_and_architecture/booth-8x9 site: BCT Engineering --- # Booth algorithm and 8 × 9 Computer Organization and Architecture · Chapter 5: Computer Arithmetic - Asked in: 2070 Chaitra, 6 marks - Video: [Booth's Algorithm With Example | booths | booths algo](https://www.youtube.com/watch?v=cWfaw7b3jKY) — Always Learn More - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_5/computer_organization_and_architecture/booth-8x9 - Whole chapter: https://www.bctengineer.com/md/semester_5/computer_organization_and_architecture/chapter-5 ## Question Explain the Booth algorithm and multiply Y = 8×9 using Booth's algorithm. ## 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. ## Answer #### 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. ```text 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** ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Why does Booth's algorithm need fewer operations for a multiplier with a block of 1s? A. Every 1 bit is added once, but zeros are skipped B. The block of 1s is replaced by 0s C. A run of 1s is treated as (next higher power - lowest power): one subtraction and one addition D. The multiplicand is shifted left instead of the product shifting right Answer: C. The block of 1s is the difference of two powers of 2, so only one subtract (at 10) and one add (at 01) are needed. (Key point: Run of 1s idea) 2. Why are five bits used for 8 x 9? A. Both must be valid signed numbers; 9 = 01001 and 8 = 01000 need a leading 0 sign bit B. Booth requires exactly 5 bits always C. To store the carry D. Because 8 x 9 has 5 digits Answer: A. Signed 4-bit range is only up to 7, so a fifth bit holds the sign. (Key point: Why 5 bits) 3. What is 8 x 9 by Booth? A. -72 = 11101 11000 B. 72 = 00010 01000 C. 72 = 01001 01000 D. 64 = 00010 00000 Answer: B. A:Q = 00010 01000 = 72. (Key point: Result) ## Related in Computer Organization and Architecture - [Booth multiplication algorithm and hardware](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Abooth-algorithm) — Computer Organization and Architecture, chapter 5, asked 8× - [Booth algorithm and 8 × 4](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Abooth-8x4) — Computer Organization and Architecture, chapter 5, asked 2× - [Booth multiplication of -5 × -9](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Abooth-5x-9) — Computer Organization and Architecture, chapter 5, asked 5× - [Booth multiplication of 5 × -6](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Abooth-5x-6) — Computer Organization and Architecture, chapter 5, asked 5× - [Booth multiplication of -7 × -10](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Abooth-7x-10) — Computer Organization and Architecture, chapter 5, asked 5× - [Booth multiplication of 10 × (-5)](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Abooth-10x-5) — Computer Organization and Architecture, chapter 5, asked 5×