Algorytm Karacuby

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^[1][2][3] roku. Jego złożoność obliczeniowa wynosi Θ${\displaystyle (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 ${\displaystyle \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 ${\displaystyle n}$-cyfrowych liczb ${\displaystyle x}$ i ${\displaystyle y}$ przy podstawie ${\displaystyle B,}$ gdzie ${\displaystyle n=2m}$ (jeśli ${\displaystyle n}$ jest nieparzyste, albo ${\displaystyle x}$ ma różną liczbę cyfr niż ${\displaystyle y,}$ można to naprawić, dodając zera po lewej stronie tych liczb), rozpisujemy je jako:

${\displaystyle x=x_{1}B^{m}+x_{2}}$

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

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

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

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

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

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

Dostajemy wtedy

${\displaystyle {\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 ${\displaystyle 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ń ${\displaystyle 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 ${\displaystyle B=10}$ i ${\displaystyle m=2.}$ Mamy

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

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

${\displaystyle X=12\cdot 56=672}$

${\displaystyle Y=34\cdot 78=2652}$

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

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

Złożoność

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

${\displaystyle T(n)=3T(n/2)+cn+d}$

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

${\displaystyle \log _{2}3}$ wynosi w przybliżeniu 1.585, a więc dla dużych ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle \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.

Przypisy

Linki zewnętrzne

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