9752256902

multiply(a, b)

n *— max(\a\, |b|)    (* |x| oznacza długość liczby x *)

if n jest małe then pomnóż a i b klasycznym algorytmem return obliczony iloczyn

P«“ L«/²J

ai *— [a/2^pJ; ao *— a mod 2^P <- |6/2^PJ; b₀ «- 6 mod 2^P 2 <— multiply(ao, bo) y *— multiply(ai + ao, 61 + bo) x «— multiply(ai, &i); return 2^2px + 2^p(y - x - 2) + 2

Fakt 2 Złożoność czasowa powyższego algorytmu wynosi 0(n^log3).

DOWÓD: (Zakładamy, źe a i 6 są liczbami n - bitowymi i n jest potęgą liczby 2.)

Wystarczy pokazać, źe czas działania algorytmu wyraża się wzorem:

_r( s    k    dla n = 1

^{K }}    \ 3T(n/2) + @(n) dla n > 1

Jedyną wątpliwość może budzić fakt, źe wskutek przeniesienia liczby ai + ao i 61 + 60 mogą być (n/2) + 1-bitowe. W takiej sytuacji ai + ao zapisujemy w postaci a'2ⁿ^ + a", a b\ + bo w postaci b'2ⁿ/² + b", gdzie a' i b' są bitami z pozycji (n/2) + 1 liczb a i b, a a" i b" są złożone z pozostałych bitów. Obliczenie y możemy teraz przedstawić jako:

(ai + ao)(i>i + 60) = a!b'2ⁿ + (a'b” + a"b') 2ⁿ/² + a"b"

Jedynym składnikiem wymagającym rekurencyjnego wywołania jest a"b" (obydwa czynniki są n/2-bitowe). Pozostałe mnożenia wykonujemy w czasie 0(n), ponieważ jednym z czynników jest pojedynczy bit (a' lub ł/) lub potęga liczby 2.

Tak więc przypadek, gdy podczas obliczania y występuje przeniesienie przy dodawaniu, zwiększa złożoność jedynie o pewną stałą, nie zmieniając klasy złożoności algorytmu. □

10.2.1 Podział na więcej części

Pokażemy teraz, źe powyższą metodę można uogólnić. Niech k € M będzie dowolną stałą. Liczby a i b przedstawiamy jako

k—1    k—1

a = 2 Oj ■ 2*■/*    b=Y,^b‘-^2<n/t

i=0    i=0

gdzie wszystkie aj oraz bi są liczbami co najwyżej n/A;-bitowymi. Naszym zadaniem jest policzenie liczb co, c\,..., C2k takich, źe dla j = 0,..., 2k:

j

Cj — O-rbj-r-r=0

18