跳至內容

布斯乘法算法

維基百科,自由的百科全書

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

算法描述

[編輯]

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

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

典型實現

[編輯]

布斯算法的實現,可以通過重複地在P上加兩個預設值A S 其中的一個,然後對P實施算術右移。設mr分別為被乘數和乘數,再令xy分別為mr中的數字位數。

  1. 確定AS的值,以及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的最右一位,得到的即為mr的積。

換另一種說法:把前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. 如果為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代表被乘數。變形為下式可以使運算次數可以減為兩次:

事實上,任何二進制數中連續的1可以被分解為兩個二進制數之差:

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

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

參考來源

[編輯]
  1. ^ Chi-hau Chen. Signal processing handbook. CRC Press. 1988: 234. ISBN 9780824779566. 

延伸閱讀

[編輯]
  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.

外部連結

[編輯]