Ve škole se děti učí násobilku. Pamatují si to zpaměti. Hodně štěstí s trojcifernými čísly! Zde vstupují do hry algoritmy. Čísla seřadíte do sloupce. Násobíte řádek po řádku. Po tisíce let jsme věřili, že nic nemůže být lepší než toto. Je to pomalé. Strašně pomalé pro velké množství dat. V roce 1960 ale 23letý chlap vše změnil. Záhada rychlosti množení zůstává stále otevřená.
Proč je to důležité?
Násobení není jen školní úkol. Díky tomu funguje celý internet. Šifrování, umělá inteligence, zpracování zvuku. To vše závisí na násobení. Intenzivní množení. Když musíte násobit obrovská čísla milionkrát za sekundu, záleží na každém kroku. I malé zvýšení efektivity ušetří miliardy.
Podívejte se na školní metodu. Dvě číslice znamenají čtyři násobení jednociferných čísel. Tři stupně? Devět. Měří se kvadraticky. Zdvojnásobte délku čísla a práce se zčtyřnásobí. Znovu to zdvojnásobte – práce se zvýší 16krát. Počítačoví vědci nepočítají vteřiny. Železo je již rychlejší. Počítají kroky. Tomu říkáme notace Big O. Školní metoda je O(n²). Kvadratický. Pokud se délka čísla zvýší o faktor 1000, množství práce exploduje milionkrát.
Zátěž se zvyšuje úměrně druhé mocnině počtu číslic.
Od starověku považovali matematickí géniové tuto kvadratickou hranici za zákon přírody. Andrei Kolmogorov, sovětská legenda, na to uvedl své jméno na přednášce v roce 1960. Studentům MSU řekl: „To trvá O(n²). To byl formální předpoklad. Výzva. Počkejte, až to někdo potvrdí nebo vyvrátí.
Uplynul jen týden. Anatoly Karatsuba seděl v publiku. Bylo mu 23 let. Vrátil se s důkazem, že se Kolmogorov mýlil. Profesor byl šokován. Kolmogorov doslova sám napsal článek pro prestižní časopis, ale jako autora uvedl jméno Karatsuba. Mladík se o tom dozvěděl, až když dotisky dorazily poštou.
Trik
Karatsuba pochopil jednoduchou, ale hlubokou věc. Násobení jsou drahé operace. Záhyby jsou levné. Proč je nevyměnit?
Vezměme 12 × 34.
Rozbijte je.
12 je 10 + 2.
34 je 30 + 4.
Tradičně děláte čtyři násobení:
1×3
1×4
2×3
2×4
Karatsuba našel způsob, jak toho dosáhnout ve třech násobcích.
Vypočítejte první část: 1×3 = 3.
Vypočítejte poslední část: 2×4 = 8.
Nyní střed. Normálně byste udělali (1×4) + (2×3). Dvě násobení. Místo toho sečtěte první čísla: 1+2=3. Přidejte poslední: 3+4=7. Vynásobte tyto částky: 3×7=21. Odečtěte již známé části. 21 – 3 – 8 = 10.
Voila. Máte střední člen za jedno násobení navíc.
Vyplatí se to?
Pro malá čísla – ne. Režijní náklady na dělení a přidávání vás stojí více.
Ale pro 1234×5678? Rozdělit na polovinu. Rekurze. Oddělte tyto poloviny. Udělej to znovu. Úspory se sčítají.
Složitost algoritmu klesne přibližně na O(n^1,585).
Dříve tisícimístná čísla vyžadovala milion násobení jednociferných čísel. Nyní potřebujete méně než 57 000 kroků. Obrovský rozdíl.
To není jen teorie. Python to má.
Python používá standardní středoškolskou matematiku pro malé vstupy. Hladký.
Ale jakmile dosáhnete asi 63 desetinných míst (v závislosti na mřížce číslic stroje), Python přepne přepínač. Karatsuba se zapne. Ty to nevidíš. Ale je tam. Zvládá vaše šifrování.
Galaktické algoritmy
Závod pokračoval po celá desetiletí. Je možné jet ještě rychleji?
Rok 2019 přinesl nové překvapení. David Harvey a Joris van der Hoeven publikovali algoritmus, který nechává Karatsubu daleko za sebou.
O(n log n).
Přečtěte si to znovu.
Logaritmy rostou neuvěřitelně pomalu.
n log n je jen o málo větší než n.
Vynásobení dvou obrovských čísel nyní v podstatě trvá přibližně stejně dlouho jako čtení samotných čísel.
Je to úžasné. Zdá se, že teoretické hranice již bylo dosaženo.
Nebo možná ne.
Tady je háček.
U čísel, která nás zajímají, to nefunguje.
Algoritmus Harveyho a van der Hoevena je rychlejší než algoritmus Karatsuba pouze tehdy, když jsou čísla velmi velká. Ne „velké jako číslo kreditní karty“. Galakticky velký.
V informatice pro to existuje termín: galaktický algoritmus.
Pěkná teorie. Praktický přínos nulový. Požadovaná čísla jsou větší než součet všech digitálních transakcí v historii lidstva.
Uvízli jsme uprostřed.
Pro většinu našich každodenních výpočtů používáme triky z 60. let.
Nosíme kostýmy 21. století přes matematiku 20. století.
Používáme někdy O(n log n) v reálném světě?
Možná, že když zpracováváme data, nastaví velikost galaxií.
Do té doby čekáme.
Další trik.
Nebo lepší vybavení, které skryje naši lenost.
Odpověď může být stále kvadratická.
Může být lineární.
To ještě nevíme.
