Algorytm budkowy to algorytm mnożenia, który pozwala nam pomnożyć dwie liczby całkowite binarne ze znakiem w uzupełnieniu do 2. Służy także do przyspieszenia wykonania procesu mnożenia. Jest również bardzo wydajny. Działa na bitach ciągu zerowych w mnożniku, który nie wymaga dodatkowego bitu, jedynie przesuwa najbardziej na prawo bity ciągu i ciąg jedynek w bitach mnożnika o wadze 2^kdo wagi 2^Mktóre można uznać za 2^{k+ 1}- 2^M .

Poniżej znajduje się obrazowe przedstawienie algorytmu Bootha:

Na powyższym schemacie początkowo AC I Q_{n + 1} bity są ustawione na 0, a SC jest licznikiem sekwencji reprezentującym całkowity zestaw bitów N, która jest równa liczbie bitów w mnożniku. Tam są BR które reprezentują mnożniki bitów, i QR oznacza bity mnożnika . Następnie napotkaliśmy dwa bity mnożnika jako Q_Ni Q_{n + 1}, gdzie Qn reprezentuje ostatni bit QR, a Q_{n + 1}reprezentuje bit Qn zwiększony o 1. Załóżmy, że dwa bity mnożnika są równe 10; oznacza to, że musimy odjąć mnożnik od iloczynu częściowego w akumulatorze AC, a następnie wykonać operację przesunięcia arytmetycznego (ashr). Jeśli oba mnożniki są równe 01, oznacza to, że musimy dodać mnożną do iloczynu częściowego w akumulatorze AC, a następnie wykonać operację przesunięcia arytmetycznego ( Aszr ), w tym Q_{n + 1} . Operacja przesunięcia arytmetycznego jest używana w algorytmie Bootha do przesuwania bitów AC i QR w prawo o jeden, pozostawiając bit znaku w AC niezmieniony. Licznik sekwencji jest stale zmniejszany, aż do powtórzenia pętli obliczeniowej równej liczbie bitów (n).

Praca nad algorytmem Booth

1. Ustaw bity binarne mnożnika i mnożnika odpowiednio na M i Q.
2. Początkowo ustawiamy AC i Q_{n + 1}rejestruje wartość 0.
3. SC reprezentuje liczbę bitów mnożnika (Q) i jest licznikiem sekwencji, który jest stale zmniejszany, aż będzie równy liczbie bitów (n) lub osiągnięty do 0.
4. Qn reprezentuje ostatni bit Q, a Q_n+1pokazuje bit Qn zwiększony o 1.
5. W każdym cyklu algorytmu budkowego Q_Ni Q_{n + 1}bity zostaną sprawdzone dla następujących parametrów w następujący sposób:
   1. Kiedy dwa bity Q_Ni Q_{n + 1}mają wartość 00 lub 11, po prostu wykonujemy arytmetyczną operację przesunięcia w prawo (ashr) do iloczynu częściowego AC. Oraz bity Qn i Q_{n + 1}zwiększa się o 1 bit.
   2. Jeśli bity Q_Ni Q_{n + 1}jest pokazany na 01, bity mnożne (M) zostaną dodane do AC (rejestru akumulatora). Następnie wykonujemy operację przesunięcia w prawo bitów AC i QR o 1.
   3. Jeśli bity Q_Ni Q_{n + 1}wynosi 10, bity mnożnika (M) zostaną odjęte od AC (rejestru akumulatora). Następnie wykonujemy operację przesunięcia w prawo bitów AC i QR o 1.
6. Operacja działa w sposób ciągły, aż do osiągnięcia n - 1 bitu w algorytmie kabiny.
7. Wyniki mnożenia bitów binarnych będą przechowywane w rejestrach AC i QR.

W algorytmie Bootha stosowane są dwie metody:

Linux edytuj plik

1. RSC (kołowy z prawym przesunięciem)

Przesuwa najbardziej na prawo bit liczby binarnej, a następnie jest dodawany na początku bitów binarnych.

2. RSA (arytmetyka z przesunięciem w prawo)

Dodaje dwa bity binarne, a następnie przesuwa wynik w prawo o 1-bitową pozycję.

ciąg porównaj Java

Przykład : 0100 + 0110 => 1010, po dodaniu liczby binarnej przesuwamy każdy bit o 1 w prawo i umieszczamy pierwszy bit wynikowej na początku nowego bitu.

Przykład: Pomnóż dwie liczby 7 i 3, korzystając z algorytmu mnożenia Bootha.

Lata . Mamy tutaj dwie liczby, 7 i 3. Przede wszystkim musimy przekonwertować 7 i 3 na liczby binarne, takie jak 7 = (0111) i 3 = (0011). Teraz ustaw 7 (w formacie binarnym 0111) jako mnożnik (M) i 3 (w formacie binarnym 0011) jako mnożnik (Q). SC (liczba sekwencji) reprezentuje liczbę bitów, a tutaj mamy 4 bity, więc ustaw SC = 4. Pokazuje także liczbę cykli iteracji algorytmów kabiny, a następnie cykle są uruchamiane SC = SC - 1 raz.

Liczbowy przykład algorytmu mnożenia Bootha to 7 x 3 = 21, a binarna reprezentacja liczby 21 to 10101. Tutaj otrzymujemy wynik w postaci binarnej 00010101. Teraz konwertujemy go na dziesiętny, jako (000010101)₁₀= 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.

węzeł listy

Przykład: Pomnóż dwie liczby 23 i -9, korzystając z algorytmu mnożenia Bootha.

Tutaj M = 23 = (010111) i Q = -9 = (110111)

Q_{n + 1} = 1, oznacza to, że wynik jest ujemny.

Zatem 23 * -9 = uzupełnienie 2 liczby 111100110001 => (00001100111)