Бутов алгоритам

Бутов алгоритам служи за множење два неозначена бинарна броја записана у комплементу двојке. Алгоритам је измислио Ендру Доналд Бут 1950. године, док је вршио истраживање о кристалографији (види још кристалографија) на Биркбек колеџу у Лондону. Бут је користио калкулаторе који су били бржи у померању (Шифтовању) цифара него у њиховом сабирању и из тог разлога је осмислио алгоритам који ће повећати брзину сабирања. Бутов алгоритам има велики допринос архитектури рачунара.

Алгоритам

Бутов алгоритам се састоји од множиоца и множеника који су смештени у Q и M регистре. Такође постоји и 1-битни регистар који је смештен логички десно од најмање значајног бита (Q₀) регистра Q и означен је као Q_-1; Његову употребу ћемо ускоро објаснити. Резултати множења ће се појавити у регистрима A и Q. А и Q_-1 се иницијализују на 0. Управљачка логика скенира битове множиоца, по један истовремено. Сада, како се сваки бит испитује, то се ради и са битовима на његовој десној страни. Ако су два бита иста (1-1 или 0-0), онда се сви битови регистра А, Q и Q_-1 померају удесно за један бит. Ако се два бита разликују, онда се множеник додаје регистру А, или од њега одузима, зависно од тога да ли су два бита 0-1 или 1-0. Иза сабирања или одузимања, долази до померања. У оба случаја, померање удесно је такво да се бит у регистру А крајње лево, А_n-1, не помера само у А_n-2, него остаје и у А_n-1. То се захтева да би се сачувао предзнак броја у А и Q. То је познато као аритметичко померање зато што задржава бит предзнака.

На слици 1 приказана је секвенца догађаја у Бутовом алгоритму за множење 7 пута 3. Иста операција је компактније приказана на слици 1.2а.

A	Q	Q-1	M	Почетне вредности
0000	0011	0	0111
1001	0011	0	0111	А → А-М
1100	1001	1	0111	Померање - Крај првог циклуса.
1110	0100	1	0111	Померање - Крај другог циклуса.
0101	0100	1	0111	А → А+М
0010	1010	0	0111	Померање - Крај трећег циклуса.
0001	0101	0	0111	Померање - Крај четвртог циклуса

Слика 1.

Остатак слике 1.2 даје друге примере алгоритма. Као што се може видети, он ради у било којој комбинацији позитивних и негативних бројева. Запазите и ефикасност алгоритма. Блокови цифара 1 или 0 се прескачу, са просечно само једним сабирањем или одузимањењм по блоку.

a) 7 x 3 = 21		(b) 7 x (-3)=(-21)
0111		0111
x 0011	(0)	x 1101	(0)
11111001	1-0	11111001	1-0
0000000	1-1	0000111	0-1
000111	0-1	111001	1-0
00010101	(21)	00010101	(-21)

Слика 1.2

Зашто ради Бутов алгоритам? Најпре размотрите случај позитивног множиоца. Посебно размотрите позитиван множилац кој се састоји од једног блока цифара 1, окруженог цифрама 0 (на пример, 00011110). Као што наме је познато, множење може да се постигне сабирањем одговарајуће померених копија множеника.

М x (00011110) = М x (2⁴+2³+2¹) = М x (16+ 8+ 4+ 2)= М x 30;

Број таквих операција може да се смањи на две ако запазимо да је:

2ⁿ+2^n-1 + . . . +2^n-k = 2ⁿ⁺¹ - 2^n-k једначина (1.1)

Тако производ може да се направи једним сабирањем и једним одузимањем множеника. Та шема се проширује на било који број блокова цифара 1 у множиоцу, укључујући и случај када се са једном цифром 1 поступа као са блоком.

M x (01111010) = М x (2⁶+2⁵+2⁴+2³+2¹) = М x (2⁷-2³+2²-2¹)

М x (00011110) = М x (2⁵ - 2¹) = М x (32 - 2) = М x 30

Бутов алгоритам се повинује тој шеми извођењем операције одузимања када се наиђе на прву цифру 1 блока (1-0) и операцију сабирања када се наиђе на крај блока (0-1). Да бисмо показали да иста шема ради за негативан множилац, треба да посматрамо следеће. Нека је Х негативан број у нотацији комплемента двојке:

Представљање = {1 x_n-2, x_n-3, … , x₁, x₀} Онда вредност Х може да се изрази на следећи начин:

X = -2^n-1+(x_n-2 * 2^n-2 )+(x_n-3 * 2^n-3 )+⋯+(x₁* 2¹ )+(x₀* 2⁰) једначина (1.2)

Бит крајње лево у X је 1 зато што је X негативан. Претпоставите да је крајња лева цифра 0 на к-тој позицији. Према томе, X је у облику Представљање X = {111…10x_к-3 x_к-2… x₁ x₀} (1.3) Онда је вредност Х

X=-2^n-1+^2n-2+⋯+2^k+1+(x_k-1 X 2^k-1) )+⋯+(x₀ X 2⁰) једначина (1.4)

Из једначине (1.1), можемо да кажемо да је:

2^n-2+2^n-3+ . . . +2^к+1)= 2^n-1 - 2^к+1

Преуређујући, добијамо:

-2^n-1+2^n-2 + . . . +2^к+1 = -2^k+1 једначина (1.5)

Смењујучћи једначину (1.5) у (1.4), имамо :

X = -2^к+1+(x_k-1 * 2^k-1) )+...+(x₀*2⁰) једначина (1.6)

Најзад можемо да се вратимо Бутовом алгоритму. Памтећи представљање Х [једначина (1.3)], јасно је да се са свим битовима од x₀ до цифре 0 крајње лево поступа исправно зато што они производе све чланове у једначини (1.6) сем (-2^к+1) и зато су у правилном облику. Када алгоритам скенира преко 0 крајње лево и наиђе на следећу цифру 1(2^k+1), долази до прелаза 1-0 и дешава се одузимање (-2^k+1). То је преостали члан у једначини (1.6).

Пример

Као пример узећемо множење неког множеника са бројем (-6). У представљању помоћу комплемента двојке, користећи 8-битну реч, (-6) се представља као 11111010.

-6 =-2⁷+2⁶+2⁵+2⁴+2³+2¹

Ово чинилац може лако проверити. Па према томе,

М x (11111010) = М x (-2⁷+2⁶+2⁵+2⁴+2³+2¹)

Када употребимо једну од једначина добијамо следеће:

М x (11111010) = М x (-2³+2¹)

Чинилац такође може и ово да провери, и даље је М x (-6). Најзад, следи претходно закључивање.

М x (11111010) = М x (-2³+2²-2¹).

Можемо видети да се Бутов алгоритам повинује тој шеми. Он изводи одузимање када се наиђе на прву цифру 1 (10), сабирање када се наиђе на (01) и најзад још једном одузимање када се наиђе на прву цифру 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\times \,^{\prime \prime }0\;1\;0\;0\;0\;0{\mbox{-1}}\;0\,^{\prime \prime }=M\times (2^{6}-2^{1})=M\times 62.$

У ствари, било који блок јединица у бинарном броју можемо написати као разлику два бинарна броја.

$(\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). Према томе,

$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}}\;1{\mbox{-1}}\;0\,^{\prime \prime }=M\times (2^{6}-2^{3}+2^{2}-2^{1})=M\times 58.$

Бутов алгоритам следи ову шему и тако извршава сабирање када наиђе на прве две цифре у блоку (0 1) и одузимање када наиђе крај блока (1 0). Такође ово ради за негативан коефицијент. Када су они у множиоцу груписани у дуге блокове, Бутов алгоритам обавља мање сабирања и одузимања од нормалног алгоритма множења.

Литература

• Andrew D. Booth. A signed binary multiplication technique. The Quarterly Journal of Mechanics and Applied Mathematics, Volume IV, Pt. 2, 1951 [1]
• Collin, Andrew. Andrew Booth's Computers at Birkbeck College Архивирано на сајту Wayback Machine (25. фебруар 2021). Resurrection, Issue 5, Spring 1993. London: Computer Conservation Society.
• Patterson, David and John Hennessy. Computer Organization and Design: The Hardware/Software Interface, Second Edition. ISBN 978-1-55860-428-5. San Francisco, California: Morgan Kaufmann Publishers. 1998.

Споњашње Везе

• Radix-4 Booth Encoding
• Radix-8 Booth Encoding in A Formal Theory of RTL and Computer Arithmetic
• Booth's Algorithm JavaScript Simulator
• Implementation in Python