ALG#2

232 Rozdział 9. Zaawansowane techniki programowania I 9

pozornie całą żądaną pamięć, faktycznie operuje jej „stronami”, które dosyla I mu w miarę potrzeb system operacyjny, sprawa może wyglądać już trochę gorzej. Drugim istotnym powodem spadku efektywności algorytmu dla dużych (praktycznie występujących) wartości N, jest kumulacja wielokrotnych wywołali rekurencyjnych i wzrastającej „zauważalności” roli operacji dodawania i odejmowania. Z wymienionych wyżej względów algorytm V. Strassena należy raczej traktować jako ciekawy wynik teoretyczny , o niepodważalnych walorach edukacyjnych!

9.1.3.Mnożenie liczb całkowitych

Kolejny przykład jest również natury obliczeniowej: zajmiemy się mnożeniem liczb całkowitych.

Mnożenie dw'óch liczb całkowitych X i Z, których reprezentacja wewnętrzna ma rozmiar /V-hitów, jest operacją klasy OfN²). Zakładamy, że mnożenie jest wykonywane klasycznie, tak jak nas tego nauczono w szkole podstawowej (sumujemy „w słupku” N wyników iloczynów cząstkow'ych. każdy z nich jest klasy O(n)).

Metoda „dziel-i-rządź” w przypadku mnożenia liczb całkowitych może być zastosowana po dokonaniu następującej obserwacji:

,v

X = [A B] = A *2^y + B,

Y = [C D] = C *2² A-D.

A i B oraz C i D oznaczają odpowiednio „połówki” reprezentacji binarnych liczb X i Y. Iloczyn X*Y może być zapisany jako:

w    v

XY=AC-2² +(AD+ BC)-2² + BI).

Jeśli założymy, że A'jest potęgą liczby 2 (co jest generalnie prawdą we współczesnych komputerach), to możemy wyrazić złożoność obliczeniową programu przez:

T(V = 1,

T(N) = 4rfy V cN.

W równaniach tych zaznaczamy wpływ czterech kosztownych operacji mnożenia plus pewien proporcjonalny do N koszt związany z dodawaniami i przesu-