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

Из Википедије, слободне енциклопедије

Бутов алгоритам служи за множење два неозначена бинарна броја записана у комплементу двојке. Алгоритам је измислио Ендру Доналд Бут 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. Добијамо производ:

 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). Такође ово ради за негативан коефицијент. Када су они у множиоцу груписани у дуге блокове, Бутов алгоритам обавља мање сабирања и одузимања од нормалног алгоритма множења.

Референце[уреди]

  1. ^ 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]
  • Collin, Andrew. Andrew Booth's Computers at Birkbeck College. 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 1-55860-428-6. San Francisco, California: Morgan Kaufmann Publishers. 1998.

Споњашње Везе[уреди]