Изворни код странице Бутов алгоритам

'''Бутов алгоритам''' служи за [[множење]] два неозначена бинарна броја записана у комплементу двојке. Алгоритам је измислио Ендру Доналд Бут 1950. године, док је вршио истраживање о кристалографији (види још [[кристалографија]]) на Биркбек колеџу у Лондону. Бут је користио калкулаторе који су били бржи у померању (Шифтовању) цифара него у њиховом сабирању и из тог разлога је осмислио алгоритам који ће повећати брзину сабирања. Бутов алгоритам има велики допринос архитектури рачунара.<ref name"Stallings">-{William Stallings}- Ауторизован превод са енглеског језика деветог издања књиге -{"Computer Organization and Architecture ''Designing for Performance ninth edition''"}-.</ref>

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

На слици 1 приказана је секвенца догађаја у Бутовом алгоритму за множење 7 пута 3. Иста операција је компактније приказана на слици 1.2а.
{| class="wikitable"
|-
! A!!      Q!!     Q<sub>-1</sub> !! 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 се прескачу, са просечно само једним сабирањем или одузимањењм по блоку.
    
{| class="wikitable"
|-
! 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<sup>4</sup>+2<sup>3</sup>+2<sup>1</sup>) = М x (16+ 8+ 4+ 2)= М x 30;'''

Број таквих операција може да се смањи на две ако запазимо да је:
: '''2<sup>n</sup>+2<sup>n-1</sup> + . . . +2<sup>n-k</sup> = 2<sup>n+1</sup> - 2<sup>n-k</sup>''' једначина (1.1)

Тако производ може да се направи једним сабирањем и једним одузимањем множеника. Та шема се проширује на било који број блокова цифара 1 у множиоцу, укључујући и случај када се са једном цифром 1 поступа као са блоком.
: '''M x (01111010) = М x (2<sup>6</sup>+2<sup>5</sup>+2<sup>4</sup>+2<sup>3</sup>+2<sup>1</sup>) = М x (2<sup>7</sup>-2<sup>3</sup>+2<sup>2</sup>-2<sup>1</sup>)'''
: '''М x (00011110) = М x (2<sup>5</sup> - 2<sup>1</sup>) = М x (32 - 2) = М x 30'''

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

Представљање = '''{1 x<sub>n-2</sub>, x<sub>n-3</sub>, … , x<sub>1</sub>, x<sub>0</sub>}'''
Онда вредност Х може да се изрази на следећи начин:
: '''X = -2<sup>n-1</sup>+(x<sub>n-2</sub> * 2<sup>n-2</sup> )+(x<sub>n-3</sub> * 2<sup>n-3</sup> )+⋯+(x<sub>1</sub>* 2<sup>1</sup> )+(x<sub>0</sub>* 2<sup>0</sup>)''' једначина (1.2)

Бит крајње лево у X је 1 зато што је X негативан. Претпоставите да је крајња лева цифра 0 на к-тој позицији. Према томе, X је у облику
Представљање '''X = {111…10x<sub>к-3</sub> x<sub>к-2</sub>… x<sub>1</sub> x<sub>0</sub>}''' (1.3)
Онда је вредност Х
: '''X=-2<sup>n-1</sup>+<sup>2n-2</sup>+⋯+2<sup>k+1</sup>+(x<sub>k-1</sub> X 2<sup>k-1</sup>) )+⋯+(x<sub>0</sub> X 2<sup>0</sup>)''' једначина (1.4)

Из једначине (1.1), можемо да кажемо да је:
: '''2<sup>n-2</sup>+2<sup>n-3</sup>+ . . . +2<sup>к+1</sup>)= 2<sup>n-1</sup> - 2<sup>к+1</sup>'''

Преуређујући, добијамо:
: '''-2<sup>n-1</sup>+2<sup>n-2</sup> + . . . +2<sup>к+1</sup> = -2<sup>k+1</sup>''' једначина (1.5)

Смењујучћи једначину (1.5) у (1.4), имамо :
: '''X = -2<sup>к+1</sup>+(x<sub>k-1</sub> * 2<sup>k-1</sup>) )+...+(x<sub>0</sub>*2<sup>0</sup>)''' једначина (1.6)

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

== Пример ==
Као пример узећемо множење неког множеника са бројем (-6). У представљању помоћу комплемента двојке,
користећи 8-битну реч, (-6) се представља као 11111010.
: '''-6 =-2<sup>7</sup>+2<sup>6</sup>+2<sup>5</sup>+2<sup>4</sup>+2<sup>3</sup>+2<sup>1</sup>'''

Ово чинилац може лако проверити. Па према томе,
: '''М x (11111010) = М x (-2<sup>7</sup>+2<sup>6</sup>+2<sup>5</sup>+2<sup>4</sup>+2<sup>3</sup>+2<sup>1</sup>)'''

Када употребимо једну од једначина добијамо следеће:
: '''М x (11111010) = М x (-2<sup>3</sup>+2<sup>1</sup>)'''

Чинилац такође може и ово да провери, и даље је М x (-6). Најзад, следи претходно закључивање.
: '''М x (11111010) = М x (-2<sup>3</sup>+2<sup>2</sup>-2<sup>1</sup>).'''

Можемо видети да се Бутов алгоритам повинује тој шеми. Он изводи одузимање када се наиђе на прву цифру 1 (10), сабирање када се наиђе на (01) и најзад још једном одузимање када се наиђе на прву цифру 1 следећег блока.

Према томе, Бутов алгоритам изводи мање сабирања и одузимања него неки директинији алгоритам.

== Како алгоритам ради ==

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

: <math> 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 </math>

Где је М-множеник. Број операција може бити двоструко мањи ако напишемо овако:

: <math> M \times \,^{\prime\prime} 0 \; 1 \; 0 \; 0 \; 0 \; 0 \mbox{-1} \; 0 \,^{\prime\prime} = M \times (2^6 - 2^1) = M \times 62. </math>

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

: <math> (\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. </math>

Дакле, ми заправо мењамо множење низом јединица у оригиналном броју, неким простијим операцијама, онда додајемо множилац, па померамо (шифтујемо) делимични производ који је формиран на одговарајућим местима и на крају одузимамо множилац. Стога ми само померамо (шифтујемо) цифре у бинарном множиоцу. Ова шема се може проширити на било који број блокова јединица у множиоцу (укључујући и случај једне у блоку 1). Према томе,

: <math> 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 </math>
: <math> 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. </math>

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

== Референце ==
{{reflist}}

== Литература ==
{{Литература}}-{
* Andrew D. Booth. A signed binary multiplication technique. The Quarterly Journal of Mechanics and Applied Mathematics, Volume IV, Pt. 2, 1951 [http://bwrc.eecs.berkeley.edu/Classes/icdesign/ee241_s00/PAPERS/archive/booth51.pdf] {{Wayback|url=http://bwrc.eecs.berkeley.edu/Classes/icdesign/ee241_s00/PAPERS/archive/booth51.pdf |date=20120717071922 }}
* Collin, Andrew. [http://www.cs.man.ac.uk./CCS/res/res05.htm#e Andrew Booth's Computers at Birkbeck College] {{Wayback|url=http://www.cs.man.ac.uk./CCS/res/res05.htm#e |date=20210225001655 }}. ''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.
}-{{Литература крај}}

== Споњашње Везе ==
* [http://www.geoffknagge.com/fyp/booth.shtml -{Radix-4 Booth Encoding}-]
* -{[https://web.archive.org/web/20120216060633/http://www.russinoff.com/libman/text/node38.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}-]
* [http://philosophyforprogrammers.blogspot.com/2011/05/booths-multiplication-algorithm-in.html -{Implementation in Python}-]

{{нормативна контрола}}

[[Категорија:Бинарна аритметика]]
[[Категорија:Рачунарска аритметика]]
[[Категорија:Алгоритми]]