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.

1. 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).
   1. A: Nozīmīgākos bitus (pa labi) aizpilda ar m vērtību, atlikušos bitus (y + 1) ar nullēm.
   2. S: Nozīmīgākos bitus (pa labi) aizpilda ar (-m) papildkodu, atlikušos bitus (y + 1) ar nullēm.
   3. 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.
2. Nosaka P pēdējos divus nozīmīgākos (pa labi) bitus.
   1. Ja tie ir 01, tad P + A. Pārpilde tiek ignorēta.
   2. Ja tie ir 10, tad P + S. Pārpilde tiek ignorēta.
   3. Ja tie ir 00, neko nedara. Pāriet pie nākamā soļa.
   4. Ja tie ir 11, neko nedara. Pāriet pie nākamā soļa.
3. P skaitļa aritmētiskā nobīde pa labi par vienu bitu. P satur jauno vērtību.
4. 2. un 3. punktu atkārto līdz izpildīti y reizes.
5. 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:
  1. P = 0000 1100 0. Pēdējie divi biti 00.
     • P = 0000 0110 0. Aritmētiskā nobīde pa labi.
  2. P = 0000 0110 0. Pēdējie divi biti 00.
     • P = 0000 0011 0. Aritmētiskā nobīde pa labi.
  3. 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.
  4. 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