Buta algoritms

Buta algoritms ir reizināšanas algoritms, kas sareizina divus zīmes (+/-) binārus skaitļus, izmantojot binārā skaitļa papildkodu. To 1951. gadā izgudroja Endrū Donalds Buts.

 Procedūra 

Buta algoritms paredz atkārtoti pieskaitīt vienu no sākotnējām vērtībām (A un S) rezultātam P un tad izpildīt aritmētisko nobīdi pa labi skaitlim P. 
m - reizināmais, r — reizinātājs.
x un y norāda bitu skaitu m un r.
 Nosaka A un S vērtības un P sākuma vērtību. A, S, P skaitļu garumiem jābūt vienādiem ar (x + y + 1).
 A: Nozīmīgākos bitus (pa labi) aizpilda ar m vērtību, atlikušos bitus (y + 1) ar nullēm.
 S: Nozīmīgākos bitus (pa labi) aizpilda ar (-m) papildkodu, atlikušos bitus (y + 1) ar nullēm.
 P: Nozīmīgākos x bitus aizpilda ar nullēm, pa labi pievieno r vērtību, pēdējam bitam (pa labi) pieškir vērtību 0.
 Nosaka P pēdējos divus nozīmīgākos (pa labi) bitus.
 Ja tie ir 01, tad P + A. Pārpilde tiek ignorēta.
 Ja tie ir 10, tad P + S. Pārpilde tiek ignorēta.
 Ja tie ir 00, neko nedara. Pāriet pie nākamā soļa.
 Ja tie ir 11, neko nedara. Pāriet pie nākamā soļa.
 P skaitļa aritmētiskā nobīde pa labi par vienu bitu. P satur jauno vērtību.
 2. un 3. punktu atkārto līdz izpildīti y reizes.
 Atmet P pēdējo nozīmīgo bitu (pa labi), P satur m un r reizinājuma vērtību.

 Piemērs 

3 x (-4), kur m = 3, r = -4, x = 4 un y = 4:
 A = 0011 0000 0
 B = 1101 0000 0
 P = 0000 1100 0
 Izpilda ciklu 4 reizes:
 P = 0000 1100 0. Pēdējie divi biti 00.
 P = 0000 0110 0. Aritmētiskā nobīde pa labi.
 P = 0000 0110 0. Pēdējie divi biti 00.
 P = 0000 0011 0. Aritmētiskā nobīde pa labi.
 P = 0000 0011 0. Pēdējie divi biti 10.
 P = 1101 0011 0. P = P + S
 P = 1110 1001 1. Aritmētiskā nobīde pa labi.
 P = 1110 1001 1. Pēdējie divi biti 11.
 P = 1111 0100 1. Aritmētiskā nobīde pa labi.
 P = 1111 0100, decimālā sistēmā -12

 Ārējās saites 

 Buta algoritma simulācija

Kategorija:Algoritmi
Kategorija:Datorzinātne