Algorytm Karacuby

Algorytm Karacuby
Rodzaj

Mnożenie

Struktura danych

Duże liczby całkowite

Złożoność
Czasowa

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 Θ, w przypadku mnożenia dwóch liczb składających się z n cyfr. Jest on zatem szybszy od algorytmu klasycznego 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 -cyfrowych liczb i przy podstawie gdzie (jeśli jest nieparzyste, albo ma różną liczbę cyfr niż można to naprawić, dodając zera po lewej stronie tych liczb), rozpisujemy je jako:

gdzie i są mniejsze niż Wynik mnożenia wynosi wtedy:

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 Karacuba zauważył, że możemy ten sam wynik uzyskać, wykonując tylko trzy mnożenia:

Dostajemy wtedy

A zatem tym samym kosztem kilku dodawań i odejmowań zmniejszyliśmy liczbę mnożeń z czterech do trzech.

Każde z tych mnożeń -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 i Mamy

Złożoność

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

dla pewnych stałych i Jego rozwiązaniem jest funkcja rzędu

wynosi w przybliżeniu 1.585, a więc dla dużych funkcja ta ma mniejszą wartość od funkcji kwadratowej. Z powodu kosztów wywołań rekurencyjnych algorytm ten nie jest opłacalny dla małych 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 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