Booth algorithm

The Booth algorithm is an algorithm for the multiplication of two numbers in two's complement representation. It was developed in 1951 by Andrew Donald Booth while working on crystallography at Birkbeck College .

Procedure

Let x be the number of bits of the multiplicand and y the number of bits of the multiplier.
Draw a three-row grid with columns. Label the lines with A (addition), S (subtraction) and P (product). ${\ displaystyle x + y + 1}$
Write down the first x bits of each line as follows:
- A: multiplicand
- S: negated multiplicand (in two's complement)
- P: zeros
The next y bits of each line are to be filled as follows:
- A: zeros
- S: zeros
- P: multiplier
The last column is padded with zeros.
Carry out the following two steps y times:
1. Are the last two bits of P
  - 00 or 11: Do nothing
  - 01 . Ignore any overflow. ${\ displaystyle P = P + A}$
  - 10 . Ignore any overflow. ${\ displaystyle P = P + S}$
2. Arithmetically shift the product one position to the right.

The product is now in the front bits (the last bit is ignored).

{\ displaystyle x + y}

idea

One makes use of the fact that every number b can be represented as the difference between two numbers c and d:

${\ displaystyle {\ mbox {Sei}} b = cd}$

Then any multiplication of b by a factor a can be transformed as follows:

${\ displaystyle a \ cdot b = a \ cdot (cd) = a \ cdot ca \ cdot d}$

This method offers advantages over the "paper and pencil" method for numbers that have long, equivalent bit strings in the binary representation . These are "skipped" with the booth method. Based on this, the Booth method also allows efficient multiplication for binary numbers in two's complement , i.e. H. the algorithm has the advantage that one does not have to consider the signs of the two factors.

example

If you want to multiply by a number X, you needed three additions to the traditional method: . The Booth's method, however, requires only one . ${\ displaystyle 30_ {10} = 00011110_ {2}}$ ${\ displaystyle 10_ {2} \ times X + 100_ {2} \ times X + 1000_ {2} \ times X + 10000_ {2} \ times X}$ ${\ displaystyle 100000_ {2} \ cdot X-10_ {2} \ cdot X}$

The subtraction can be calculated in two's complement like an addition, the multiplication by a multiple of 2 only corresponds to a shift of the digits to the left (shift operation). The method thus serves for efficient multiplication in computers.

The Booth algorithm offers an efficient way of determining the coding to be used for a number. You go through the binary number from right to left. If the binary digit changes from the last to the current position from 0 to 1, a −1 is set, if there is a change from 1 to 0 a +1 and if there is no change a 0 is set. In the first step, think of the number on the right a 0.

Examples

Multiply and ${\ displaystyle 44_ {10} = (00101100) _ {2}}$ ${\ displaystyle 17_ {10} = (00010001) _ {2}}$

Coding of a factor according to Booth

Step 1	0	1	0	1	1	0	0
Step 1
step 2	0	1	0	1	1	0	0
step 2						0
step 3	0	1	0	1	1	0	0
step 3					-1	0
Step 4	0	1	0	1	1	0	0
Step 4				0	−1	0
Step 5	0	1	0	1	1	0	0
Step 5			+1	0	−1	0
Step 6	0	1	0	1	1	0	0
Step 6		-1	+1	0	−1	0
Step 7	0	1	0	1	1	0	0
Step 7	+1	−1	+1	0	−1	0

Formal: Add another "digit" to the operand to be coded using Booth , which is set to zero. The other points of the new are calculated as follows: . ${\ displaystyle Y = (y_ {n-1}, \ dots, y_ {0})}$ ${\ displaystyle y _ {- 1}}$ ${\ displaystyle {y '} _ {i}, i \ in \ left \ {0, \ dots, n-1 \ right \}}$ ${\ displaystyle Y ': = (y' _ {n-1}, \ dots, y '_ {0}, y _ {- 1})}$ ${\ displaystyle {y '} _ {i} = y_ {i-1} -y_ {i} \ \ forall i \ in \ {0, \ dots, n-1 \}}$

multiplication

									0	0	0	1	0	0	0	1	2nd factor
x									0	+1	−1	+1	0	−1	0	0	Coding of the 1st factor
+		0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	no addition
+		0	0	0	0	0	0	0	0	0	0	0	0	0	0		no addition
+		1	1	1	1	1	1	1	1	0	1	1	1	1			2's complement (2nd factor)
+		0	0	0	0	0	0	0	0	0	0	0	0				no addition
+		0	0	0	0	0	0	1	0	0	0	1					2nd factor
+		1	1	1	1	1	0	1	1	1	1						2's complement (2nd factor)
+		0	0	0	0	1	0	0	0	1							2nd factor
+		0	0	0	0	0	0	0	0								no addition
1	0	0	0	0	0	0	1	0	1	1	1	0	1	1	0	0	Result without overflow

Instead of multiplying by 0100000, 0001000 and 0000100 and adding the results, it is now multiplied by 1000000, 0100000, 0010000 and 0000100 and the results are added or subtracted accordingly.

As you can see in the example, the number of additions can also increase (in the example from 3 to 4), which is not exactly what you want. On a statistical average, just as many additions are needed in the Booth method as without the Booth method. The advantage, however, is that there is no equal distribution of numbers in computer science. Rather, there are often numbers with many zeros and, due to the two's complement of negative numbers, often many ones at the beginning. Only because of this fact does the Booth method have advantages over normal multiplication.

The extension of the Booth method is the bit pair method , in which two digits are always combined.

swell

The work of Professor Andrew D. Booth , Department of Computer Science and Information Systems, Birkbeck College (engl.)

Web links

automatic calculation of a booth multiplication