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. def MnozKaratsuba(a, b):
2. if a < 10 or b < 10:
3. return a * b
5. dl = int(min(math.log10(a), math.log10(b)) + 1)
6. podzial = int(pow(10, math.floor(dl / 2)))
7. a_lewa, a_prawa = a // podzial, a % podzial
8. b_lewa, b_prawa = b // podzial, b % podzial
10. czesc1 = MnozKaratsuba(a_prawa, b_prawa)
11. czesc2 = MnozKaratsuba(a_prawa + a_lewa, b_prawa + b_lewa)
12. czesc3 = MnozKaratsuba(a_lewa, b_lewa)
14. return (czesc3 * podzial * podzial) + ((czesc2 - czesc3 - czesc1) * podzial) + czesc1

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. a = int(input("Podaj pierwszą liczbę\n a = "))
2. b = int(input("Podaj drugą liczbę\n b = "))
3. wynik = MnozKaratsuba(a, b)
4. print(a, "*", b, "=", wynik)

• Kod źródłowy Implementacja