06. Booth's Algorithm

$\gdef \N{\mathbb{N}} \gdef \Z{\mathbb{Z}} \gdef \Q{\mathbb{Q}} \gdef \R{\mathbb{R}} \gdef \C{\mathbb{C}} \gdef \setcomp#1{\overline{#1}} \gdef \sseq{\subseteq} \gdef \pset#1{\mathcal{P}(#1)} \gdef \covariant{\operatorname{Cov}} \gdef \of{\circ} \gdef \p{^{\prime}} \gdef \pp{^{\prime\prime}} \gdef \ppp{^{\prime\prime\prime}} \gdef \pn#1{^{\prime\times{#1}}} $

Booth’s Algorithm is an efficient method for multiplying two binary numbers in 2’s Compliment Format.

\(\newcommand{\code}[1]{\texttt{**1**{: #1 .hash}}}\)

Note

There will be 3 ‘fields’ referred to: \(A\), \(B\), and product.
A and B refer to the first and second multiplicands:
When multiplying two numbers, it’s \(A\times B\)
Product is our ‘working draft’ of what the result is.

Sign-extend the numbers to make sure they’re the same length. The product will be twice the amount of bits the operands take. Make sure the numbers are signed!
Write out \(-B\) in 2’s Compliment. This will be useful later.

Pro Tip:
Keep your bits very orderly. Graph paper is advised, it will help reduce hand errors.

First, to set up the algorithm, prepare a table of sorts. The headers of the table should be: Iteration, Product, and L. The first row of the table should look like this (Assuming A and B are 4 bits):

Iteration Step Product L Description
0 0 00000000 0 Initialize

Then set the last 4 bits of the Product to equal the value in A.
For the rest of the algorithm, the next step is determined by the combination of the last bit of the Product, and the L bit.
The L bit is the bit that just got chopped off of the product. We’ll get to that soon.

Product L Action
0 0 Do Nothing
1 1 Do Nothing
0 1 Addition - Add B to the first half of the Product field. Discard carry-over
1 0 Subtraction - Add -B to the first half of the Product field
After each step, shift the product field right by one bit.
If your multiplicands are \(n\) bits in length, you keep going until the end of the \(n^{th}\) iteration.

I feel like the best way to continue is by example, with a TL;DR at the bottom:
Let \(A=\) 0100, Let \(B=\) 0111. \(-B=\) 1001

Iteration Step Product L Action Taken Commentary
0 0 00000100 0 Initialize The last four bits are equal to \(A\)
1 1.00 00000100 0 No action The bits are 00
1 2 00000010 0 Shift right one bit
2 1.00 00000010 0 No action The bits are 00
2 2 00000001 0 Shift right one bit
3 1.10 10010001 0 Add \(-B\) to the right half of the product The bits are 10
3 2 11001000 1 Shift right one bit
4 1.01 00111000 1 Add \(B\) to the right half of the product The bits are 01
4 2 00011100 0 Shift right one bit

TL;DR:

  1. Make sure A and B are the same length (sign extending if needed), and signed.
    • Calculate -B in two’s compliment form
  2. Set up the table. Keep track of your iteration number, your ‘step’, the Product field, and the leftover bit field. Set the 2nd half of the product field to A, and the first half to 0.
  3. Increment the iteration counter. If it’s greater than the number of bits in A or B, stop, go to step 7.
  4. The last bit of the product joined with the leftover bit tell you what to do:
    1. If they’re the same (00 or 11), do nothing. Proceed to the next part.
    2. If it’s 01, add B to the first half of the product field, discarding carry-over on the leading bit.
    3. If it’s 10, add -B to the first half of the product field, ignoring ‘borrow’ on the leading bit.
  5. Shift right one bit
  6. Repeat steps 3-5
  7. The result is the Product field. Do not include the leftover bit in your result!
    1. If you do, you’re dumb. More importantly, you’ll get the wrong answer. If you want to avoid either one of those two terrible fates, Don’t include the leftover bit!