Бутов алгоритам
Бутов алгоритам служи за множење два неозначена бинарна броја записана у комплементу двојке. Алгоритам је измислио Ендру Доналд Бут 1950. године, док је вршио истраживање о кристалографији (види још кристалографија) на Биркбек колеџу у Лондону. Бут је користио калкулаторе који су били бржи у померању (Шифтовању) цифара него у њиховом сабирању и из тог разлога је осмислио алгоритам који ће повећати брзину сабирања. Бутов алгоритам има велики допринос архитектури рачунара.[1]
Алгоритам
[уреди | уреди извор]Бутов алгоритам се састоји од множиоца и множеника који су смештени у Q и M регистре. Такође постоји и 1-битни регистар који је смештен логички десно од најмање значајног бита (Q0) регистра 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 (24+23+21) = М x (16+ 8+ 4+ 2)= М x 30;
Број таквих операција може да се смањи на две ако запазимо да је:
- 2n+2n-1 + . . . +2n-k = 2n+1 - 2n-k једначина (1.1)
Тако производ може да се направи једним сабирањем и једним одузимањем множеника. Та шема се проширује на било који број блокова цифара 1 у множиоцу, укључујући и случај када се са једном цифром 1 поступа као са блоком.
- M x (01111010) = М x (26+25+24+23+21) = М x (27-23+22-21)
- М x (00011110) = М x (25 - 21) = М x (32 - 2) = М x 30
Бутов алгоритам се повинује тој шеми извођењем операције одузимања када се наиђе на прву цифру 1 блока (1-0) и операцију сабирања када се наиђе на крај блока (0-1). Да бисмо показали да иста шема ради за негативан множилац, треба да посматрамо следеће. Нека је Х негативан број у нотацији комплемента двојке:
Представљање = {1 xn-2, xn-3, … , x1, x0} Онда вредност Х може да се изрази на следећи начин:
- X = -2n-1+(xn-2 * 2n-2 )+(xn-3 * 2n-3 )+⋯+(x1* 21 )+(x0* 20) једначина (1.2)
Бит крајње лево у X је 1 зато што је X негативан. Претпоставите да је крајња лева цифра 0 на к-тој позицији. Према томе, X је у облику Представљање X = {111…10xк-3 xк-2… x1 x0} (1.3) Онда је вредност Х
- X=-2n-1+2n-2+⋯+2k+1+(xk-1 X 2k-1) )+⋯+(x0 X 20) једначина (1.4)
Из једначине (1.1), можемо да кажемо да је:
- 2n-2+2n-3+ . . . +2к+1)= 2n-1 - 2к+1
Преуређујући, добијамо:
- -2n-1+2n-2 + . . . +2к+1 = -2k+1 једначина (1.5)
Смењујучћи једначину (1.5) у (1.4), имамо :
- X = -2к+1+(xk-1 * 2k-1) )+...+(x0*20) једначина (1.6)
Најзад можемо да се вратимо Бутовом алгоритму. Памтећи представљање Х [једначина (1.3)], јасно је да се са свим битовима од x0 до цифре 0 крајње лево поступа исправно зато што они производе све чланове у једначини (1.6) сем (-2к+1) и зато су у правилном облику. Када алгоритам скенира преко 0 крајње лево и наиђе на следећу цифру 1(2k+1), долази до прелаза 1-0 и дешава се одузимање (-2k+1). То је преостали члан у једначини (1.6).
Пример
[уреди | уреди извор]Као пример узећемо множење неког множеника са бројем (-6). У представљању помоћу комплемента двојке, користећи 8-битну реч, (-6) се представља као 11111010.
- -6 =-27+26+25+24+23+21
Ово чинилац може лако проверити. Па према томе,
- М x (11111010) = М x (-27+26+25+24+23+21)
Када употребимо једну од једначина добијамо следеће:
- М x (11111010) = М x (-23+21)
Чинилац такође може и ово да провери, и даље је М x (-6). Најзад, следи претходно закључивање.
- М x (11111010) = М x (-23+22-21).
Можемо видети да се Бутов алгоритам повинује тој шеми. Он изводи одузимање када се наиђе на прву цифру 1 (10), сабирање када се наиђе на (01) и најзад још једном одузимање када се наиђе на прву цифру 1 следећег блока.
Према томе, Бутов алгоритам изводи мање сабирања и одузимања него неки директинији алгоритам.
Како алгоритам ради
[уреди | уреди извор]Узмимо да је множилац позитиван, и да се састоји од блока јединица, окружених нулама, као што је 00111110. Добијамо производ:
Где је М-множеник. Број операција може бити двоструко мањи ако напишемо овако:
У ствари, било који блок јединица у бинарном броју можемо написати као разлику два бинарна броја.
Дакле, ми заправо мењамо множење низом јединица у оригиналном броју, неким простијим операцијама, онда додајемо множилац, па померамо (шифтујемо) делимични производ који је формиран на одговарајућим местима и на крају одузимамо множилац. Стога ми само померамо (шифтујемо) цифре у бинарном множиоцу. Ова шема се може проширити на било који број блокова јединица у множиоцу (укључујући и случај једне у блоку 1). Према томе,
Бутов алгоритам следи ову шему и тако извршава сабирање када наиђе на прве две цифре у блоку (0 1) и одузимање када наиђе крај блока (1 0). Такође ово ради за негативан коефицијент. Када су они у множиоцу груписани у дуге блокове, Бутов алгоритам обавља мање сабирања и одузимања од нормалног алгоритма множења.
Референце
[уреди | уреди извор]- ^ William Stallings Ауторизован превод са енглеског језика деветог издања књиге "Computer Organization and Architecture Designing for Performance ninth edition".
Литература
[уреди | уреди извор]- Andrew D. Booth. A signed binary multiplication technique. The Quarterly Journal of Mechanics and Applied Mathematics, Volume IV, Pt. 2, 1951 [1] Архивирано на сајту Wayback Machine (17. јул 2012)
- 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.