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. static int MnozKaratsuba(int a, int b)
2. {
3. if (a < 10 || b < 10)
4. {
5. return a * b;
6. }
8. int dl = (int)Math.Min(Math.Log10(a), Math.Log10(b)) + 1;
9. int podzial = (int)Math.Pow(10, Math.Floor((double)dl / 2));
10. int a_prawa = a % podzial;
11. int a_lewa = a / podzial;
12. int b_prawa = b % podzial;
13. int b_lewa = b / podzial;
15. int czesc1 = MnozKaratsuba(a_prawa, b_prawa);
16. int czesc2 = MnozKaratsuba((a_prawa + a_lewa), (b_prawa + b_lewa));
17. int czesc3 = MnozKaratsuba(a_lewa, b_lewa);
19. return (czesc3 * podzial * podzial) + ((czesc2 - czesc3 - czesc1) * podzial) + czesc1;
20. }

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. static void Main(string[] args)
2. {
3. Console.Write("Podaj pierwszą liczbę\n a = ");
4. int a = Convert.ToInt32(Console.ReadLine());
5. Console.Write("Podaj drugą liczbę\n b = ");
6. int b = Convert.ToInt32(Console.ReadLine());
7. int wynik = MnozKaratsuba(a, b);
8. Console.WriteLine("{0} * {1} = {2}", a, b, wynik);
9. Console.ReadLine();
10. }

• Kod źródłowy Implementacja