Buta algoritms

Vikipēdijas lapa
Pārlēkt uz: navigācija, meklēt

Buta algoritmu 1951. gadā izgudroja Endrū Donalds Buts.

Buta reizināšanas algoritms ir reizināšanas algoritms, kas sareizina divus zīmes (+/-) binārus skaitļus, izmantojot binārā skaitļa papildkodu.

Procedūra[labot šo sadaļu | labot pirmkodu]

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[labot šo sadaļu | labot pirmkodu]

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[labot šo sadaļu | labot pirmkodu]