Liczby całkowite: mnożenie

1

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 M

noż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

Liczby całkowite: mnożenie

2

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ć groź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 2

2

, 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 = 10

2

). 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:

Liczby całkowite: mnożenie

3

11011 ← mnożna

*10111 ← mnożnik

11011 ← 1 * mnożna

+11011 ← 1 * mnożna

1010001 ← suma częściowa

+11011

← 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.

Liczby całkowite: mnożenie

4

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ądź – 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

Liczby całkowite: mnożenie

5

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 M

noż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:

Liczby całkowite: mnożenie

6

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.

Sprawdźmy wartość wyniku (czyli zakodujmy go raz jeszcze do U2):

110111 000001

001000 111110

+

1

001000 111111 = 2

9

+ 2

6

– 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 2

k

– 1 = 2

0

+2

1

+ ...+2

k-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).

Liczby całkowite: mnożenie

7

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

Liczby całkowite: mnożenie

8

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. weź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

Liczby całkowite: mnożenie

9

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

Liczby całkowite: mnożenie

10

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;

Liczby całkowite: mnożenie

11

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

Liczby całkowite: mnożenie

12

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
znaleźć algorytmy mnożenia, które poprawiają algorytm Booth’a bądź proponują inne
sposoby, które nie posiadają wspomnianej wady.