Butov algoritam

Butov algoritam služi za množenje dva neoznačena binarna broja zapisana u komplementu dvojke. Algoritam je izmislio Endru Donald But 1950. godine, dok je vršio istraživanje o kristalografiji (vidi još kristalografija) na Birkbek koledžu u Londonu. But je koristio kalkulatore koji su bili brži u pomeranju (Šiftovanju) cifara nego u njihovom sabiranju i iz tog razloga je osmislio algoritam koji će povećati brzinu sabiranja. Butov algoritam ima veliki doprinos arhitekturi računara.^[1]

Algoritam uredi

Butov algoritam se sastoji od množioca i množenika koji su smešteni u Q i M registre. Takođe postoji i 1-bitni registar koji je smešten logički desno od najmanje značajnog bita (Q₀) registra Q i označen je kao Q_-1; Njegovu upotrebu ćemo uskoro objasniti. Rezultati množenja će se pojaviti u registrima A i Q. A i Q_-1 se inicijalizuju na 0. Upravljačka logika skenira bitove množioca, po jedan istovremeno. Sada, kako se svaki bit ispituje, to se radi i sa bitovima na njegovoj desnoj strani. Ako su dva bita ista (1-1 ili 0-0), onda se svi bitovi registra A, Q i Q_-1 pomeraju udesno za jedan bit. Ako se dva bita razlikuju, onda se množenik dodaje registru A, ili od njega oduzima, zavisno od toga da li su dva bita 0-1 ili 1-0. Iza sabiranja ili oduzimanja, dolazi do pomeranja. U oba slučaja, pomeranje udesno je takvo da se bit u registru A krajnje levo, A_n-1, ne pomera samo u A_n-2, nego ostaje i u A_n-1. To se zahteva da bi se sačuvao predznak broja u A i Q. To je poznato kao aritmetičko pomeranje zato što zadržava bit predznaka.

Na slici 1 prikazana je sekvenca događaja u Butovom algoritmu za množenje 7 puta 3. Ista operacija je kompaktnije prikazana na slici 1.2a.

A	Q	Q_-1	M	Početne vrednosti
0000	0011	0	0111
1001	0011	0	0111	A → A-M
1100	1001	1	0111	Pomeranje - Kraj prvog ciklusa.
1110	0100	1	0111	Pomeranje - Kraj drugog ciklusa.
0101	0100	1	0111	A → A+M
0010	1010	0	0111	Pomeranje - Kraj trećeg ciklusa.
0001	0101	0	0111	Pomeranje - Kraj četvrtog ciklusa

Slika 1.

Ostatak slike 1.2 daje druge primere algoritma. Kao što se može videti, on radi u bilo kojoj kombinaciji pozitivnih i negativnih brojeva. Zapazite i efikasnost algoritma. Blokovi cifara 1 ili 0 se preskaču, sa prosečno samo jednim sabiranjem ili oduzimanjenjm po bloku.

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)

Slika 1.2

Zašto radi Butov algoritam? Najpre razmotrite slučaj pozitivnog množioca. Posebno razmotrite pozitivan množilac koj se sastoji od jednog bloka cifara 1, okruženog ciframa 0 (na primer, 00011110). Kao što name je poznato, množenje može da se postigne sabiranjem odgovarajuće pomerenih kopija množenika.

M x (00011110) = M x (2⁴+2³+2¹) = M x (16+ 8+ 4+ 2)= M x 30;

Broj takvih operacija može da se smanji na dve ako zapazimo da je:

2ⁿ+2^n-1 + . . . +2^n-k = 2ⁿ⁺¹ - 2^n-k jednačina (1.1)

Tako proizvod može da se napravi jednim sabiranjem i jednim oduzimanjem množenika. Ta šema se proširuje na bilo koji broj blokova cifara 1 u množiocu, uključujući i slučaj kada se sa jednom cifrom 1 postupa kao sa blokom.

M x (01111010) = M x (2⁶+2⁵+2⁴+2³+2¹) = M x (2⁷-2³+2²-2¹)

M x (00011110) = M x (2⁵ - 2¹) = M x (32 - 2) = M x 30

Butov algoritam se povinuje toj šemi izvođenjem operacije oduzimanja kada se naiđe na prvu cifru 1 bloka (1-0) i operaciju sabiranja kada se naiđe na kraj bloka (0-1). Da bismo pokazali da ista šema radi za negativan množilac, treba da posmatramo sledeće. Neka je H negativan broj u notaciji komplementa dvojke:

Predstavljanje = {1 x_n-2, x_n-3, … , x₁, x₀} Onda vrednost H može da se izrazi na sledeći način:

X = -2^n-1+(x_n-2 * 2^n-2 )+(x_n-3 * 2^n-3 )+⋯+(x₁* 2¹ )+(x₀* 2⁰) jednačina (1.2)

Bit krajnje levo u X je 1 zato što je X negativan. Pretpostavite da je krajnja leva cifra 0 na k-toj poziciji. Prema tome, X je u obliku Predstavljanje X = {111…10x_k-3 x_k-2… x₁ x₀} (1.3) Onda je vrednost H

X=-2^n-1+^2n-2+⋯+2^k+1+(x_k-1 X 2^k-1) )+⋯+(x₀ X 2⁰) jednačina (1.4)

Iz jednačine (1.1), možemo da kažemo da je:

2^n-2+2^n-3+ . . . +2^k+1)= 2^n-1 - 2^k+1

Preuređujući, dobijamo:

-2^n-1+2^n-2 + . . . +2^k+1 = -2^k+1 jednačina (1.5)

Smenjujučći jednačinu (1.5) u (1.4), imamo :

X = -2^k+1+(x_k-1 * 2^k-1) )+...+(x₀*2⁰) jednačina (1.6)

Najzad možemo da se vratimo Butovom algoritmu. Pamteći predstavljanje H [jednačina (1.3)], jasno je da se sa svim bitovima od x₀ do cifre 0 krajnje levo postupa ispravno zato što oni proizvode sve članove u jednačini (1.6) sem (-2^k+1) i zato su u pravilnom obliku. Kada algoritam skenira preko 0 krajnje levo i naiđe na sledeću cifru 1(2^k+1), dolazi do prelaza 1-0 i dešava se oduzimanje (-2^k+1). To je preostali član u jednačini (1.6).

Primer uredi

Kao primer uzećemo množenje nekog množenika sa brojem (-6). U predstavljanju pomoću komplementa dvojke, koristeći 8-bitnu reč, (-6) se predstavlja kao 11111010.

-6 =-2⁷+2⁶+2⁵+2⁴+2³+2¹

Ovo činilac može lako proveriti. Pa prema tome,

M x (11111010) = M x (-2⁷+2⁶+2⁵+2⁴+2³+2¹)

Kada upotrebimo jednu od jednačina dobijamo sledeće:

M x (11111010) = M x (-2³+2¹)

Činilac takođe može i ovo da proveri, i dalje je M x (-6). Najzad, sledi prethodno zaključivanje.

M x (11111010) = M x (-2³+2²-2¹).

Možemo videti da se Butov algoritam povinuje toj šemi. On izvodi oduzimanje kada se naiđe na prvu cifru 1 (10), sabiranje kada se naiđe na (01) i najzad još jednom oduzimanje kada se naiđe na prvu cifru 1 sledećeg bloka.

Prema tome, Butov algoritam izvodi manje sabiranja i oduzimanja nego neki direktiniji algoritam.

Kako algoritam radi uredi

Uzmimo da je množilac pozitivan, i da se sastoji od bloka jedinica, okruženih nulama, kao što je 00111110. Dobijamo proizvod:

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

Gde je M-množenik. Broj operacija može biti dvostruko manji ako napišemo ovako:

M\times \,^{\prime \prime }0\;1\;0\;0\;0\;0{\mbox{-1}}\;0\,^{\prime \prime }=M\times (2^{6}-2^{1})=M\times 62.

U stvari, bilo koji blok jedinica u binarnom broju možemo napisati kao razliku dva binarna broja.

(\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}.

Dakle, mi zapravo menjamo množenje nizom jedinica u originalnom broju, nekim prostijim operacijama, onda dodajemo množilac, pa pomeramo (šiftujemo) delimični proizvod koji je formiran na odgovarajućim mestima i na kraju oduzimamo množilac. Stoga mi samo pomeramo (šiftujemo) cifre u binarnom množiocu. Ova šema se može proširiti na bilo koji broj blokova jedinica u množiocu (uključujući i slučaj jedne u bloku 1). Prema tome,

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.

Butov algoritam sledi ovu šemu i tako izvršava sabiranje kada naiđe na prve dve cifre u bloku (0 1) i oduzimanje kada naiđe kraj bloka (1 0). Takođe ovo radi za negativan koeficijent. Kada su oni u množiocu grupisani u duge blokove, Butov algoritam obavlja manje sabiranja i oduzimanja od normalnog algoritma množenja.

Reference uredi

^ William Stallings Autorizovan prevod sa engleskog jezika devetog izdanja knjige "Computer Organization and Architecture Designing for Performance ninth edition".

Literatura uredi

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 Архивирано на сајту Wayback Machine (25. фебруар 2021). 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 978-1-55860-428-5. San Francisco, California: Morgan Kaufmann Publishers. 1998.

Sponjašnje Veze uredi

[1] William Stallings Autorizovan prevod sa engleskog jezika devetog izdanja knjige "Computer Organization and Architecture Designing for Performance ninth edition".

[1]