Booth's multiplication algorithm: Difference between revisions

Revision as of 08:22, 3 March 2025

Latest revision as of 11:30, 12 August 2025

(8 intermediate revisions by 4 users not shown)

Line 4:

==The algorithm==

Booth's algorithm examines adjacent pairs of [[bit]]s of the ''N''-bit multiplier ''Y'' in signed [[two's complement]] representation, including an implicit bit below the [[least significant bit]], ''y''₋₁ = 0. For each bit ''y''_''i'', for ''i'' running from 0 to ''N'' − 1, the bits ''y''_''i'' and ''y''_''i''−1 are considered. Where these two bits are equal, the product accumulator ''P'' is left unchanged. Where ''y''_''i'' = 0 and ''y''_''i''−1 = 1, the multiplicand times 2^''i'' is added to ''P''; and where ''y''_i = 1 and ''y''_i−1 = 0, the multiplicand times 2^''i'' is subtracted from ''P''. The final value of ''P''<nowiki> is the signed product.</nowiki>{{Citation needed|reason=No source for the algorithm|date=April 2025}}

The representations 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 [[Least significant bit|LSB]] to [[Most significant bit|MSB]], starting at ''i'' = 0; the multiplication by 2^''i'' 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''.<ref name="Chen_1992"/> There are many variations and optimizations on these details.

Line 25:

# [[arithmetic shift|Arithmetically shift]] 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'''<nowiki>.</nowiki>{{Citation needed|reason=No source for the Implementation|date=April 2025}}

==Example==

Line 65:

==How it works==

Consider a positive multiplier consisting of a block of 1s surrounded by 0s. For example, 00111110. The product is given by:

<math display="block"> M \times \,^begin{\prime\primearray}{|r|r|r|r|r|r|r|r|}\hline 0 \;& 0 \;& 1 \;& 1 \;& 1 \;& 1 \;& 1 \;& 0 \,^{\prime \primehline \end{array} = M \times (2^5 + 2^4 + 2^3 + 2^2 + 2^1) = M \times 62 </math>

where M is the multiplicand. The number of operations can be reduced to two by rewriting the same as

<math display="block"> M \times \,^begin{\prime\primearray}{|r|r|r|r|r|r|r|r|}\hline 0 \;& 1 \; & 0 \;& 0 \;& 0 \;& 0 \mbox{& -1} \;& 0 \\; ^{\primehline \primeend{array} = M \times (2^6 - 2^1) = M \times 62. </math>

In fact, it can be shown that any sequence of 1s in a binary number can be broken into the difference of two binary numbers:

Line 77:

This scheme can be extended to any number of blocks of 1s in a multiplier (including the case of a single 1 in a block). Thus,

<math display="block"> M \times \,^begin{\prime\primearray}{|r|r|r|r|r|r|r|r|}\hline 0 \;& 0 \;& 1 \;& 1 \;& 1 \;& 0 \;& 1 \;& 0 \,^{\prime \primehline \end{array}\ = M \times (2^5 + 2^4 + 2^3 + 2^1) = M \times 58 </math>

<math display="block"> M \times \,^begin{\prime\primearray}{|r|r|r|r|r|r|r|r|}\hline 0 \;& 1 \;& 0 \;& 0 \mbox{& -1} \;& 1 \mbox{& -1} \;& 0 \,^{\prime \primehline \end{array} = M \times (2^6 - 2^3 + 2^2 - 2^1) = M \times 58. </math>

Booth's algorithm follows this old scheme by performing an addition when it encounters the first digit of a block of ones (0 1) and 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.

== Pentium multiplier implementation ==

Intel's [[Pentium]] microprocessor uses a radix-8 variant of Booth's algorithm in its 64-bit hardware multiplier. Because of the way it implements the radix-8 multiplication, it needs a complex auxiliary circuit to perform the special case of multiplication by 3 in a way that minimizes latency, combining the use of [[carryCarry-lookahead adder|carry-lookahead]], [[carry-select addition|carry-select]], and [[Kogge–Stone addition]].<ref>{{Cite web |first=Ken|last=Shirriff|title=The Pentium contains a complicated circuit to multiply by three |url=https://www.righto.com/2025/03/pentium-multiplier-adder-reverse-engineered.html |access-date=2025-03-03|website=righto.com}}</ref>

== See also ==

Line 108:

* [https://web.archive.org/web/20171017093721/http://www.russinoff.com/libman/text/node65.html Radix-8 Booth Encoding] in [https://web.archive.org/web/20070927194831/http://www.russinoff.com/libman/ A Formal Theory of RTL and Computer Arithmetic]

* [http://www.ecs.umass.edu/ece/koren/arith/simulator/Booth/ Booth's Algorithm JavaScript Simulator]

* [httphttps://philosophyforprogrammers.blogspot.com/2011/05/booths-multiplication-algorithm-in.html Implementation in Python]

[[Category:1950 introductions]]