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. # Nakreslíme si tři řádky po x + y + 1 místech (bitech), označíme je A, B a C. +more # 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 # Dalších y bitů každého řádku se vyplní takto: #* A: nuly #* B: nuly #* C: násobitel # Do posledního bitů každého řádku se napíše nula. # Poté se následující kroky opakují y-krát: ## 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. ## Řádek C se (aritmeticky) posune o jedno místo doprava. # Poslední bit součinu (řádku C) se zahodí.

Příklad

310 × -410: 00112 × -(01002) => 00112 × 11002: * 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. +more ** 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 01002 = -1210.

Proč algoritmus funguje

Uvažme kladný násobitel sestávající z posloupnosti jedniček obklopené nulami. Např. +more 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 , 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 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 \; 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. +more 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. +more Booth používal kalkulátory, které měly rychlejší operaci posunu než sčítání, a vytvořil proto algoritmus, aby je urychlil.

Kategorie:Algoritmy