Booth's multiplication algorithm
Encyclopedia
Booth's multiplication algorithm is a multiplication algorithm
that multiplies two signed binary numbers in two's complement notation
. The algorithm
was invented by Andrew Donald Booth
in 1950 while doing research on crystallography
at Birkbeck College
in Bloomsbury
, London
. Booth used desk calculators that were faster at shift
ing than adding and created the algorithm to increase their speed. Booth's algorithm is of interest in the study of computer architecture
.
representation, including an implicit bit below the least significant bit, y-1 = 0. For each bit yi, for i running from 0 to N-1, the bits yi and yi-1 are considered. Where these two bits are equal, the product accumulator P is left unchanged. Where yi = 0 and yi-1 = 1, the multiplicand times 2i is added to P; and where yi = 1 and yi-1 = 0, the multiplicand times 2i is subtracted from P. The final value of P is the signed product.
The representation of the multiplicand and product are not specified; typically, these are both also in two's complement representation, like the multiplier, but any number system that supports addition and subtraction will work as well. As stated here, the order of the steps is not determined. Typically, it proceeds from LSB to MSB, starting at i = 0; the multiplication by 2i is then typically replaced by incremental shifting of the P accumulator to the right between steps; low bits can be shifted out, and subsequent additions and subtractions can then be done just on the highest N bits of P.
There are many variations and optimizations on these details.
The algorithm is often described as converting strings of 1's in the multiplier to a high-order +1 and a low-order –1 at the ends of the string. When a string runs through the MSB, there is no high-order +1, and the net effect is interpretation as a negative of the appropriate value.
on P. Let m and r be the multiplicand and multiplier, respectively; and let x and y represent the number of bits in m and r.
The above mentioned technique is inadequate when the multiplicand is the largest negative number that can be represented (e.g. if the multiplicand has 4 bits then this value is −8). One possible correction to this problem is to add one more bit to the left of A, S and P. Below, we demonstrate the improved technique by multiplying −8 by 2 using 4 bits for the multiplicand and the multiplier:
where M is the multiplicand. The number of operations can be reduced to two by rewriting the same as
In fact, it can be shown that any sequence of 1's in a binary number can be broken into the difference of two binary numbers:
Hence, we can actually replace the multiplication by the string of ones in the original number by simpler operations, adding the multiplier, shifting the partial product thus formed by appropriate places, and then finally subtracting the multiplier. It is making use of the fact that we do not have to do anything but shift while we are dealing with 0s in a binary multiplier, and is similar to using the mathematical property that 99 = 100 − 1 while multiplying by 99.
This scheme can be extended to any number of blocks of 1s in a multiplier (including the case of single 1 in a block). Thus,
Booth's algorithm follows this scheme by performing an addition when it encounters the first digit of a block of ones (0 1) and a subtraction when it encounters the end of the block (1 0). This works for a negative multiplier as well. When the ones in a multiplier are grouped into long blocks, Booth's algorithm performs fewer additions and subtractions than the normal multiplication algorithm.
Multiplication algorithm
A multiplication algorithm is an algorithm to multiply two numbers. Depending on the size of the numbers, different algorithms are in use...
that multiplies two signed binary numbers in two's complement notation
Two's complement
The two's complement of a binary number is defined as the value obtained by subtracting the number from a large power of two...
. The algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
was invented by Andrew Donald Booth
Andrew Donald Booth
Andrew Donald Booth was a British electrical engineer, physicist and computer scientist who led the invention of the magnetic drum memory for computers and invented Booth's multiplication algorithm....
in 1950 while doing research on crystallography
Crystallography
Crystallography is the experimental science of the arrangement of atoms in solids. The word "crystallography" derives from the Greek words crystallon = cold drop / frozen drop, with its meaning extending to all solids with some degree of transparency, and grapho = write.Before the development of...
at Birkbeck College
Birkbeck, University of London
Birkbeck, University of London is a public research university located in London, United Kingdom and a constituent college of the federal University of London. It offers many Master's and Bachelor's degree programmes that can be studied either part-time or full-time, though nearly all teaching is...
in Bloomsbury
Bloomsbury
-Places:* Bloomsbury is an area in central London.* Bloomsbury , related local government unit* Bloomsbury, New Jersey, New Jersey, USA* Bloomsbury , listed on the NRHP in Maryland...
, London
London
London is the capital city of :England and the :United Kingdom, the largest metropolitan area in the United Kingdom, and the largest urban zone in the European Union by most measures. Located on the River Thames, London has been a major settlement for two millennia, its history going back to its...
. Booth used desk calculators that were faster at shift
Arithmetic shift
In computer programming, an arithmetic shift is a shift operator, sometimes known as a signed shift . For binary numbers it is a bitwise operation that shifts all of the bits of its operand; every bit in the operand is simply moved a given number of bit positions, and the vacant bit-positions are...
ing than adding and created the algorithm to increase their speed. Booth's algorithm is of interest in the study of computer architecture
Computer architecture
In computer science and engineering, computer architecture is the practical art of selecting and interconnecting hardware components to create computers that meet functional, performance and cost goals and the formal modelling of those systems....
.
The algorithm
Booth's algorithm examines adjacent pairs of bits of the N-bit multiplier Y in signed two's complementTwo's complement
The two's complement of a binary number is defined as the value obtained by subtracting the number from a large power of two...
representation, including an implicit bit below the least significant bit, y-1 = 0. For each bit yi, for i running from 0 to N-1, the bits yi and yi-1 are considered. Where these two bits are equal, the product accumulator P is left unchanged. Where yi = 0 and yi-1 = 1, the multiplicand times 2i is added to P; and where yi = 1 and yi-1 = 0, the multiplicand times 2i is subtracted from P. The final value of P is the signed product.
The representation of the multiplicand and product are not specified; typically, these are both also in two's complement representation, like the multiplier, but any number system that supports addition and subtraction will work as well. As stated here, the order of the steps is not determined. Typically, it proceeds from LSB to MSB, starting at i = 0; the multiplication by 2i is then typically replaced by incremental shifting of the P accumulator to the right between steps; low bits can be shifted out, and subsequent additions and subtractions can then be done just on the highest N bits of P.
There are many variations and optimizations on these details.
The algorithm is often described as converting strings of 1's in the multiplier to a high-order +1 and a low-order –1 at the ends of the string. When a string runs through the MSB, there is no high-order +1, and the net effect is interpretation as a negative of the appropriate value.
A typical implementation
Booth's algorithm can be implemented by repeatedly adding (with ordinary unsigned binary addition) one of two predetermined values A and S to a product P, then performing a rightward arithmetic shiftArithmetic shift
In computer programming, an arithmetic shift is a shift operator, sometimes known as a signed shift . For binary numbers it is a bitwise operation that shifts all of the bits of its operand; every bit in the operand is simply moved a given number of bit positions, and the vacant bit-positions are...
on P. Let m and r be the multiplicand and multiplier, respectively; and let x and y represent the number of bits in m and r.
- Determine the values of A and S, and the initial value of P. All of these numbers should have a length equal to (x + y + 1).
- A: Fill the most significant (leftmost) bits with the value of m. Fill the remaining (y + 1) bits with zeros.
- S: Fill the most significant bits with the value of (−m) in two's complement notation. Fill the remaining (y + 1) bits with zeros.
- P: Fill the most significant x bits with zeros. To the right of this, append the value of r. Fill the least significant (rightmost) bit with a zero.
- Determine the two least significant (rightmost) bits of P.
- If they are 01, find the value of P + A. Ignore any overflow.
- If they are 10, find the value of P + S. Ignore any overflow.
- If they are 00, do nothing. Use P directly in the next step.
- If they are 11, do nothing. Use P directly in the next step.
- Arithmetically shiftArithmetic shiftIn computer programming, an arithmetic shift is a shift operator, sometimes known as a signed shift . For binary numbers it is a bitwise operation that shifts all of the bits of its operand; every bit in the operand is simply moved a given number of bit positions, and the vacant bit-positions are...
the value obtained in the 2nd step by a single place to the right. Let P now equal this new value. - Repeat steps 2 and 3 until they have been done y times.
- Drop the least significant (rightmost) bit from P. This is the product of m and r.
Example
Find 3 × (−4), with m = 3 and r = −4, and x = 4 and y = 4:- m = 0011, -m = 1101, r = 1100
- A = 0011 0000 0
- S = 1101 0000 0
- P = 0000 1100 0
- Perform the loop four times :
- P = 0000 1100 0. The last two bits are 00.
- P = 0000 0110 0. Arithmetic right shift.
- P = 0000 0110 0. The last two bits are 00.
- P = 0000 0011 0. Arithmetic right shift.
- P = 0000 0011 0. The last two bits are 10.
- P = 1101 0011 0. P = P + S.
- P = 1110 1001 1. Arithmetic right shift.
- P = 1110 1001 1. The last two bits are 11.
- P = 1111 0100 1. Arithmetic right shift.
- P = 0000 1100 0. The last two bits are 00.
- The product is 1111 0100, which is −12.
The above mentioned technique is inadequate when the multiplicand is the largest negative number that can be represented (e.g. if the multiplicand has 4 bits then this value is −8). One possible correction to this problem is to add one more bit to the left of A, S and P. Below, we demonstrate the improved technique by multiplying −8 by 2 using 4 bits for the multiplicand and the multiplier:
- A = 1 1000 0000 0
- S = 0 1000 0000 0
- P = 0 0000 0010 0
- Perform the loop four times :
- P = 0 0000 0010 0. The last two bits are 00.
- P = 0 0000 0001 0. Right shift.
- P = 0 0000 0001 0. The last two bits are 10.
- P = 0 1000 0001 0. P = P + S.
- P = 0 0100 0000 1. Right shift.
- P = 0 0100 0000 1. The last two bits are 01.
- P = 1 1100 0000 1. P = P + A.
- P = 1 1110 0000 0. Right shift.
- P = 1 1110 0000 0. The last two bits are 00.
- P = 1 1111 0000 0. Right shift.
- P = 0 0000 0010 0. The last two bits are 00.
- The product is 11110000 (after discarding the first and the last bit) which is −16.
How it works
Consider a positive multiplier consisting of a block of 1s surrounded by 0s. For example, 00111110. The product is given by :
where M is the multiplicand. The number of operations can be reduced to two by rewriting the same as
In fact, it can be shown that any sequence of 1's in a binary number can be broken into the difference of two binary numbers:
Hence, we can actually replace the multiplication by the string of ones in the original number by simpler operations, adding the multiplier, shifting the partial product thus formed by appropriate places, and then finally subtracting the multiplier. It is making use of the fact that we do not have to do anything but shift while we are dealing with 0s in a binary multiplier, and is similar to using the mathematical property that 99 = 100 − 1 while multiplying by 99.
This scheme can be extended to any number of blocks of 1s in a multiplier (including the case of single 1 in a block). Thus,
Booth's algorithm follows this scheme by performing an addition when it encounters the first digit of a block of ones (0 1) and a subtraction when it encounters the end of the block (1 0). This works for a negative multiplier as well. When the ones in a multiplier are grouped into long blocks, Booth's algorithm performs fewer additions and subtractions than the normal multiplication algorithm.