Liczby całkowite: mnożenie
Przedmioty prowadzone w ramach Programu Rozwoju WSFiZ w Białymstoku realizowane są w ramach
Programu Operacyjnego Kapitał Ludzki, Priorytet IV Szkolnictwo wyższe i nauka, Poddziałanie 4.1.1
Wzmocnienie potencjału dydaktycznego uczelni, współfinansowanego ze środków
Europejskiego Funduszu Społecznego (POKL.04.01.01-00-030/08)
3. Liczby całkowite: mnożenie
Spis treści
3. Liczby całkowite: mnożenie ..................................................................................... 1
3.1 Mnożenie liczb całkowitych dodatnich .............................................................. 1
3.2 Mnożenie liczb całkowitych ze znakiem............................................................ 5
3.2.1 Algorytm Booth a .......................................................................................... 8
3.1 Mnożenie liczb całkowitych dodatnich
Mnożenie jest dobrym przykładem pokazującym, w jaki sposób skomplikowane pod
względem złożoności działanie jest realizowane przy pomocy prostych, dobrze
uwarunkowanych i przetestowanych kroków. Generalnie algorytmy rozwiązujące tej
klasy problemy są w systemie komputerowym realizowane na jeden z trzech sposobów:
1. hardware owo;
2. software owo;
3. mikroprogramowo.
Realizacja hardware owa polega na zaprojektowaniu układu elektronicznego, który
wykona wszystkie przewidziane przez algorytm kroki i tylko te kroki. Nie ma
możliwości wprowadzenia zmian do zrealizowanego projektu, co nie dziwi, jeżeli
uwzględnić fakt, że jego finalna realizacja może przybrać postać układu scalonego. Jest
to pewnego rodzaju wadą, ale jednocześnie stanowi o podstawowej sile takiego
rozwiązania: jest ono najszybsze z możliwych. W związku z powyższym zapewne będzie
stosowane wszędzie tam, gdzie celem głównym projektu jest duża prędkość, z jaką są
wykonywane obliczenia. Na przeciwnym biegunie znajduje się realizacja software owa.
Jest to realizacja, w której przeprowadzenie zmian jest stale możliwe: nowa wersja
programu po skompilowaniu i zlinkowaniu może być natychmiast uruchomiona.
Ponieważ jest to program (najczęściej w postaci procedury napisanej w konkretnym
języku programowania) to wykonuje się on tak jak każdy inny program napisany w tym
języku  z pewnością dużo wolniej niż jego hardware owy odpowiednik. Rozwiązanie
takie będzie stosowane w sytuacjach, w których nie szybkość, a np. niska cena jest
główną przesłanką projektową. Innym, równie dobrym powodem preferującym takie
rozwiązanie jest faza testowa projektu, w której konieczność częstych zmian wynika z
poszukiwań rozwiązań optymalnych. Rozwiązanie mikroprogramowe jest właściwie
typem rozwiązania software owego ale zrealizowanego w bardzo szczególnych
warunkach. Nie wnikając w szczegóły (tym będzie poświęcony oddzielny wykład) ze
1
Liczby całkowite: mnożenie
względu na czas wykonania lokuje się ono pomiędzy dwoma, wcześniej omówionymi
sposobami.
Zanim zaczniemy omawiać użyteczne algorytmy mnożenia binarnego zwróćmy uwagę
na kilka istotnych cech tego działania, bazując na obserwacjach poczynionych przy jego
wykonywaniu na liczbach dziesiętnych. Pierwsza jest oczywista: w wyniku mnożenia
dwóch liczb o n cyfrach może powstać liczba o 2n cyfrach (np. 3"4 = 12). Jeżeli nie
przewidzimy dostatecznie wiele miejsca na wynik to grozi nam sytuacja powstanie
nadmiaru. Sam w sobie nadmiar nie musi być groz
ny, zwłaszcza, że procesory zazwyczaj
go sygnalizują ustawiając jedynkę w specjalnym bicie kontrolnym, a wiele języków
programowania posiada mechanizmy odczytywania wartości tego bitu. Tak więc
programista zazwyczaj ma szansę odpowiednio na niego zareagować. Tym niemniej
najkorzystniejszą, z punktu widzenia użytkownika jest sytuacja, w której nadmiar nie
pojawia się.
Pozostałe własności pokażemy na przykładzie polegającym na wykonaniu mnożenia
27"23 w wersji binarnej (NKB) przy użyciu reguł analogicznych do tych, używanych w
mnożeniu dziesiętnym.
dzisiętnie binarnie (NKB)
27 �! mnożna 11011
*23 �! mnożnik *10111
81 11011
54 11011
11011
00000 kłopotliwe
11011 dodawanie
621 = 1001101101
Rysunek 3.1. Konwencjonalne mnożenie i jego binarny odpowiednik.
Z binarnej części przykładu wynika wprost, że mnożenie sprowadza się do
wielokrotnego dodawania mnożnej. Ilość operacji dodawania wynika z ilości jedynek
mnożnika. Dodawanie to może być kłopotliwe. Chodzi o sytuacje, w których przy
wykonywaniu ostatecznego sumowania liczba dodanych jedynek przekracza 3, a wtedy
przeniesienia muszą być wykonywane nie na pozycję poprzedzającą, tylko na kolejne.
Tak jest np. przy dodawaniu szóstej kolumny cyfr w omawianym przykładzie, gdzie do
trzech jedynek należy dodać jedną z poprzedniego dodawania. Cztery jedynki dają w
sumie 4 czyli 22, co oznacza, że powstałą z dodawania jedynkę należy dodać w kolumnie
odległej o 2 w lewo od bieżącej (jest to tak, jak gdyby w odpowiadającemu tej sytuacji
dodawaniu dziesiętnym dodawalibyśmy z przeniesienia 100 = 102). Tak więc istotnie
wykonywanie opisywanych dodawań jest dosyć kłopotliwe. Dużo praktyczniejsze jest
mnożenie z użyciem sum częściowych, powstałych przez każdorazowe dodawanie
pojawiającej się w kolejnych rzędach mnożnej, tak jak to zaprezentowano poniżej:
2
Liczby całkowite: mnożenie
11011 �! mnożna
*10111 �! mnożnik
11011 �! 1 * mnożna
+11011 �! 1 * mnożna
1010001 �! suma częściowa
+11101 �! 1 * mnożna
10111101 �! suma częściowa
+00000 �! 0 * mnożna
10111101 �! suma częściowa
+11011 �! 1 * mnożna
1001101101 �! wynik
Rysunek 3.2. Mnożenie binarne z wykorzystaniem sum częściowych.
Zauważmy, że efektywnie w każdym cząstkowym działaniu bierze udział jedynie n=5
bitów. Spostrzeżenie to było punktem wyjścia do skonstruowania algorytmu, w którym
mnożna, mnożnik i wynik będą przechowywane w trzech n-bitowych rejestrach, które
można zapisywać i odczytywać oraz przesuwać ich zawartość we wskazaną stronę. W
oczywisty sposób algorytm nawiązuje do rejestrów procesora, które są jednakowe co do
ilości przechowywanych w nich bitów i na których można wykonywać wszystkie
wspomniane operacje. Wprowadzimy dodatkowe oznaczenia: przez MSB oznaczać
będziemy najbardziej znaczący (pierwszy lewy) bit w liczbie. Przez LSB oznaczać
będziemy najmniej znaczący (pierwszy prawy) bit w liczbie. Skróty pochodzą od
pierwszych liter angielskich słów: odpowiednio most significant bit i least significant bit,
a ich stosowanie uzasadnia fakt, iż w języku polskim odpowiadające im określenia mają
identyczne pierwsze litery. Jest wygodnie wyobrażać sobie położenie tych rejestrów tak,
jak na rysunku poniżej:
MSB rejestru M
M
C A Q LSB rejestru Q
N-bitowe rejestry będziemy nazywać M, A, Q. Na rysunku występuje dodatkowy, 1-
bitowy rejestr (mały prostokąt obok rejestru A), który przechowa bit nadmiaru, jeżeli taki
powstanie w wyniku wykonania mnożenia. Do ciągu bitów zapisanych w sąsiednich (w
sensie zamieszczonego rysunku) rejestrach odwoływać się będziemy pisząc kolejno, bez
spacji, nazwy tych rejestrów, np. CAQ oznacza ciąg bitów zapisanych w rejestrze C,
następnie A i na końcu w Q.
Algorytm (1) składa się z dwóch kroków: inicjującego i wykonawczego
1. Inicjalizacja (1)
a) Wyzeruj A i C;
b) Załaduj mnożną do M;
c) Załaduj mnożnik do Q;
2. Powtarzaj n razy:
a) Jeżeli LSB w Q jest 1 to dodaj M do A;
b) Przesuń ciąg bitów zapisanych w CAQ o jedną pozycję w prawo,
wprowadzając do C 0.
Końcowy rezultat mnożenia znajduje się w rejestrach AQ.
3
Liczby całkowite: mnożenie
Zanim wyjaśnimy genezę kolejnych punktów algorytmu zaprezentujemy przykład
pokazujący jego działanie. Wymnóżmy 13"11 = (1101)2"(1011)2.
M
1 1 0 1
0 0 0 0 0 1 0 1 1
Nr iteracji C A Q Operacja
0 0 0 0 0 : 1 0 1 1
1 0 1 1 0 1 : 1 0 1 1 dodaj M do A
0 0 1 1 0 1:1 0 1 przesuń w prawo
2 1 0 0 1 1 1:1 0 1 dodaj M do A
0 1 0 0 1 1 1 1:0 przesuń w prawo
3 0 0 1 0 0 1 1 1:1 przesuń w prawo
4 1 0 0 0 1 1 1 1:1 dodaj M do A
0 1 0 0 0 1 1 1 1: przesuń w prawo
Wynik: 1 0 0 0 1 1 1 1 = (143)10
Zwróćmy uwagę na dwukropek, który pojawia się w zapisach kolejnych stanów
rejestrów A i Q. Został on dodany, aby pokazywać granicę pomiędzy wynikiem, a
mnożnikiem. Granica ta za każdą iteracją przesuwa się, ponieważ do wyniku dochodzi
kolejny bit, a o jeden mniej bitów zostaje do przeanalizowania w mnożniku.
Spróbujmy teraz wyjaśnić, dlaczego w poszczególne krokach algorytmu (zwłaszcza
tych wykonawczych, zapisanych w punkcie 2 - wyżej), wykonywane są takie, a nie inne
czynności.
Powtarzanie n-krotne wynika z konieczności n-krotnego analizowania wartości bitów
mnożnika (jest w Q) zaczynając od jego LSB, ponieważ wykryta tam 1 decyduje o
dodaniu mnożnej (M), bądz
 jeżeli wykryto 0  dodaniu ciągu 0 czyli braku
dodawania.
Przesuwanie bitów w rejestrach CAQ w prawo wynika z praw względności ruchu
obiektów względem innych obiektów. Przyjrzyjmy się początkowej fazie
standardowego mnożenia binarnego:
11011 �! mnożna
*10111 �! mnożnik jest to górny fragment
rysunku 3.1 (patrz wyżej)
w lewo 11011 �! 1 * mnożna
+11011 �! 1 * mnożna
W ostatnim wierszu zapisaliśmy mnożną przesuniętą o jedną pozycję w lewo. Ale równie
dobrze moglibyśmy ustabilizować położenie mnożnej i przesunąć poprzedzający wiersz
jedną pozycję w prawo. Efekt końcowy byłby taki sam:
11011 �! mnożna
*10111 �! mnożnik jest to górny fragment
w prawo rysunku 3.1 (patrz wyżej)
11011�! 1 * mnożna
+11011 �! 1 * mnożna
4
Liczby całkowite: mnożenie
W konwencjonalnym mnożeniu nieruchoma jest suma częściowa i w związku z tym
mnożna wymnożona przez kolejną jedynkę mnożnika jest wpisywana pod nią z
przesunięciem w lewo. W algorytmie  komputerowym nieruchoma jest mnożna
(właściwie miejsce do wpisywania jej bitów  rejestr M) i w związku z tym suma
częściowa znajdująca sie w rejestrach CAQ musi być przesuwana w prawo.
W opisywanym algorytmie w prawo przesuwamy nie tylko mnożną ale i znajdujący
się w sąsiednim rejestrze Q mnożnik. Efekt, jaki uzyskujemy jest wieloraki. Po
pierwsze z mnożnika za każdym przesunięciem wypada bit, które już spełnił swoją
rolę, a w jego miejsce wchodzi następny. Jest to bit, przez który w konwencjonalnym
mnożeniu będziemy za chwilę mnożyć mnożną. Jego wartość 1 oznacza (jak to już
wyjaśnialiśmy przed chwilą), że bity mnożnej pojawią się w kolejnym rzędzie i będą
dodawane do ostatnio uzyskanej sumy częściowej, albo  jeżeli jest to 0  dodawanie
powinno być zaniechane (albo mówiąc inaczej do sumy częściowej dodawane będą
zera). W wyniku przesuwania w prawo ten decyzyjny bit jest zawsze w stałym
miejscu: jest to pierwszy od prawej bit w Q, a więc jest LSB rejestru Q.
Drugim efektem każdego przesuwania w prawo jest wchodzenie na pozycję MSB w
rejestrze Q (czyli lewą skrajną) tego bitu rejestru A, który jest gotowym bitem
wyniku i nie będzie już uczestniczył w dodawaniu tworzącym kolejną sumę
częściową. Ponieważ jest bit wyniku to jego wartość musi być zapamiętana. Wpisanie
go do rejestru Q daje dokładnie taki efekt.
3.2 Mnożenie liczb całkowitych ze znakiem
Rozważania poświęcone mnożeniu liczb całkowitych ze znakiem należy zacząć od
uwagi, że można postępować podobnie, jak to sugerowane było dla odejmowania i kodu
ZM. Mówiąc konkretnie można wykonać mnożenie na modułach liczb, a w oddzielnym
postępowaniu ustalić znak wyniku i w razie, gdyby okazał się on być ujemny zamienić
liczbę będącą wynikiem na liczbę przeciwną.
Istnieje, jak się za chwilę okaże, rozwiązanie prostsze, polegające na pewnej
modyfikacji algorytmu (wyżej). Algorytm w wersji zmodyfikowanej korzysta z
nieomówionej dotychczas własności kodu U2. Własność ta wiąże się z problemem
konieczności zapisania ujemnej mnożnej lub mnożnika na określonej z góry liczbie
bitów. Jeżeli byłyby to liczby dodatnie, to poprzedzilibyśmy je odpowiednią liczbą zer.
Co jednak zrobić z ujemną liczbą w kodzie U2 rozpoczynającej się jedynką? Okazuje się,
że należy ją poprzedzić odpowiednią liczbą jedynek. O tym, że postępowanie to nie
zmieni wartości liczby przekonamy się analizując następujące przykłady: (wszystkie
liczby binarne będą w podawane w kodzie U2, chyba, że powiemy, że jest inaczej):
Dziesiętnie Binarnie (6 bitów) Binarnie (12 bitów)
25 011001 000000 011001 czy ta liczba ma taką samą
 25 100111 111111 100111 wartość jak jej wersja 6-cio bitowa?
Żeby się przekonać, jaką wartość ma wersja 12 bitowa należy wdrożyć standardową
procedurę obliczania modułu liczby w kodzie U2, tzn. zakodować ją jeszcze raz. Mamy:
5
Liczby całkowite: mnożenie
111111 100111
000000 011000
+ 1
000000 011001 = 25
Co oznacza, że dopisanie sześciu jedynek z przodu liczby nie zmieniło jej wartości.
Chociaż liczby bitów liczby (tj. 6 i 12) zostały dobrane przypadkowo, to łatwo sprawdzić,
że dopisanie dowolnej liczby jedynek daje dokładnie ten sam efekt: wartość liczby
pozostaje stała. O liczbie, w której powielono bit znaku (bo do tego sprowadza się ta
własność mówimy, że została znakowo rozszerzona  ang. signed extended). Korzystając
z tej własności wykonajmy działanie ( 25) " 23:
( 25)10 = 100111 = 111111 100111
* (23)10 = 010111 = 010111
 75 111111 100111
 50 111111 00111
111110 0111
000000 000
111001 11
000000 0
( 575)10 = = 110111 000001
Zanim sprawdzimy wynik przyjrzyjmy się obliczeniom i zauważmy, że przed
rozpoczęciem działania 6-cio bitowa mnożna została znakowo rozszerzona do 12 bitów.
Zrobiono tak dlatego, że przy mnożeniu liczba bitów wyniku może ulec podwojeniu w
stosunku do ilości bitów mnożnej i mnożnika. Ponieważ ostateczny rezultat obliczany
jest przez dodawanie, to 12-bitowy wynik zapewniono rozszerzając znakowo ujemny
składnik (rozszerzenie drugiego, dodatniego jest błędem). Podobnie do 12 bitów powinno
sie rozszerzyć wszystkie składniki finalnej sumy. Tu należy jednak uwzględnić regułę
dotycząca działań na liczbach w kodzie U2, zgodnie z którą, wszelkie przeniesienia
ponad z góry znaną liczbę bitów wyniku powinny zostać pominięte. Stąd zapisywany w
kolejnym wierszu wynik mnożenia odpowiedniego bitu mnożnika przez mnożną jest o1
bit krótsze do poprzedniego wyniku tak, aby sumowanych było dokładnie 12 bitów.
Pomijane są pierwsze bity, bo to one mogłyby spowodować zwiększenie ilości bitów
ostatecznego wyniku ponad przyjęty limit.
Sprawdz
my wartość wyniku (czyli zakodujmy go raz jeszcze do U2):
110111 000001
001000 111110
+ 1
001000 111111 = 29 + 26  1 = 575
Przy obliczaniu wartości dziesiętnej skorzystaliśmy z tożsamości dla zapisów w NKB:
(11...1)2 = (100 ... 0)2  1, czyli 2k  1 = 20+21+ ...+2k-1
Własność ta oznacza, że liczba złożona z k jedynek jest równa k tej potędze liczby 2
pomniejszonej o 1 (uwaga: własność dotyczy zapisów w NKB).
6
Liczby całkowite: mnożenie
Zauważmy, że całość dotychczasowych rozważań dotyczących mnożenia liczb
ujemnych sprowadza się do przypadku, że liczbą ujemną może być mnożna. Zauważmy,
że gdyby ujemny był mnożnik, a mnożna dodatnia, to przez wstępne przemnożenie przez
 1 obu liczb łatwo można doprowadzić do sytuacji pożądanej. Podobnie jak mnożenie
dwóch liczb ujemnych przez taką samą operację można sprowadzić do mnożenia liczb
dodatnich. Tak więc nie jest to założenie ograniczające i można je zaakceptować jako
założenie uściślające wartości czynników (tak nazywamy łącznie mnożną i mnożnik).
Zajmijmy się teraz rozszerzeniem algorytmu 1 (patrz wyżej) o możliwość mnożenia
pary liczb o różnych znakach. Tak jak uprzednio bazować będziemy na 4 rejestrach, przy
czym teraz rejestr przeniesienia będzie musiał być zastąpiony również 1-no bitowym
rejestrem znaku nazywanym S. Jest jasne, że będzie on przechowywał znak mnożnej,
który to znak po każdym przesunięciu zawartości rejestrów w prawo będzie na nowo
ładowany wartością wynikającą z tego znaku, aby realizować rozszerzenie znakowe
mnożnej.
1. Inicjalizacja (2)
a) Wyzeruj A i S;
b) Załaduj mnożną do M;
c) Załaduj mnożnik do Q;
d) Jeżeli Q < 0, zastąp M i Q przez ich negacje
2. Powtarzaj n razy:
a) Jeżeli LSB w Q jest 1 to dodaj M do A i ustaw S zgodnie ze znakiem M;
b) Przesuń ciąg bitów zapisanych w SAQ o jedną pozycję w prawo, nie
zmieniając zawartości S.
Końcowy rezultat mnożenia znajduje się w rejestrach AQ.
Jako przykład wymnożymy (-13) i 11 zapisane na 5 ciu bitach. Zwróć uwagę, że
zawartość S zmienia się tylko jeden raz, gdy po raz pierwszy ujemna mnożna zapisywana
jest do rejestru A.
M
1 0 0 1 1
0 0 0 0 0 0 0 1 0 1 1
Nr iteracji S A Q Operacja
0 0 0 0 0 0 : 0 1 0 1 1
1 1 1 0 0 1 1 : 0 1 0 1 1 dodaj M do A
1 1 1 0 0 1 1: 0 1 0 1 przesuń w prawo
2 1 0 1 1 0 0 1:0 1 0 1 dodaj M do A
1 1 0 1 1 0 0 1:0 1 0 przesuń w prawo
3 1 1 1 0 1 1 0 0 1:0 1 przesuń w prawo
4 1 0 1 1 1 0 0 0 1:0 1 dodaj M do A
1 1 0 1 1 1 0 0 0 1:0 przesuń w prawo
5 1 1 1 0 1 1 1 0 0 0 1 przesuń w prawo
Wynik: 1 1 0 1 1 1 0 0 0 1 =  143
7
Liczby całkowite: mnożenie
Jak widać algorytm (wyżej) działa dobrze. Pomimo to poszukiwano rozwiązań, które
pozwalałaby uzyskiwać wynik w mniejszej liczbie kroków, a więc działać szybciej. W
literaturze przedmiotu wymienia się algorytm Booth a (patrz niżej) jako jeden z tych,
które spełniają te oczekiwania.
3.2.1 Algorytm Booth a
Podstawą działania algorytmu Booth a są następujące spostrzeżenia:
1. Liczba dodawań mnożnej zależy wprost od liczby jedynek w mnożniku;
2. Gdyby udało się przekształcić mnożnik w taki sposób aby liczba jedynek w jego
zapisie była mniejsza od tej w zapisie oryginalnym, a koszty tego przekształcenia
były małe, to można by istotnie przyśpieszyć obliczenia.
Posłużmy się przykładem. Załóżmy, że chcemy mnożyć 11" 15 = 001011" 001111.
Użycie algorytmu (wyżej) spowodowałoby konieczność czterokrotnego dodawania
mnożnej, po jednym dodawaniu na każdą jedynkę mnożnika. Gdyby jednak zapisać
mnożnik w taki sposób: 15 = 16  1, to otrzymalibyśmy co następuje:
001011 " 001111 = 001011 " (010000  000001) =
= 001011 " 010000  001011 " 000001 =
= 000010 110000  000000 001011
Jak wynika z przedstawionych przekształceń wynik mnożenia można otrzymać już po
jednym odejmowaniu (popatrz na drugi wiersz przekształceń: są tam dwa mnożenia, w
których mnożne mają po jednej jedynce, co oznacza, że do końcowej różnicy przechodzi
mnożna  001011  przesunięta o odpowiednią liczbę pozycji, co z kolei widać w
ostatnim wierszu).
Podobne przekształcenia mogą dawać wyniki również w dużo bardziej ogólnych
przypadkach. Np. wez
my następujący mnożnik: (2031)10 = 0111 1110 1111. Można go
przed wykonaniem mnożenia przekształcić następująco:
0111 1110 1111 = 10000 0000 0000  10 0000 + 1 0000  1
Można sprawdzić, że prawa strona nadal równa 2031. Z przekształcenia wynika, że
zamiast 10 dodawań (tyle jedynek ma pierwotna postać mnożnika) do przeprowadzenia
mnożenia wystarczą dwa odejmowania i jedno dodawanie.
To, czego potrzebujemy to uogólnienie powyższych spostrzeżeń, tak aby można było
rozkładać na jedno-jedynkowe składniki dowolny mnożnik. Otóż istnieje taki algorytm.
Polega on na przypisaniu parom kolejnych bitów mnożnika jednej z trzech wartości:  1,
0 lub +1. Którą konkretnie  to zależy od tego, jakie bity występują w rozważanej parze,
zgodnie z następującą tabelą:
Bity mnożnika Wartość przypisana
bit i bit i-1 bit i
0 0 0
0 1 +1
1 0  1
1 1 0
8
Liczby całkowite: mnożenie
W tabeli w lewej kolumnie występują wszystkie możliwe kombinacje sąsiednich bitów
mnożnika. Są one (bity w parze) indeksowane przez i oraz i-1. W prawej kolumnie
występują przypisywane każdej parze kodowe wartości. Nazwane są one trochę na
wyrost też bitami (prawdziwe bity mogą mieć wartość tylko 0 albo 1) ponieważ ich ciąg
obliczony dla wszystkich kolejnych par tworzy słowo kodowe o długości równej ilości
bitów mnożnika. Ponieważ bity mnożnika numerowane są od 0 to dla bitu zerowego
potrzebujemy pary o indeksie  1. Utwórzmy sztuczny ekstra bit o wartości 0 i załóżmy,
że on jest tym brakującym bitem.
Wykorzystując podane reguły utwórzmy słowo kodowe dla mnożnika, który był już
obiektem eksperymentów, tj. (2031)10 = 0111 1110 1111. Zaczynamy od pary bitów
mnożnika o indeksach -1 i 0:
Mnożnik: 0 1 1 1 1 1 1 0 1 1 1 1 0 �! dodatkowy bit b 1
Słowo kodowe: +1 0 0 0 0 0 1+1 0 0 0 1
Wartości  bitów słowa kodowego i miejsce bitów w słowie pozwala natychmiast
napisać:
0111 1110 1111 = 1000 0000 0000  10 0000 + 1 0000  1
Dla tych co nie do końca są przekonani do ostatniego przejścia możemy zaproponować
przeliczenie ilości bitów w każdym ze składników prawej strony powyższej tożsamości i
porównanie jej z indeksem odpowiedniej jedynki w słowie kodowym. Podobnie proszę
porównać znak stojący przed każdym ze składników z wartością odpowiedniego bitu
słowa kodowego.
Zanim zaprezentujemy przykład przywołajmy jeszcze raz konsekwencje faktu
wystąpienia na i tym bicie słowa kodowego +1 i  1. Otóż w obu przypadkach mnożna
powinna zostać przesunięta w taki sposób, że jej LSB będzie na pozycji i-tej wyniku, z
tym że tam, gdzie występuje +1 mnożna występuje w postaci oryginalnej, a brakujące
bity na najbardziej znaczących pozycjach powinny być wypełnione zerami. Natomiast
tam gdzie występuje -1 mnożna występuje w postaci swego kodu U2, a brakujące bity na
najbardziej znaczących pozycjach powinny być wypełnione jedynkami (rozszerzenie
znakowe) .
Po tych wyjaśnieniach spróbujmy wykonać mnożenie 100 " ( 31). Potrzebujemy wersji
binarnej mnożnej (100) oraz jej kodu U2 (użyjemy go, gdy będzie odejmowana).
Obliczmy też słowo kodowe mnożnika ( 31). Obliczenia wykonamy na 8 bitach.
(100)10 = 0110 0100 (31)10 = 0 0 0 1 1 1 1 1
( 100)10 = 1001 1100 ( 31)10 = 1 1 1 0 0 0 0 1 0 �! b 1
Słowo kodowe: 0 0 1 0 0 0+1 1
W prezentowanych dotychczas przykładach układ czynników był taki, że pod mnożną
pisaliśmy bity mnożnika i rozpoczynaliśmy mnożenie. Teraz w miejsce mnożnika
wpiszemy słowo kodowe, bo to jego  bity mówią nam, czy mnożna w kolejnym kroku
ma być dodana czy odjęta (tj. dodany kod U2). Tekst przykładu pokazany jest poniżej.
Żeby nie zaciemniać obrazu na rysunku pominięto ciągi zer, poprzestając na jednym,
występującym na pozycji LSB. Kolorowe strzałki pokazują te bity słowa kodowego, na
9
Liczby całkowite: mnożenie
podstawie których odejmowano lub dodawano zapisaną na odpowiedniej liczbie bitów
mnożną (tj. 100).
mnożna (100) 0 1 1 0 0 1 0 0
słowo kodowe 0 0 1 0 0 0+1 1
- mnożna 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0
+mnożna 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0
0
0
0
- mnożna 1 1 1 1 0 0 1 1 1 0 0
0
0
1 1 1 1 0 0 1 1 1 1 1 0 0 1 0 0 = (-3100)10
Podsumujmy zyski. Przy zwykłym mnożeniu potrzebnych jest 5 dodawań, bo tyle
jedynek ma mnożnik. W zaprezentowanej wersji (wersji Booth a) tych dodawań jest 3, co
oznacza 40% zysk.
Formalna,  komputerowa wersja algorytmu Booth a różni się kilkoma szczegółami.
Po pierwsze słowo kodowe nie jest liczone w całości, tylko bit po bicie, w tempie
pojawiających się potrzeb, czyli po jednym bicie na każdą iterację. Na jego
przechowywanie przeznaczono specjalny 1 bitowy rejestr nazwany B. Sumaryczna
liczba rejestrów zaangażowanych w mnożenie nie ulegnie zmianie, bo rejestr B zastąpi
rejestr S, który przy tej metodzie mnożenia nie jest potrzebny. Na rysunku poniżej
pokazano rejestry użyte do mnożenia metodą Booth a:
M LSB rejestru Q
�!
A Q B
Warto zwrócić uwagę, że umiejscowienie rejestru B z prawej strony rejestru Q (do
którego ładuje się mnożnik) i jego inicjalne zerowanie powoduje, że para bitów: LSB
rejestru Q i bit rejestru B znajdują się obok siebie, co ułatwia obliczenie inicjalnego, a
potem następnych  bitów słowa kodowego.
A oto algorytm Booth a:
1. Inicjalizacja (3)
a) Wyzeruj A i B;
b) Załaduj mnożną do M;
c) Załaduj mnożnik do Q;
2. Powtarzaj n razy:
a) Jeżeli LSB w Q jest 1 i B = 0 to odejmij M od A albo
Jeżeli LSB w Q jest 0 i B = 1 to dodaj M do A;
10
Liczby całkowite: mnożenie
b) Przesuń ciąg bitów zapisanych w AQB o jedną pozycję w prawo, stosując
do MSB w A zasadę znakowego rozszerzenia.
Końcowy rezultat mnożenia znajduje się w rejestrach AQ.
Przykład (13"11): M
0 1 1 0 1
0 0 0 0 0 0 1 0 1 1 0
Nr iteracji A Q B Operacja
0 0 0 0 0 : 0 1 0 1 1 0
1 1 0 0 1 1 : 0 1 0 1 1 0 odejmij M od A
1 1 0 0 1 1:0 1 0 1 1 przesuń w prawo
2 1 1 1 0 0 1 1:0 1 0 1 przesuń w prawo
3 0 1 0 0 1 1 1:0 1 0 1 dodaj M od A
0 0 1 0 0 1 1 1:0 1 0 przesuń w prawo
4 1 0 1 1 1 1 1 1:0 1 0 odejmij M do A
1 1 0 1 1 1 1 1 1:0 1 przesuń w prawo
5 0 1 0 0 0 1 1 1 1:0 1 dodaj M od A
0 0 1 0 0 0 1 1 1 1: 0 przesuń w prawo
Wynik: 0 0 1 0 0 0 1 1 1 1 = (143)10
Zanim wyjaśnimy istotne punkty algorytmu przeanalizujmy przykład pokazujący jego
działanie. Mnożymy w nim 13"11 = (1101)2"(1011)2. Potrzebne nam  13 = (10011)U2.
Tak jak w poprzednich przykładach dwukropek oddziela sumy częściowe od bitów
mnożnika. Strzałki pokazują LSB rejestru Q i bit B. Są to bity na podstawie których
zapada decyzja o odejmowaniu, dodawaniu czy wyłącznie przesuwaniu. Uważny
czytelnik rozpozna w nich bity, na podstawie których wyznaczaliśmy kolejne  bity
słowa kodowego. Tak, jak to było powiedziane wcześniej algorytm działa w ten sposób,
że zamiast wyznaczyć słowo kodowe w całości, wyznacza kolejne jego bity tak, aby ich
wartość była znana w momencie podejmowania decyzji o tym czy należy dodawać M do
A, odejmować M od A, czy tylko przesuwać zawartość rejestrów A i Q o jeden bit w
prawo. Przesuwanie w prawo powoduje wypychanie nieprzydatnych bitów, a na ich
miejsce wprowadza te, na podstawie których zapadają kolejne decyzje. Przy
dodawaniach i odejmowaniach bity przeniesienia, o ile powstają, są zgodnie z zasadą
działania na kodach U2 ignorowane. Należy zwrócić uwagę na punkt 2b (patrz wyżej)
algorytmu, który mówi, że przy wprowadzaniu nowych bitów w trakcie przesuwania w
prawo należy stosować zasadę znakowego rozszerzenia. Oznacza to, że przesuwając
liczbę ujemną (MSB = 1) w zwolnione miejsce wprowadzamy 1, natomiast kiedy robimy
to z liczbą dodatnią (MSB = 0) to wprowadzamy zero. Postępowanie takie wynika
właśnie z zasady konstruowania znakowego rozszerzenia: liczba ujemna nie zmienia
wartości, jeżeli dopisujemy do niej z lewej strony jedynki, a liczba dodatnia  jeżeli
dopisujemy zera. To, że musimy dopisywać cyfry wynika z wymogu prowadzenia
działań na takiej liczbie cyfr, jaką ma wynik  w naszym przypadku 10. Ciekawą i
pozytywną cechą algorytmu Booth a jest brak jakichkolwiek wymagań na znaki mnożnej
11
Liczby całkowite: mnożenie
i mnożnika, jak to było w algorytmie (2) zwykłego mnożenia liczb ze znakiem (patrz
wyżej).
Przykład został tak dobrany, żeby pokazać również wady tego algorytmu. Jeżeli
cofniemy się do przykładu ilustrującego pierwszą, najwcześniejszą wersję algorytmu
mnożenia (algorytm wyżej) to spostrzeżemy, że ilość operacji w wersji Booth a wcale nie
zmalała, a o 1 wzrosła. Wynika to z faktu, że ilość składników po rozłożenie mnożnika
może być większa niż liczba jedynek w jego pierwotnej postaci. W literaturze można
znalez
ć algorytmy mnożenia, które poprawiają algorytm Booth a bądz
proponują inne
sposoby, które nie posiadają wspomnianej wady.
12