Boothi algoritm

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

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

1. Üks korrutistest teisendatakse, võrreldes kõrvuti olevate bitte.
2. Teisenduse tulemus korrutatakse teise kordajaga.
3. Peale igat tehet tehakse bitinihe paremale.
4. 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 tabel

i + 1	i	Tegur
0	0	‎‎‎‏‏‎ ‎‏‏‎ ‎0 x M‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎‏‏‎ ‎‏‏‎ ‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎‏‏‎ ‎
0	1	+1 x M
1	0	‏‏‎ ‎–1 x M
1	1	‏‏‎ ‎‏‏‎ ‎‏‏‎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)

Tulemus	Tehe
0 0 0 0 0 0 1 0 1 1	1 0 1 0 1 x (–1)
1 1 1 1 1 0 1 0 1	1 0 1 0 1 x (+1)
0 0 0 0 1 0 1 1	1 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 1	1 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ärjekorranumber	4	3	2	1	0
a (korrutatav)	0	1	0	1	1
b (kordaja)	0	1	1	1	0
–a (a kahe täiendi kujul)	1	0	1	0	1

Teisendame b

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

$b=2^{(3+1)}-2^{(1)}$

Korrutame a ja teisendatud b

$a*b=a*(2^{4}-2^{1})=a*2^{4}-a*2^{1}$

a korrutatud b esimese osaga

$a*2^{4}=01011*2^{4}=010110000$

põhimõtteliselt kahe aste, ehk $2^{(4)}$näitab, mitu nulli lisada

a korrutatud b teise osaga

$(-a)*2^{1}=10101*2^{1}=101010$

Liidame saadud korrutised kokku

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

$a*b$ = 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).

Välislingid

• Boothi algoritmi tutvustus – video Youtube'is
• Boothi algoritmi kasutusvõimalusi – video Youtube'is
• Binaararvude korrutamine – video Youtube'is