70331 Str011 (2)

18    1. KiUta rsgidnieri elementarnej teorii lierb

Wreszcie misze oszacowanie może być zapisane za pomocą n i m, jeśli pamiętamy wzór na liczbę cyfr, z którego wynika, że k « [log₂w] *f I ^

log// log 2

logm log 2

+ 1 i / aa [log₂ m] + 1

Przykład 6, Znajdźmy ograniczenie górne liczby operacji na bitach potrzebnych do obliczenia «!.

Rozwiązanie. Użyjemy następującego algorytmu. Najpierw pomnożymy 2 przez 3, potem wynik przez 4, następny wynik przez 5 itd., aż wreszcie dojdziemy do n. W (J — l)-ym kroku (J = 2, 3, ..., n — 1) mnożymy j\ przez j + 1. Mamy więc n — 2 kroków; w każdym kroku mnożymy częściowy iloczyn (tzn. /!) przez następną liczbę. Częściowe iloczyny robią się coraz większe. W najgorszym przypadku możemy przyjąć, że liczba bitów częściowego iloczynu będzie taka jak liczba bitów ostatniego iloczynu, tzn. liczby ni.

Aby znaleźć liczbę bitów iloczynu wykorzystamy to, że liczba bitów w iloczynie dwóch liczb jest albo równa sumie liczb bitów obu czynników, albo jest od tej sumy mniejsza o 1 (porównaj omówienie algorytmu mnożenia). Wynika stąd, żc iloczyn n liczb fc-bitowych ma co najwyżej nk bitów. Zatem, jeśli n jest liczbą fc-bitową - z czego wynika, że każda liczba mniejsza od n ma co najwyżej k bitów - to n\ ma co najwyżej nk bitów.

Wobec tego w każdym zn-2 mnożeń potrzebnych do obliczenia n\ mnożymy liczbę co najwyżej fc-bitową (mianowicie liczbę j + 1) przez liczbę mającą co najwyżej nk bitów (mianowicie liczbę _/!). To wymaga co najwyżej nk² operacji na bitach. Musimy wykonać to n — 2 razy. Zatem łączna liczba operacji na bitach jest ograniczona przez (n - 2)nk² = n(n - 2)([log₂ n] + l)². Z grubsza biorąc, to ograniczenie w przybliżeniu wynosi n^ł(log₂«)².

Przykład 7. Znajdźmy ograniczenie górne liczby operacji na bitach potrzebnych do pomnożenia wielomianu Za_tx* stopnia nie większego niż n_x przez wielomian LbjX^J stopnia nie większego niż n₂, przy czym współczynniki obu wielomianów są liczbami całkowitymi nieujemnymi mniejszymi lub równymi m. Załóżmy, że n₂ ^ n_v

Rozwiązanie. Aby obliczyć £ a_{bp czyli współczynnik przy x^v w iloczynie

j+j*»

wielomianów (gdzie 0 < v < n_x + n₂), potrzebujemy n₂ + 1 mnożeń i n₂ dodawań. Liczby, które mnożymy, są ograniczone przez m, a liczby, które dodajemy, są ograniczone przez m²; ale ponieważ musimy dodawać kolejne liczby do sumy częściowej tych liczb, musimy przyjąć n₂m² jako ograniczenie górne wielkości dodawanych liczb. Zatem w obliczeniu współczynnika stojącego przy x^v liczba operacji na bitach wyniesie co najwyżej

(n₂ + l)(log₂m + l)² + n₂ (log₂ (n₂m₂) + 1).

Ponieważ liczba v może przyjąć jedną z n_t + n* *f 1 wartości, więc szukanym ograniczeniem czasu mnożenia wielomianów jest

(«i + n₂ + 1)((h_z + l)(log ₂m + \f + n₂(Iog₂(n₂m²) +1)).

Otrzymamy trochę mniej dokładne ograniczenie, usuwając z tego wzoru jedynki, przez co wzór przyjmie bardziej zwartą postać:

+ (Iogn₂ + 21ogm) j.

s/n₂ (co

Uwaga. Jeśli przyjmiemy n = n_l^n₂ oraz założymy, że m ^ 16 i m > yfn₂

na ogół jest spełnione w praktyce), to ostatnie wyrażenie może być zastąpione znacznie prostszym 4n² (log₂m)². Ten przykład świadczy o tym, że na ogół nie istnieje „właściwa odpowiedź” na pytanie o oszacowanie czasu potrzebnego do wykonania danego zadania. Chcemy mieć wynik w postaci względnie prostej funkcji danych (w tym przypadku n_vn₂ i m), dającej ograniczenie górne, które dla większości danych jest w przybliżeniu tego samego rzędu wielkości co liczba operacji na bitach rzeczywiście potrzebnych w praktyce. Z tego powodu w przykładzie 7 nie chcielibyśmy zastąpić naszego oszacowania przez powiedzmy 4n²m, gdyż dla dużych m dałoby to oszacowanie czasu o wiele rzędów wielkości za duże.

Dotychczas zajmowaliśmy się dodawaniem i mnożeniem liczb ż-bito-wych i /-bitowych. Pozostałe dwa działania arytmetyczne - odejmowanie i dzielenie - mają takie same oszacowania czasu jak odpowiednio dodawanie i mnożenie:

Czas(odęjmowanie liczby jfc-bitowej od liczby /-bitowej) ^ max(£, /);

Czas(dzielenie liczby ^-bitowej przez liczbę /-bitową) < kl.

Dokładniej, odejmowanie wymaga rozszerzenia naszej definicji operacji na bitach tak, by dołączyć operację odejmowania bitu 0 lub 1 od innego bitu 0 lub 1 (uwzględniającej ewentualną „pożyczkę” 1 z poprzedniej kolumny); por. ćwiczenie 8.

Aby przeanalizować dzielenie liczb całkowitych zapisanych w systemie dwójkowym, przyjrzyjmy się ilustracjom takim jak w przykładzie 3. Przypuśćmy, że k ^ / (jeśli k < /, to dzielenie jest trywialne, tzn. iloraz jest zerem, a cała dzielna jest resztą). Znalezienie ilorazu i reszty wymaga co najwyżej k — / -f 1 odejmowań. Każde odejmowanie wymaga / lub / + 1 operacji na bitach; jednak w tym drugim przypadku wiemy, że pierwsza od lewej strony kolumna będzie zawierała bit 0, a więc możemy pominąć tę operację na bitach (traktując ją raczej jak „zaksięgowanie” czegoś, a nie jak obliczenie). Podobnie pomijamy