Booth算法

**布斯乘法算法**（英語：Booth's multiplication algorithm）是計算機中一種利用數的 2 的補碼形式來計算乘法的算法。該算法由安德魯・唐納德・布思於 1950 年發明，當時他在倫敦大學柏貝克學院做晶體學研究。布斯曾使用過一種台式計算器，由於用這種計算器來做移位計算比加法快，他發明了該算法來加快計算速度。布斯算法在計算機體系結構學科中備受關注。

## 算法描述

對於 _N_ 位乘數 _Y_，布斯算法檢查其 2 的補碼形式的最後一位和一個隱含的低位，命名為 _y_-1，初始值為 0。對於 _y_i, _i_ = 0, 1, ..., _N_ - 1，考察 _y_i 和 _y_i - 1。當這兩位相同時，存放積的累加器 _P_ 的值保持不變。當 _y_i = 0 且 _y_i - 1 = 1 時，被乘數乘以 2i 加到 _P_ 中。當 _y_i = 1 且 _y_i - 1 = 0 時，從 _P_ 中減去被乘數乘以 2i 的值。算法結束後，_P_ 中的數即為乘法結果。

該算法對被乘數和積這兩個數的表達方式並沒有作規定。一般地，和乘數一樣，可以採用 2 的補碼方式表達。也可以採用其他計數形式，只要支持加減法就行。這個算法從乘數的最低位執行到最高位，從 _i_ = 0 開始，接下來和 2i 的乘法被累加器 _P_ 的算術右移所取代。較低位可以被移出，加減法可以只在 _P_ 的前 _N_ 位上進行。

## 典型實現

布斯算法的實現，可以通過重複地在 _P_ 上加兩個預設值 _A_ 和 S 其中的一個，然後對 _P_ 實施算術右移。設 _m_ 和 _r_ 分別為被乘數和乘數，再令 _x_ 和 _y_ 分別為 _m_ 和 _r_ 中的數字位數。

1. 確定 _A_ 和 _S_ 的值，以及 _P_ 的初始值。這三個數字的長度都應等於（_x_ + _y_ + 1）：
  1. 對於 _A_，以 _m_ 的值填充前 x 位（最靠左的位），用零填滿剩下的（_y_ + 1）位；
  2. 對於 _S_，以（ - _m_）的值填充前 x 位，用零填滿剩下的（_y_ + 1）位；
  3. 對於 _P_：用 0 填滿最左的 _x_ 位，將 _r_ 的值附加在尾部；最右一位用零占位（輔助位，當 i=0 時 i-1=-1, 指的就是這個輔助位）；
2. 考察 _P_ 的最右兩位：
  1. 如果等於 01，求出 _P_ + _A_ 的值，忽略上溢；
  2. 如果等於 10，求出 _P_ + _S_ 的值，忽略上溢；
  3. 如果等於 00，不做任何運算，在下一步中直接採用 _P_ 的值；
  4. 如果等於 11，不做任何運算，在下一步中直接採用 _P_ 的值。
3. 對第 2 步中得到的值進行算術右移一位，並將結果賦給 _P_；
4. 重複第 2 步和第 3 步，一共做 _y_ 次；
5. 舍掉 _P_ 的最右一位，得到的即為 _m_ 和 _r_ 的積。

換另一種說法：把前 x 位用一個單獨的數 R0 表示，中間 y 位用另一個數表示 R1 表示，輔助位用 Z 表示
在這裡，要通過重複的把 R0 加上或者減去 m 來得到結果。具體如下：
初始值 R0=0,R1=r.Z=0, 此時來考查 yi 和 yi-1 這兩位，在這裡就是 r 的最後一位和 Z 的值。這裡要說下為什麼每次看的都是這兩位了。在下邊每次運算後都會把 R0,R1,Z 中的值右移一次，RO 的最後一位移入 R1 的高位，R1 的最後一位移入 Z。這裡要注意的是在右移 R0 時，如果他的最高位是 1, 則移位後最高位用 1 填充，如果最高位是 0，移位後最高位用 0 填充。接下來要按 r 的最後一位和 Z 的值來判斷怎麼加減了：

1. 1. 如果為 01, 則 R0+m，進位忽略。然後 R0,R1,Z 右移一位，再下一步判斷，直到把 R1 的每一位都判斷過後為結束
  2. 如果為 10, 則 R0-m，借位忽略（只要 x 位的 R0 的值）。然後 R0,R1,Z 右移一位，再下一步判斷，直到把 R1 的每一位都判斷過後為結束
  3. 如果為 00 或是 11, 則 R0 的值保持不變。然後 R0,R1,Z 右移一位，再下一步判斷，直到把 R1 的每一位都判斷過後為結束

最後是結果，結果就是 R0 並上 R1 的值。比如 R0=3,R1=25, 結果就是 325.

## 算法原理

考慮一個由若干個 0 包圍著若干個 1 的正的二進位乘數，比如 00111110，積可以表達為：

　
: $M\times \,^{\prime \prime }0\;0\;1\;1\;1\;1\;1\;0\,^{\prime \prime }=M\times (2^{5}+2^{4}+2^{3}+2^{2}+2^{1})=M\times 62$

其中，M 代表被乘數。變形為下式可以使運算次數可以減為兩次：

　
: $M\times \,^{\prime \prime }0\;1\;0\;0\;0\;0{\mbox{-1}}\;0\,^{\prime \prime }=M\times (2^{6}-2^{1})=M\times 62$ 。

事實上，任何二進位數中連續的 1 可以被分解為兩個二進位數之差：

　
: $(\ldots 0\overbrace {1\ldots 1} ^{n}0\ldots )_{2}\equiv (\ldots 1\overbrace {0\ldots 0} ^{n}0\ldots )_{2}-(\ldots 0\overbrace {0\ldots 1} ^{n}0\ldots )_{2}$ 。

因此，我們可以用更簡單的運算來替換原數中連續為 1 的數字的乘法，通過加上乘數，對部分積進行移位運算，最後再將之從乘數中減去。它利用了我們在針對為零的位做乘法時，不需要做其他運算，只需移位這一特點，這很像我們在做和 99 的乘法時利用 99 = 100 − 1 這一性質。這種模式可以擴展應用於任何一串數字中連續為 1 的部分（包括只有一個 1 的情況）。那麼，

　
: $M\times \,^{\prime \prime }0\;0\;1\;1\;1\;0\;1\;0\,^{\prime \prime }=M\times (2^{5}+2^{4}+2^{3}+2^{1})=M\times 58$

　
: $M\times \,^{\prime \prime }0\;1\;0\;0{\mbox{-1}}\;0\;1\;0\,^{\prime \prime }=M\times (2^{6}-2^{3}+2^{1})=M\times 58$ 。

布斯算法遵從這種模式，它在遇到一串數字中的第一組從 0 到 1 的變化時（即遇到 01 時）執行加法，在遇到這一串連續 1 的尾部時（即遇到 10 時）執行減法。這在乘數為負時同樣有效。當乘數中的連續 1 比較多時（形成比較長的 1 串時），布斯算法較一般的乘法算法執行的加減法運算少。

## 參考來源

## 延伸閱讀

1. Andrew D. Booth. A signed binary multiplication technique. The Quarterly Journal of Mechanics and Applied Mathematics, Volume IV, Pt. 2 [1] （頁面存檔備份，存於網際網路檔案館）
2. Collin, Andrew. Andrew Booth's Computers at Birkbeck College （頁面存檔備份，存於網際網路檔案館）. _Resurrection_, Issue 5, Spring 1993. London: Computer Conservation Society.
3. Patterson, David and John Hennessy. _Computer Organization and Design: The Hardware/Software Interface, Second Edition_. ISBN 1-55860-428-6. San Francisco, California: Morgan Kaufmann Publishers. 1998.
4. Stallings, William. _Computer Organization and Architecture: Designing for performance, Fifth Edition_. ISBN 0-13-081294-3. New Jersey: Prentice-Hall, Inc.. 2000.

## 外部連結

* Radix-4 Booth Encoding （頁面存檔備份，存於網際網路檔案館）
* Radix-8 Booth Encoding in A Formal Theory of RTL and Computer Arithmetic
* Booth's Algorithm
* Booth's Algorithm JavaScript Simulator （頁面存檔備份，存於網際網路檔案館）
* Implementation in Verilog
* Implementation in Python （頁面存檔備份，存於網際網路檔案館）
* 布斯算法 (帶符號的二進位乘法)