Strona główna » Algorytmy » Artykuły » Algorytm Karatsuba
 

Algorytm Karatsuba

Wstęp

Algorytm Karatsuba pozwala na szybkie mnożenie bardzo dużych liczb. Jego zaletą jest wykonanie mniejszej ilości operacji mnożenia, a zwiększenia potrzebnych operacji dodawania. W tym artykule zostanie wyjaśniona zasada działania tego algorytmu oraz jak można go zaimplementować w programie.

Opis algorytmu

Algorytm opiera się na idei "dziel i zwyciężaj". A. Karatsuba zauważył, że mnożone liczby można podzielić na dwie części, a następnie na ich podstawie wyliczyć trzy części, które po odpowiednim zsumowaniu zwrócą iloczyn. W trakcie liczenia można wykorzystać rekurencję.

Oto lista kroków algorytmu (dla wersji rekurencyjnej) do obliczenia iloczynu liczby a i b:

  1. Pobierz długość krótszej liczby dl = min(długość(a), długość(b))
  2. Oblicz miejsce podziału liczby s = floor(dl/2)
  3. Podziel liczby na część lewą i prawą po s cyfrach od prawej
    a = al*10s + ap
    b = bl*10s + bp
  4. Oblicz kolejne części:
    • p1 = al * bl
    • p2 = (ap + al) * (bp + bl)
    • p3 = ap * bp
    • Oblicz wynik = p3*102s + (p2 - p3 - p1)*10s + p1

Do obliczania iloczynów w punkcie 4. można rekurencyjnie wykorzystać algorytm Karatsuba, ale należy pamiętać, że jeśli jedna z liczb jest pojedynczą cyfrą to należy zwrócić zwykły iloczyn, a nie liczony przy pomocy tego algorytmu.

Przykład

Przyjmijmy za a = 1213, a za b = 50403. Oto kolejne kroki obliczania iloczynu:

  1. dl = min(długość(a), długość(b)) = min(4, 5) = 4
  2. s = floor(dl/2) = 2
  3. Podziel liczby na część lewą i prawą po s cyfrach od prawej
    1213 = 12*102 + 13
    50403 = 504*102 + 3
  4. Oblicz kolejne części:
    • p1 = 13 * 3 = 39
    • p2 = (12 + 13) * (504 + 3) = 12675
    • p3 = 12 * 504 = 6048
    • Oblicz wynik = 6048*104 + (12675 - 6048 - 39)*102 + 39 = 60480000 + 658800 + 39 = 61138839

Jak można zauważyć obliczenia cząstkowe są znacznie prostsze niż ostateczny wynik, który też łatwo obliczyć, ponieważ odpowiednie części niewiele na siebie nachodzą.

Przykład

Algorytm Karatsuba porównuje się z zwyczajnym algorytmem mnożenia, którego złożoność szacuje się na O(n2). W tym algorytmie złożoność spada do O(nlog23). W przypadku algorytmu obliczającego rekurencyjnie warto dzielić liczby na dwie części o jak najbliższej długości.

Implementacja

Oto przykładowy algorytm MnozKaratsuba(). Przyjmuje on dwie liczby całkowite a i b dla których zostaje zwrócony iloczyn.

  1. int MnozKaratsuba(int a, int b) {
  2.   if (a < 10 || b < 10) {
  3.     return a * b;
  4.   }
  5.   int dl = (int)min(log10(a), log10(b)) + 1;
  6.   int podzial = (int)pow(10, floor(dl / 2));
  7.   int a_prawa = a % podzial;
  8.   int a_lewa = a / podzial;
  9.   int b_prawa = b % podzial;
  10.   int b_lewa = b / podzial;
  11.   int czesc1 = MnozKaratsuba(a_prawa, b_prawa);
  12.   int czesc2 = MnozKaratsuba((a_prawa + a_lewa), (b_prawa + b_lewa));
  13.   int czesc3 = MnozKaratsuba(a_lewa, b_lewa);
  14.   return (czesc3 * podzial * podzial) + ((czesc2 - czesc3 - czesc1) * podzial) + czesc1;
  15. }

Algorytm oblicza iloczyn w sposób rekurencyjny. Jeśli przynajmniej jedna z liczb jest cyfrą to zwracany jest iloczyn "tradycyjny". Dla większych liczb algorytm liczy według wzoru podanego na początku artykułu.

Testowanie funkcji

Poniższy fragment kodu wczyta od użytkownika dwie liczby, a następnie wypisze ich iloczyn obliczony przy pomocy algorytmu Karatsuba.

  1. int main() {
  2.   int a, b;
  3.   cout << "Podaj pierwsza liczbe\n a = ";
  4.   cin >> a;
  5.   cout << "Podaj druga liczbe\n b = ";
  6.   cin >> b;
  7.   int wynik = MnozKaratsuba(a, b);
  8.   cout << a << " * " << b << " = " << wynik;
  9.   system("pause");
  10.   return 0;
  11. }