Boothův algoritmus

Boothův algoritmus je algoritmus na násobení dvou binárních čísel se znaménkem v dvojkovém doplňku.

Algoritmus

Počet bitů násobence je x, počet bitů násobitele je y.

1. Nakreslíme si tři řádky po x + y + 1 místech (bitech), označíme je A, B a C.
2. Nejvyšších (nejvíce nalevo) x bitů každého řádku se vyplní v dvojkovém doplňku takto:
   • A: násobenec
   • B: minus násobenec
   • C: nuly
3. Dalších y bitů každého řádku se vyplní takto:
   • A: nuly
   • B: nuly
   • C: násobitel
4. Do posledního bitů každého řádku se napíše nula.
5. Poté se následující kroky opakují y-krát:
   1. Pokud jsou poslední dva bity řádku C:
      • 00 nebo 11: nedělá se nic
      • 01: C = C + A. Přetečení se ignoruje.
      • 10: C = C + B. Přetečení se ignoruje.
   2. Řádek C se (aritmeticky) posune o jedno místo doprava.
6. Poslední bit součinu (řádku C) se zahodí.

Příklad

3 × -4:

• A = 0011 0000 0
• B = 1101 0000 0
• C = 0000 1100 0
• Cyklus se provede čtyřikrát:
  • C = 0000 1100 0. Poslední dva bity jsou 00.
  • C = 0000 0110 0. Posun vpravo.
  • C = 0000 0110 0. Poslední dva bity jsou 00.
  • C = 0000 0011 0. Posun vpravo.
  • C = 0000 0011 0. Poslední dva bity jsou 10.
  • C = 1101 0011 0. C = C + B.
  • C = 1110 1001 1. Posun vpravo.
  • C = 1110 1001 1. Poslední dva bity jsou 11.
  • C = 1111 0100 1. Posun vpravo.
• Výsledek je 1111 0100₂ = -12₁₀.

Proč algoritmus funguje

Uvažme kladný násobitel sestávající z posloupnosti jedniček obklopené nulami. Např. 00111110. Součin je dán:

$N\times \,^{\prime \prime }0\;0\;1\;1\;1\;1\;1\;0\,^{\prime \prime }=N\times (2^{5}+2^{4}+2^{3}+2^{2}+2^{1})=N\times 62$$N\times \,^{\prime \prime }0\;0\;1\;1\;1\;1\;1\;0\,^{\prime \prime }=N\times (2^{5}+2^{4}+2^{3}+2^{2}+2^{1})=N\times 62$,

kde N je násobenec. Počet operací se dá redukovat na dvě přepsáním téhož jako

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

Součin lze pak dostat jedním přičtením a jedním odečtením násobence. Tento postup se dá rozšířit na jakýkoliv počet posloupností jedniček v násobiteli (včetně jedné jedničky v kuse). Čili:

$N\times \,^{\prime \prime }0\;0\;1\;1\;1\;0\;1\;0\,^{\prime \prime }=N\times (2^{5}+2^{4}+2^{3}+2^{1})=N\times 58$$N\times \,^{\prime \prime }0\;0\;1\;1\;1\;0\;1\;0\,^{\prime \prime }=N\times (2^{5}+2^{4}+2^{3}+2^{1})=N\times 58$

$N\times \,^{\prime \prime }0\;1\;0\;0{\mbox{-1}}\;1{\mbox{-1}}\;0\,^{\prime \prime }=N\times (2^{6}-2^{3}+2^{2}-2^{1})=N\times 58$$N\times \,^{\prime \prime }0\;1\;0\;0{\mbox{-1}}\;1{\mbox{-1}}\;0\,^{\prime \prime }=N\times (2^{6}-2^{3}+2^{2}-2^{1})=N\times 58$

Boothův algoritmus se drží tohoto postupu přičtením, pokud narazí na první číslici z posloupnosti jedniček (0 1), a odečtením, pokud narazí na konec posloupnosti (1 0). Toto funguje také pro záporný násobitel. Jestliže se jedničky v násobiteli vyskytují v dlouhých blocích za sebou, vykoná Boothův algoritmus méně přičítání a odečítání než normální multiplikační algoritmus

Historie

Algoritmus byl vynalezen Andrewem Boothem v roce 1951 při výzkumu krystalografie na Univerzitě v Birkbecku. Booth používal kalkulátory, které měly rychlejší operaci posunu než sčítání, a vytvořil proto algoritmus, aby je urychlil.