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 üht pidi keeramisel masin liidab ning teistpidi keeramisel lahutab summale registri väärtuse.

Miks see leiutati

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 varasemalt 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.

Algoritmist lähemalt

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.

Kuidas Boothi algoritm töötab?

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)

Näide arvutusest kasutades Boothi algoritmi

Soovime korrutada arvud -11 ja +13

+13 on bittides 0 1 1 0 1

Teiendame 0 1 1 0 1 ülal 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 biti (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ärgneval 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).

Lisamaterjale paremaks ülevaateks

Mis on Boothi Algoritm https://www.youtube.com/watch?v=meSn0UXmgac

Boothi Algoritmi kasutusi https://www.youtube.com/watch?v=tnLKU07b-HA

Binaararvude korrutamine https://www.youtube.com/watch?v=PjmWG_8b3os