W szkole dzieci uczą się tabliczki mnożenia. Pamiętają to na pamięć. Powodzenia z liczbami trzycyfrowymi! Tutaj w grę wchodzą algorytmy. Ustawiamy liczby w kolumnie. Mnożysz linia po linii. Przez tysiące lat wierzyliśmy, że nie ma nic lepszego od tego. To jest powolne. Strasznie wolno przy dużych ilościach danych. Ale w 1960 roku 23-letni facet zmienił wszystko. Tajemnica szybkości mnożenia pozostaje wciąż otwarta.
Dlaczego to jest ważne?
Mnożenie to nie tylko zadanie szkolne. Dzięki niemu cały Internet działa. Szyfrowanie, sztuczna inteligencja, przetwarzanie dźwięku. Wszystko to opiera się na mnożeniu. Intensywne rozmnażanie. Kiedy musisz pomnożyć ogromne liczby miliony razy na sekundę, każdy krok ma znaczenie. Nawet niewielki wzrost wydajności pozwala zaoszczędzić miliardy.
Spójrz na metodę szkolną. Dwie cyfry oznaczają cztery mnożenia liczb jednocyfrowych. Trzy stopnie? Dziewięć. Skaluje się kwadratowo. Podwój długość liczby, a praca wzrośnie czterokrotnie. Podwój to jeszcze raz – praca wzrośnie 16 razy. Informatycy nie liczą sekund. Żelazo jest już coraz szybsze. Liczą kroki. Nazywamy to notacją Wielkiego O. Metoda szkolna to O(n²). Kwadratowy. Jeśli długość liczby wzrośnie 1000 razy, ilość pracy eksploduje milion razy.
Obciążenie wzrasta proporcjonalnie do kwadratu liczby cyfr.
Od czasów starożytnych matematyczni geniusze uważali tę kwadratową granicę za prawo natury. Andriej Kołmogorow, radziecka legenda, umieścił swoje nazwisko na wykładzie w 1960 roku. Powiedział studentom MSU: „To wymaga O(n²)”. Było to założenie formalne. Wyzwanie. Poczekaj aż ktoś to potwierdzi lub obali.
Minął dopiero tydzień. Na widowni siedział Anatolij Karatsuba. Miał 23 lata. Wrócił z dowodem na to, że Kołmogorow się mylił. Profesor był zszokowany. Kołmogorow dosłownie sam napisał artykuł dla prestiżowego magazynu, ale jako autora podał Karatsubę. Młody człowiek dowiedział się o tym dopiero, gdy przedruki dotarły pocztą.
Sztuczka
Karatsuba zrozumiał prostą, ale głęboką rzecz. Mnożenie to kosztowna operacja. Fałdy są tanie. Dlaczego ich nie zamienić?
Weźmy 12×34.
Rozbij je.
12 to 10 + 2.
34 to 30 + 4.
Tradycyjnie wykonujesz cztery mnożenia:
1×3
1×4
2×3
2×4
Karatsuba znalazł sposób, aby to zrobić w trzech mnożeniach.
Oblicz pierwszą część: 1×3 = 3.
Oblicz ostatnią część: 2×4 = 8.
Teraz środek. Zwykle zrobiłbyś (1×4) + (2×3). Dwa mnożenia. Zamiast tego dodaj pierwsze liczby: 1+2=3. Dodaj ostatnie: 3+4=7. Pomnóż te kwoty: 3×7=21. Odejmij już znane części. 21 – 3 – 8 = 10.
Voila. Masz średni termin na jedno dodatkowe mnożenie.
Czy to się opłaca?
Dla małych liczb – nie. Koszty dzielenia i dodawania kosztują więcej.
Ale dla 1234×5678? Podziel na pół. Rekurencja. Oddziel te połówki. Zrób to jeszcze raz. Oszczędności sumują się.
Złożoność algorytmu spada do około O(n^1,585).
Liczby tysiąccyfrowe wymagały kiedyś miliona mnożeń liczb jednocyfrowych. Teraz potrzebujesz mniej niż 57 000 kroków. Ogromna różnica.
To nie jest tylko teoria. Python to ma.
Python używa standardowej matematyki szkolnej dla małych danych wejściowych. Gładki.
Ale gdy osiągniesz około 63 miejsca po przecinku (w zależności od siatki cyfr maszyny), Python przełącza przełącznik. Włącza się Karatsuba. Nie widzisz tego. Ale on tam jest. Obsługuje Twoje szyfrowanie.
Algorytmy galaktyczne
Wyścig trwał przez dziesięciolecia. Czy można jechać jeszcze szybciej?
Rok 2019 przyniósł nową niespodziankę. David Harvey i Joris van der Hoeven opublikowali algorytm, który pozostawia Karatsubę daleko w tyle.
O(n log n).
Przeczytaj to jeszcze raz.
Logarytmy rosną niewiarygodnie wolno.
n log n jest tylko nieznacznie większe niż n.
Zasadniczo mnożenie dwóch ogromnych liczb zajmuje teraz mniej więcej tyle samo czasu, co czytanie samych liczb.
To oszałamiające. Wydaje się, że teoretyczny limit został już osiągnięty.
A może nie.
Oto haczyk.
Nie działa to w przypadku liczb, które nas interesują.
Algorytm Harveya i van der Hoevenów staje się szybszy niż algorytm Karatsuby tylko wtedy, gdy liczby stają się bardzo duże. Nie „duży jak numer karty kredytowej”. Galaktycznie duży.
W informatyce istnieje na to określenie: algorytm galaktyczny.
Niezła teoria. Zero praktycznych korzyści. Wymagane liczby są większe niż suma wszystkich transakcji cyfrowych w historii ludzkości.
Utknęliśmy pośrodku.
W większości naszych codziennych obliczeń używamy trików z lat 60.
Nosimy kostiumy XXI wieku ponad matematyką XX wieku.
Czy kiedykolwiek używamy O(n log n) w prawdziwym świecie?
Być może, gdy przetwarzamy dane, ustalamy wielkość galaktyk.
Do tego czasu czekamy.
Następna sztuczka.
Albo lepszy sprzęt, który ukryje nasze lenistwo.
Odpowiedź może nadal być kwadratowa.
Może mieć charakter liniowy.
Jeszcze nie wiemy.
