Algorytm Karacuby

Algorytm Karacuby

Rodzaj	Mnożenie
Struktura danych	Duże liczby całkowite
Złożoność
Czasowa	$\Theta (n^{\log _{2}3})$

Algorytm Karacuby – algorytm szybkiego mnożenia dużych liczb całkowitych, opracowany przez Anatolija Karacubę w 1960 i opublikowany razem z Jurijem Ofmanem w 1962 roku. Jego złożoność obliczeniowa wynosi Θ$(n^{\log _{2}3}),$ w przypadku mnożenia dwóch liczb składających się z n cyfr. Jest on zatem szybszy od algorytmu klasycznego $\Theta (n^{2}),$ dla odpowiednio dużych wartości n. Mnożenie niewielkich liczb jest szybsze przy pomocy mniej skomplikowanego algorytmu klasycznego.

Algorytm

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=x_{1}B^{m}+x_{2}$

$y=y_{1}B^{m}+y_{2}$

gdzie $x_{2}$ i $y_{2}$ są mniejsze niż $B^{m}.$ Wynik mnożenia wynosi wtedy:

${\begin{aligned}xy&=(x_{1}B^{m}+x_{2})(y_{1}B^{m}+y_{2})\\[2px]&=x_{1}y_{1}B^{2m}+(x_{1}y_{2}+x_{2}y_{1})B^{m}+x_{2}y_{2}\end{aligned}}$

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(n^{2}).$ Karacuba zauważył, że możemy ten sam wynik uzyskać, wykonując tylko trzy mnożenia:

$X=x_{1}y_{1}$

$Y=x_{2}y_{2}$

$Z=(x_{1}+x_{2})(y_{1}+y_{2})-X-Y$

Dostajemy wtedy

${\begin{aligned}Z&=(x_{1}y_{1}+x_{1}y_{2}+x_{2}y_{1}+x_{2}y_{2})-x_{1}y_{1}-x_{2}y_{2}\\[2px]&=x_{1}y_{2}+x_{2}y_{1}\end{aligned}}$

A zatem $xy=XB^{2m}+Y+ZB^{m};$ 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

Pseudokod

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

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

$12\ 34=12\cdot 10^{2}+34$

$56\ 78=56\cdot 10^{2}+78$

$X=12\cdot 56=672$

$Y=34\cdot 78=2652$

$Z=(12+34)(56+78)-X-Y=46\cdot 134-672-2652=2840$

$X10^{2\cdot 2}+Y+Z10^{2}=672\ 0000+2652+2840\ 00=\mathbf {7006652} =1234\cdot 5678$

Złożoność

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)=3T(n/2)+cn+d$

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

$\log _{2}3$ 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 _{3}5}).$ 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.

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Karatsuba Multiplication, [w:] MathWorld, Wolfram Research  (ang.).
• Karatsuba’s Trick. W: Daniel J. Bernstein: Multidigit multiplication for mathematicians. [dostęp 2014-07-06].brak strony w książce
• Karatsuba Multiplication on Fast Algorithms and the FEE. [dostęp 2014-07-06]. (ang.).
• Implementacja algorytmu w C++