Algorytm Karacuby

Z Wikipedii, wolnej encyklopedii
(Przekierowano z Algorytm Karatsuby)
Skocz do: nawigacja, szukaj
Algorytm Karacuby
Rodzaj Mnożenie
Struktura danych Duże liczby całkowite
Złożoność
Czasowa \Theta(n^{\log_23})

Algorytm Karacubyalgorytm szybkiego mnożenia dużych liczb całkowitych, opracowany przez Anatolija Karacubę w 1960 i opublikowany razem z Jurijem Ofmanem w 1962[1][2][3] roku. Jego złożoność obliczeniowa wynosi Θ(n^{\log_23}). Jest to lepszy rezultat od algorytmu klasycznego Θ(n2), chociaż dla niewielkich liczb jest mniej praktyczny.

Algorytm[edytuj | edytuj kod]

Do pomnożenia dwóch n-cyfrowych liczb x i y przy podstawie B, gdzie n=2m (jeśli n jest nieparzyste, albo x ma różną liczbę cyfr niż y, można to naprawić dodając zera po lewej stronie tych liczb), rozpisujemy je jako:

x = x1 Bm + x2
y = y1 Bm + y2

gdzie x2 i y2 są mniejsze niż Bm. Wynik mnożenia wynosi wtedy:

xy = (x1Bm + x2)(y1Bm + y2)
= x1y1B2m + (x1y2 + x2y1)Bm + x2y2

Standardową metodą byłoby pomnożenie czterech czynników osobno i dodanie ich po odpowiednim przesunięciu. Daje to algorytm działający w czasie O(n2). Karacuba zauważył że możemy ten sam wynik uzyskać wykonując tylko trzy mnożenia:

X = x1y1
Y = x2y2
Z = (x1 + x2)(y1 + y2) – X – Y

Dostajemy wtedy

Z = (x1y1 + x1y2 + x2y1 + x2y2) – x1y1x2y2
= x1y2 + x2y1

A zatem xy = X B2m + Y + Z Bm; tym samym kosztem kilku dodawań i odejmowań zmniejszyliśmy liczbę mnożeń z czterech do trzech.

Każde z tych mnożeń m-cyfrowych liczb możemy znów wykonać za pomocą algorytmu Karacuby, wykorzystując rekurencję.

Implementacja[edytuj | edytuj kod]

Pseudokod[edytuj | edytuj kod]

procedure karatsuba(num1, num2)
  if (num1 < 10) or (num2 < 10)
    return num1 * num2
 
  /* Obliczanie długości liczb */
  n = max(size_base10(num1), size_base10(num2))
  m = n / 2
 
  /* Podział sekwencji cyfr na pół*/
  high1, low1 = split_at(num1, m)
  high2, low2 = split_at(num2, m)
 
  /* 3 wywołania dla liczb o długości w przybliżeniu mniejszych o połowę */
  X = karatsuba(high1, high2)
  Y = karatsuba(low1, low2)
  Z = karatsuba((low1 + high1), (low2 + high2)) - X - Y
 
  return (X * 10 ^ (2 * m)) + ((Z) * 10 ^ (m)) + (Y)

Przykład[edytuj | edytuj kod]

Chcemy obliczyć iloczyn liczb 1234 i 5678. W tym wypadku B = 10 i m = 2. Mamy

12 34 = 12 ⋅ 102 + 34
56 78 = 56 ⋅ 102 + 78
X = 12 ⋅ 56 = 672
Y = 34 ⋅ 78 = 2652
Z = (12 + 34)(56 + 78) – XY = 46 ⋅ 134 – 672 – 2652 = 2840
X 102⋅2 + Y + Z 102 = 672 0000 + 2652 + 2840 00 = 7006652 = 1234 ⋅ 5678

Złożoność[edytuj | edytuj kod]

Niech T(n) oznacza liczbę operacji potrzebnych do pomnożenia dwóch n-cyfrowych liczb za pomocą algorytmu Karacuby. Dostajemy równanie rekurencyjne:

T(n) = 3 T(n/2) + cn + d

dla pewnych stałych c i d. Jego rozwiązaniem jest funkcja rzędu \Theta(n^{\log_23}).

\log_23 wynosi w przybliżeniu 1.585, a więc dla dużych n funkcja ta ma mniejszą wartość od funkcji kwadratowej. Z powodu kosztów wywołań rekurencyjnych algorytm ten nie jest opłacalny dla małych n. Zwykle przyjmuje się że zaczyna być on opłacalny dla liczb kilkusetbitowych.

Pomysł dzielenia czynników na mniejsze części można uogólnić. Dzieląc każdy z czynników na 3 fragmenty, można zamiast 9 mnożeń wykonać 5, osiągając algorytm o złożoności \Theta(n^{\log_35}). Dalsze zwiększanie liczby części również daje pewien zysk (kosztem znacznego skomplikowania algorytmu), ale jeszcze lepsze wyniki można uzyskać wykorzystując szybką transformatę Fouriera. Daje to najszybszy znany algorytm mnożenia – algorytm Schönhage-Strassena, który jest stosowany do mnożenia liczb złożonych z dziesiątek tysięcy bitów.

Przypisy

  1. A. Karatsuba and Yu. Ofman. Multiplication of Many-Digital Numbers by Automatic Computers. „Proceedings of the USSR Academy of Sciences”. 145, s. 293–294, 1962 (ang.). 
  2. A. A. Karatsuba. The Complexity of Computations. „Proceedings of the Steklov Institute of Mathematics”. 211, s. 169–183, 1995 (ang.). 
  3. D.E. Knuth: The art of computer programming. v.2.. Addison-Wesley Publ.Co., 1969, s. 724. (ang.)

Linki zewnętrzne[edytuj | edytuj kod]