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

Алгоритам 
Бутов алгоритам се састоји од множиоца и множеника који су смештени у 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а.

Слика 1.

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

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

Референце

Литература 
-{
 Andrew D. Booth. A signed binary multiplication technique. The Quarterly Journal of Mechanics and Applied Mathematics, Volume IV, Pt. 2, 1951 
 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. . 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}-

Бинарна аритметика
Рачунарска аритметика
Алгоритми
Бутов алгоритам служи за множење два неозначена бинарна броја записана у комплементу двојке . Алгоритам је измислио Ендру Доналд Бут године , док је вршио истраживање о кристалографији ( види још кристалографија ) на Биркбек колеџу у Лондону . Бут је користио калкулаторе који су били бржи у померању ( Шифтовању ) цифара него у њиховом сабирању и из тог разлога је осмислио алгоритам који ће повећати брзину сабирања . Бутов алгоритам има велики допринос архитектури рачунара . Алгоритам Бутов алгоритам се састоји од множиоца и множеника који су смештени у Q и M регистре . Такође постоји ибитни регистар који је смештен логички десно од најмање значајног бита ( Q0 ) регистра Q и означен је као Q-1 ; Његову употребу ћемо ускоро објаснити . Резултати множења ће се појавити у регистрима A и Q . А и Q-1 се иницијализују на Управљачка логика скенира битове множиоца , по један истовремено . Сада , како се сваки бит испитује , то се ради и са битовима на његовој десној страни . Ако су два бита истаили онда се сви битови регистра А , Q и Q-1 померају удесно за један бит . Ако се два бита разликују , онда се множеник додаје регистру А , или од њега одузима , зависно од тога да ли су два битаили Иза сабирања или одузимања , долази до померања . У оба случаја , померање удесно је такво да се бит у регистру А крајње лево , Аn-1 , не помера само у Аn-2 , него остаје и у Аn-1 . То се захтева да би се сачувао предзнак броја у А и Q . То је познато као аритметичко померање зато што задржава бит предзнака . На слициприказана је секвенца догађаја у Бутовом алгоритму за множењепута Иста операција је компактније приказана на слици2а . Слика Остатак слике2 даје друге примере алгоритма . Као што се може видети , он ради у било којој комбинацији позитивних и негативних бројева . Запазите и ефикасност алгоритма . Блокови цифараилисе прескачу , са просечно само једним сабирањем или одузимањењм по блоку . Слика2 Зашто ради Бутов алгоритам ? Најпре размотрите случај позитивног множиоца . Посебно размотрите позитиван множилац кој се састоји од једног блока цифара окруженог цифрама( на пример , Као што наме је познато , множење може да се постигне сабирањем одговарајуће померених копија множеника . М x= М x23+21 ) = М x М x Број таквих операција може да се смањи на две ако запазимо да је : +2n-1 + \ . \ . \ . +2n-k =+1 --k једначина1 ) Тако производ може да се направи једним сабирањем и једним одузимањем множеника . Та шема се проширује на било који број блокова цифарау множиоцу , укључујући и случај када се са једном цифромпоступа као са блоком . M x= М x25+24+23+21 ) = М x22-21 ) М x= М x-= М x-= М x Бутов алгоритам се повинује тој шеми извођењем операције одузимања када се наиђе на прву цифрублокаи операцију сабирања када се наиђе на крај блока Да бисмо показали да иста шема ради за негативан множилац , треба да посматрамо следеће . Нека је Х негативан број у нотацији комплемента двојке : Представљање = { 1 xn-2 , xn-3 , … , x1 , x0 } Онда вредност Х може да се изрази на следећи начин : X =-1+( xn-2 *-2 ) +( xn-3 *-3 ) +⋯+( x1 * ) +( x0*једначина2 ) Бит крајње лево у X језато што је X негативан . Претпоставите да је крајња лева цифрана к-тој позицији . Према томе , X је у облику Представљање X = { 111…10xк-3 xк-2 … x1 x0 }3 ) Онда је вредност Х X=-2n-1+2n-2+⋯+2k+1+( xk-1 X-1 ) ) +⋯+( x0 Xједначина4 ) Из једначине1 ) , можемо да кажемо да је : -2+2n-3+ \ . \ . \ . +2к+1 ) =-1 -+1 Преуређујући , добијамо : -1+2n-2 + \ . \ . \ . +2к+1 =+1 једначина5 ) Смењујучћи једначину5 ) у4 ) , имамо \ : X =+1+( xk-1 *-1 ) )+...+( x0*20 ) једначина6 ) Најзад можемо да се вратимо Бутовом алгоритму . Памтећи представљање Х [ једначина3 ) ] , јасно је да се са свим битовима од x0 до цифрекрајње лево поступа исправно зато што они производе све чланове у једначини6 ) сем+1 ) и зато су у правилном облику . Када алгоритам скенира прекокрајње лево и наиђе на следећу цифру2k+1 ) , долази до прелазаи дешава се одузимање+1 ) . То је преостали члан у једначини6 ) . Пример Као пример узећемо множење неког множеника са бројем У представљању помоћу комплемента двојке , користећибитну реч,се представља као =-27+26+25+24+23+21 Ово чинилац може лако проверити . Па према томе , М x= М x26+25+24+23+21 ) Када употребимо једну од једначина добијамо следеће : М x= М x21 ) Чинилац такође може и ово да провери , и даље је М x Најзад , следи претходно закључивање . М x= М x22-21 ) . Можемо видети да се Бутов алгоритам повинује тој шеми . Он изводи одузимање када се наиђе на прву цифру( 10 ) , сабирање када се наиђе наи најзад још једном одузимање када се наиђе на прву цифруследећег блока . Према томе , Бутов алгоритам изводи мање сабирања и одузимања него неки директинији алгоритам . Како алгоритам ради Узмимо да је множилац позитиван , и да се састоји од блока јединица , окружених нулама , као што је Добијамо производ : Где је М-множеник . Број операција може бити двоструко мањи ако напишемо овако : У ствари , било који блок јединица у бинарном броју можемо написати као разлику два бинарна броја . Дакле , ми заправо мењамо множење низом јединица у оригиналном броју , неким простијим операцијама , онда додајемо множилац , па померамо ( шифтујемо ) делимични производ који је формиран на одговарајућим местима и на крају одузимамо множилац . Стога ми само померамо ( шифтујемо ) цифре у бинарном множиоцу . Ова шема се може проширити на било који број блокова јединица у множиоцу ( укључујући и случај једне у блоку Према томе , Бутов алгоритам следи ову шему и тако извршава сабирање када наиђе на прве две цифре у блоку1 ) и одузимање када наиђе крај блока0 ) . Такође ово ради за негативан коефицијент . Када су они у множиоцу груписани у дуге блокове , Бутов алгоритам обавља мање сабирања и одузимања од нормалног алгоритма множења . Референце Литература - { Andrew D. Booth . A signed binary multiplication technique . The Quarterly Journal of Mechanics and Applied Mathematics , Volume IV , Pt . Collin , Andrew . Andrew Booth's Computers at Birkbeck College \ . Resurrection , Issue Spring London : Computer Conservation Society . Patterson , David and John Hennessy . Computer Organization and Design : The Hardware / Software Interface , Second Edition . \ . San Francisco , California : Morgan Kaufmann Publishers . }- Споњашње Везе -{ 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 }- Бинарна аритметика Рачунарска аритметика Алгоритми