Boothi algoritm

Boothi algoritm on märgiga binaararvude korrutamise meetod. Selle leiutas Andrew Donald Booth 1950. aastal, tehes Londonis Birkbecki kolledžis kristallograafiauuringuid.

alt=Pilt WSR160 arvutist|pisi|A. Walther WSR160 arvuti aastast 1960. Vända ühtpidi keeramisel masin liidab ning teistpidi keeramisel lahutab summale registri väärtuse.

Arvutite arengu tulemusena kasvas üha enam vajadus leida meetod, millega saaks korrutada kahte arvu, mille märk ei ole alati positiivne. Selliste arvutuste käsitsi arvutamiseks oli juba varem mitmeid viise, kuid vaid üksikud sobisid 20. sajandi keskpaiga arvutite riistvaraga kasutamiseks. 

Varasemaid märkidega binaararvude korrutamise meetodeid, mida sai selle perioodi arvutitel kasutada, oli väga keeruline rakendada ning selleks läks enamasti vaja täiendavat spetsiaalset riistvara. Otsiti uut, lihtsamat ja vähem arvutusjõudlust vajavat meetodit.

Boothi algoritm on bittide korrutamise algoritm, mis korrutab kaks märgiga binaararvu kahe täiendi meetodiga. See võimaldab mõlemal kordajal olla ükskõik kas pluss või miinus märgiga ja neid omavahel korrutada ilma eelneva teadmiseta kumma märgiga see arv päriselt on.

Boothi algoritm on kiirem kui tavaline binaararvude korrutamine, sest see töötab efektiivselt negatiivsete arvudega. See saavutatakse kuna väärtusele eelnevate bittidega (milleks on negatiivse arvu puhul ühed) ei pea arvutusi tegema.

Selle asemel, et korrutatavat binaararvu iga bitiga täielikult korrutada, kasutatakse Boothi algoritmis positsioonipõhist korrutamist, vähendades sellega arvutuste arvu ja aega.

 Boothi algoritmi tööpõhimõte

 Üks korrutistest teisendatakse, võrreldes kõrvuti olevate bitte.
 Teisenduse tulemus korrutatakse teise kordajaga.
 Peale igat tehet tehakse bitinihe paremale. 
 korrutised liidetakse

Kõik arvu kirjeldavatest bittidest vasakule poole jäävad tühjad kohad asendatakse kõige tähtsama bitiga (most significant bit). 

(kõige tähtsam bitt on kõige vasakpoolsem bitt) 

 Boothi algoritmi kasutamine 
+Kordaja teisendamise tabeli + 1iTegur                     00‎‎‎‏‏‎ ‎‏‏‎ ‎0 x M‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎‏‏‎ ‎‏‏‎ ‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎‏‏‎ ‎01 +1 x M10 ‏‏‎ ‎–1 x M11‏‏‎ ‎‏‏‎ ‎‏‏‎0 x M
Vastavalt sellele tabelile asendatakse teine tegur korrutises üleminekute lugemisega

Kui null muutub üheks, on tulemus +1

Kui üks muutub nulliks, on tulemus –1

Kui muutub samaks bitiks ehk 0 → 0 või 1 → 1 siis on tulemus 0 (see on põhiline põhjus miks seda viisi arvutamine on kiirem)

 Arvutusnäide 
Soovime korrutada arvud –11 ja +13

+13 on bittides 0 1 1 0 1

Teisendame 0 1 1 0 1 eespool toodud tabeli järgi

0 → 1 = +1

1 → 1 = 0

1 → 0 = –1

0 → 1 = +1

1 → 0 = –1 (kui bitijada saab läbi siis võetakse puuduva biti asemel on 0) 

saame +1 0 –1 1 –1

Nüüd saab korrutada teisendatud kujul arvu 13 arvuga –11

Edasi rakendatakse tavalist binaararvude korrutamist 

‏‏‎ ‎‏‏‎ ‎1  0  ‏‏‎1  ‏‏‎‎ 0  1  (–11)

+1 0 –1 +1 –1 (+13)
+TulemusTehe0 0 0 0 0 0 1 0 1 11 0 1 0 1 x (–1)1 1 1 1 1 0 1 0 11 0 1 0 1 x (+1)0 0 0 0 1 0 1 11 0 1 0 1 x (–1)0 0 0 0 0 0 0 1 0 1 0 1 x (0)1 1 0 1 0 11 0 1 0 1 x (+1)
Vasakpoolseimat bitti (most significant bit) paljundatakse.

Kui tulemused kokku liita, siis saame vastuseks:

1 1 0 1 1 1 0 0 0 1 (–143)

 Teine viis Boothi algoritmi kasutades arvutada* 
+Näites kasutatavad arvud Biti järjekorranumber43210a (korrutatav)01011b (kordaja)01110 –a (a kahe täiendi kujul)10101

Teisendame b 

Arvu b esimene, teine ja kolmas bitt on ühed ning viimane bitt on null. Saame seda esitada järgmisel kujul: 



Korrutame a ja teisendatud b

a korrutatud b esimese osaga

põhimõtteliselt kahe aste, ehk  näitab, mitu nulli lisada

a korrutatud b teise osaga

Liidame saadud korrutised kokku

Kuna –a on negatiivne, siis laiendatakse (vasakut poolt) bitiga 1 (mitte 0 nagu positiivse arvu puhul)

 = 0 1011 0000 + 1 1111 0101 = 10 1001 1010

–a puhul kasutati kahe täiendit, mille tõttu võime kõige vasakpoolsemat ühte võib ignoreerida (arv on negatiivne).

 Viited 

 Välislingid 
 Boothi algoritmi tutvustus – video Youtube'is
 Boothi algoritmi kasutusvõimalusi – video Youtube'is
 Binaararvude korrutamine – video Youtube'is

Kategooria:Matemaatika