48461 Str010 (2)

ló I. Kilka ARadnieA elfiincniarncj teorii licth

3.    Jeśli (o) oba bity są równe 0 i jest przeniesienie lub (b) jeden bit jest równy 0, drugi jest równy 1 i nic ma przeniesienia, to zapisujemy 1 i przesuwamy się do następnego miejsca.

4.    Jeśli (a) jeden bit jest równy 0. drugi bit jest równy I i jest przeniesienie lub (b) oba bity są równe 1 i nic ma przeniesienia, to zapisujemy 0, zaznaczamy przeniesienie w następnej kolumnie i przesuwamy się do następnego miejsca.

5.    Jeśli oba bity są równe 1 i jest przeniesienie, to zapisujemy 1, zaznaczamy przeniesienie w następnej kolumnie i przesuwamy się do następnego miejsca.

Wykonanie takiej operacji jeden raz nazywamy operacją na bitach. Dodanie dwóch liczb fc~bito\vych wymaga k operacji na bitach. Zobaczymy, że bardziej złożone zadania też mogą być rozłożone na pojedyncze operacje na bitach. Czas, jakiego komputer będzie potrzebował do wykonania zadania, jest w zasadzie proporcjonalny do liczby operacji na bitach. Oczywiście współczynnik proporcjonalności - liczba nanosekund na jedną operację na bitach - zależy od konkretnego systemu komputerowego. (Jest to nadmierne uproszczenie, gdyż na ten czas mogą mieć wpływ „czynniki administracyjne'*, takie jak dostęp do pamięci.) Kiedy mówimy o szacowaniu „czasu" wymaganego do wykonania jakiegoś zadania, mamy na myśli znalezienie oszacowania liczby wymaganych operacji na bitach. W tego typu oszacowaniach będziemy pomijać czas potrzebny do „księgowania" lub do wykonania operacji logicznych innych niż operacje na bilach; na ogół wykonanie operacji na bitach wymaga znacznie więcej czasu.

Następnie przeanalizujmy proces mnożenia liczb całkowitych, fc-bitowej przez /-bitową. Na przykład:

11101

1101

11101

111010

11101

101111001

Przypuśćmy, że stosujemy tę znaną wszystkim procedurę do mnożenia liczby fc-bitowej n przez liczbę /-bitową m. Otrzymamy co najwyżej / wierszy (o jeden wiersz mniej dla każdego zerowego bitu liczby m), gdzie każdy wiersz stanowi kopię liczby n przesuniętą w lewo o pewną odległość, tzn. z dopisanymi na końcu zerami. Załóżmy, że mamy V < / wierszy. Ponieważ chcemy rozłożyć całe nasze obliczenie na operacje na bitach, nie możemy dodać jednocześnie wszystkich wierszy. Musimy raczej przesuwać się w dół od drugiego wiersza do /'-tego wiersza, dodając każdy wiersz do sumy częściowej wszystkich wcześniejszych wierszy. W każdym kroku obserwujemy, o ile miejsc liczba n była przesunięta w lewo przy tworzeniu tego nowego wiersza. Przepisujemy

bity znajdujące się w sumie częściowej najbardziej na prawo, a następnie dodajemy do liczby n liczbę utworzoną z pozostałej części tumy częściowej — jak już widzieliśmy wcześniej, wymaga to fc operacji na bitach. W powyższym przykładzie, gdy mnożymy 11101 przez 1101, po dodaniu dwóch pierwszych wierszy i otrzymaniu 10010001, przepisujemy ostatnie tr/y bity 001 i resztę (tzn. 10010) dodajemy do n — 11101. Wreszcie do tej sumy 10010 -+- 11101 = 101111 dopisujemy na końcu 001, otrzymując sumę /' = 3 wierszy, równą 101111001.

Z tego opisu wynika, źe mnożenie może być rozbite na /' — 1 dodawań, wymagających po k operacji na bitach. Ponieważ /' — 1 </'</, więc daje to proste oszacowanie

Czas(mnożenie liczby fc-bitowej przez liczbę /-bitową) < fc/.

Powinniśmy poczynić kilka obserwacji dotyczących powyższego szacowania liczby operacji na bitach potrzebnych do wykonania mnożenia w systemie dwójkowym. Po pierwsze, jak już wspomnieliśmy wcześniej, zliczaliśmy tylko operacje na bitach. Nie uwzględniliśmy czasu potrzebnego do przesunięcia o kilka cyfr w lewo liczby n ani czasu potrzebnego do przepisania cyfr znajdujących się z prawego skraju sumy częściowej, odpowiadających miejscom, o które liczba n została przesunięta. W praktyce operacje przesuwania i przepisywania są znacznie szybsze od operacji na bitach, więc bezpiecznie możemy je pominąć. Inaczej mówiąc, definiujemy „oszacowanie czasu’* wykonania zadania arytmetycznego jako ograniczenie górne liczby operacji na bitach, bez uwzględnienia operacji przesuwania, zmiany zawartości rejestrów („kopiowania”), dostępu do pamięci itp. Zauważmy, że to oznacza, iż otrzymamy takie samo oszacowanie czasu, gdy będziemy mnożyć w systemie dwójkowym fc-bitowe rozwinięcie liczby wymiernej przez rozwinięcie /-bitowe; jedyną dodatkową czynnością jest ustalenie miejsca przecinka oddzielającego część całkowitą od ułamkowej i umieszczenie go we właściwym miejscu w wyniku.

Po drugie, jeśli chcemy otrzymać oszacowanie czasu w prostej i wygodnej w użyciu postaci, to powinniśmy w wielu momentach zakładać, że mamy do czynienia z „najgorszym przypadkiem”. Jeśli na przykład rozwinięcie dwójkowe liczby m ma wiele zer, to liczba /' będzie znacznie mniejsza niż /. Moglibyśmy zatem użyć oszacowania

Czas(mnożenie liczby fc-bitowej przez liczbę /-bitową) < fc • (liczba jedynek

w rozwinięciu liczby ni).

Jednakże nie warto brać pod uwagę tego ulepszenia (czyli obniżenia) szacowania czasu obliczeń, gdyż bardziej przydatne jest proste, jednolite oszacowanie, które zależy wyłącznie od wielkości liczb min, a nier ed, poszczególnych bitów, które przypadkiem mogą wystąpić w rozwinięciach tych liczb.

W szczególnym przypadku mamy

Czas(mnożenic liczby fc-bitowej przez liczbę fc-bitową) < fc².