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 = a_l*10^s + a_p
   b = b_l*10^s + b_p
4. Oblicz kolejne części:
   • p₁ = a_l * b_l
   • p₂ = (a_p + a_l) * (b_p + b_l)
   • p₃ = a_p * b_p
   • Oblicz wynik = p₃*10^2s + (p₂ - p₃ - p₁)*10^s + p₁

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*10² + 13
   50403 = 504*10² + 3
4. Oblicz kolejne części:
   • p₁ = 13 * 3 = 39
   • p₂ = (12 + 13) * (504 + 3) = 12675
   • p₃ = 12 * 504 = 6048
   • Oblicz wynik = 6048*10⁴ + (12675 - 6048 - 39)*10² + 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(n²). W tym algorytmie złożoność spada do O(n^log₂3). 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.   }
6.   int dl = (int)min(log10(a), log10(b)) + 1;
7.   int podzial = (int)pow(10, floor(dl / 2));
8.   int a_prawa = a % podzial;
9.   int a_lewa = a / podzial;
10.   int b_prawa = b % podzial;
11.   int b_lewa = b / podzial;
13.   int czesc1 = MnozKaratsuba(a_prawa, b_prawa);
14.   int czesc2 = MnozKaratsuba((a_prawa + a_lewa), (b_prawa + b_lewa));
15.   int czesc3 = MnozKaratsuba(a_lewa, b_lewa);
17.   return (czesc3 * podzial * podzial) + ((czesc2 - czesc3 - czesc1) * podzial) + czesc1;
18. }

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. }

• Kod źródłowy Implementacja