Karatsuba przyspieszył mnożenie, usuwając jedno z czterech mnożeń
Gdy dwie duże liczby podzielimy na górną i dolną połowę, szkolne mnożenie blokowe wymaga czterech iloczynów połówek. Anatolij Karatsuba zauważył, że środkowe składniki można odzyskać algebraicznie przy użyciu tylko trzech takich mnożeń oraz dodatkowych dodawań i odejmowań. Rekurencyjne powtarzanie tego triku zmienia asymptotyczny koszt z O(n²) operacji na cyfrach do około O(n^1,585). Jedno „zaoszczędzone” mnożenie na każdym poziomie rekursji kumuluje się więc w zupełnie inną klasę skalowania. Współczesna biblioteka GNU MP nadal używa Karatsuby dla odpowiedniego zakresu rozmiarów, a dla większych liczb przechodzi do kolejnych algorytmów.
Cztery iloczyny wydają się nieuniknione
Niech duże liczby mają po dwie części: x=x1·B+x0 i y=y1·B+y0, gdzie B oznacza potęgę podstawy odpowiadającą połowie cyfr. Bezpośrednie rozwinięcie daje x·y=x1y1·B²+(x1y0+x0y1)·B+x0y0. Widać cztery iloczyny połówek: x1y1, x1y0, x0y1 i x0y0.
Jeśli każdy z nich obliczamy rekurencyjnie, otrzymujemy tę samą strukturę co klasyczne mnożenie: cztery podproblemy o połowie rozmiaru. Karatsuba zauważył jednak, że dwa „krzyżowe” iloczyny nie muszą być liczone osobno. Można policzyć trzeci iloczyn kombinacji części, a brakującą sumę odtworzyć przez dodawanie i odejmowanie znanych wyników.
Algebra zamienia drogie mnożenie na tańsze dodawanie
Jedna z form używana w dokumentacji GNU MP oblicza trzy produkty: x1y1, x0y0 oraz (x1-x0)(y1-y0). Z nich da się algebraicznie zrekonstruować pełny wynik. Liczba dużych mnożeń spada z czterech do trzech, choć rośnie liczba dodawań, odejmowań i operacji składania bloków.
Na jednym poziomie może to wyglądać jak niewielka oszczędność. Rekursja wzmacnia jednak efekt. Zamiast zależności T(n)=4T(n/2)+O(n), która prowadzi do zachowania kwadratowego, otrzymujemy T(n)=3T(n/2)+O(n). Wykładnik zmienia się na log2 3≈1,585. Im większe liczby, tym większą przewagę asymptotyczną daje ta różnica.
Pierwszy przełom nie jest ostatnim algorytmem
Karatsuba i Jurij Ofman opublikowali metodę mnożenia liczb wielocyfrowych w 1962 roku. Była to przełomowa demonstracja, że klasyczne kwadratowe mnożenie nie jest asymptotyczną granicą problemu. Później powstały kolejne rodziny metod, m.in. Toom–Cook i algorytmy wykorzystujące transformacje Fouriera.
GNU MP pokazuje, jak wygląda to w realnej bibliotece wielkiej precyzji: dla najmniejszych operandów używa mnożenia bazowego, potem Karatsuby, następnie kolejnych wariantów Tooma, a przy bardzo dużych rozmiarach metod FFT. Nie istnieje jeden zwycięzca dla wszystkich n. Algorytm asymptotycznie lepszy ma narzuty, które dla małych danych mogą przeważać nad korzyścią.
Dlaczego „jedno mnożenie mniej” może zmienić klasę złożoności
W algorytmach dziel i zwyciężaj liczba podproblemów na każdym poziomie jest potęgowana przez liczbę poziomów. Cztery gałęzie, każda dzielona ponownie na cztery, bardzo szybko tworzą więcej pracy niż trzy gałęzie dzielone na trzy. To dlatego lokalna algebraiczna oszczędność wpływa na globalny wykładnik złożoności.
Historia Karatsuby jest dobrym antidotum na intuicję, że szkolny sposób wykonania podstawowej operacji musi być najlepszy. Mnożenie jest tak elementarne, że łatwo potraktować jego koszt jako coś danego. Tymczasem można zmienić sposób organizacji samego działania i uzyskać przyspieszenie, które później przenosi się na dzielenie, potęgowanie, kryptografię i wszystkie obliczenia wykorzystujące wielkie liczby.
Rekurencja wzmacnia lokalną oszczędność na każdym poziomie
Różnicę można zobaczyć po kilku poziomach podziału. Klasyczny schemat czterech iloczynów tworzy 4^k podproblemów po k poziomach rekursji, natomiast Karatsuba tworzy 3^k. Dla k=10 byłoby to odpowiednio ponad milion i niecałe 60 tysięcy podproblemów najniższego poziomu, zanim uwzględnimy dodatkowe dodawania i konkretne progi implementacji. To nie jest bezpośredni model czasu rzeczywistego, ale pokazuje mechanizm zmiany wykładnika. Każde usunięte duże mnożenie powtarza się jako oszczędność w całym niższym poddrzewie rekurencji, dlatego pozornie mała algebraiczna sztuczka staje się asymptotycznym przełomem.
Próg opłacalności jest częścią realnego algorytmu
Asymptotycznie Karatsuba wygrywa z klasycznym mnożeniem, ale dla krótkich liczb dodatkowe dzielenie operandów, dodawania, odejmowania i zarządzanie pamięcią mogą kosztować więcej niż zaoszczędzone mnożenie. Dokumentacja GMP dlatego opisuje progi przełączania między metodami. Poniżej określonego rozmiaru biblioteka używa prostszego basecase multiplication, a dopiero większe operandy uzasadniają Karatsubę i kolejne algorytmy. To praktyczne przypomnienie, że zapis O(n^1,585) nie zawiera stałych kosztów ani zachowania pamięci podręcznej procesora. Biblioteka wielkiej precyzji działa najlepiej jako system kilku algorytmów, a nie jako dogmatyczne zastosowanie asymptotycznie najszybszej metody do każdego przypadku. Teoria wskazuje kierunek skalowania; implementacja musi jeszcze znaleźć moment, od którego przewaga faktycznie się materializuje.