- Násobení velkých čísel je těžké. V roce 1971 dva němečtí profesoři předpověděli algoritmus, který by to usnadnil, ale nikdo to nikdy nedokázal.
- Až nyní.
- Matematikové z Austrálie a Francie tvrdí, že jejich algoritmus dokáže násobení a další druhy aritmetiky výrazně zefektivnit.
Ze složitého násobení si už od základní školy dělají hlavu. Docentka z Univerzity Nového Jižního Walesu v Sydney v Austrálii však vyvinula novou metodu násobení obřích čísel, která je efektivnější než „dlouhé násobení“, které se mnozí učí od útlého věku.
„Technicky vzato jsme dokázali domněnku Schönhageho a Strassena z roku 1971 o složitosti násobení celých čísel,“ říká docent David Harvey ve videu níže.
Algoritmus Schönhage-Strassen, který vyvinuli dva němečtí matematici, byl skutečně nejrychlejší metodou násobení v letech 1971 až 2007. Přestože v roce 2007 byla vyvinuta rychlejší metoda, dnes se používá jen zřídka.
Schönhage a Strassen předpověděli, že algoritmus násobení n-ciferných čísel pomocí n * log(n) základních operací by měl existovat, říká Harvey. Jeho článek je prvním známým důkazem, že tomu tak je.
Harvey si vybral příklad 314 vynásobeného 159 – jistě velká rovnice, ale v reálném životě se denně používají mnohem větší. Při řešení tohoto problému se většina lidí učí násobit jednotlivá čísla dohromady a pak součty sečíst:
9 se násobí 4, 1 a 3; pak se 5 násobí 4, 1 a 3 atd. Výsledkem je 9 součinů po číslicích.
Tento způsob se nazývá n2 nebo n na kvadrát, protože je třeba n násobit n-krát. Dostaneme při ní správnou odpověď, ale Schönhage a Strassen navrhli rychlejší metodu. Dokázala přejít z n2 na něco menšího, ale stále se objevovala výzva v podobě n * log(n).
Pro někoho může být pohled na slovo uprostřed matematické úlohy dostatečným důvodem k tomu, aby se mu zaleskly oči jako v hodinách algebry. Pro osvěžení: log je zkratka pro logaritmus, který lidem pomáhá rozluštit exponenty, které z čísel dělají čtverec nebo krychli nebo dokonce něco vyššího. Takže 2⁵ je 32, ale vyjádřeno logaritmicky by to vypadalo jako log₂(32)=5. I když se to může zdát jako sousto, logaritmy mají zásadní význam, když jsou čísla mnohem větší.
Metoda Schönhage-Strassena je velmi rychlá, říká Harvey. Kdyby měl počítač použít metodu čtverce, která se učí ve škole, na problém, kde mají dvě čísla po miliardě číslic, trvalo by to měsíce. Počítač používající Schönhage-Strassenovu metodu by to zvládl za 30 sekund.
Ale pokud by čísla stále rostla do bilionů a dále, algoritmus vyvinutý Harveym a jeho spolupracovníkem Jorisem van der Hoevenem na École Polytechnique ve Francii by mohl najít řešení rychleji než Schönhage-Strassenův algoritmus z roku 1971.
„Znamená to, že můžete efektivněji provádět všechny druhy aritmetiky, například dělení a odmocniny,“ říká. „Také byste mohli počítat číslice pí efektivněji než dříve. Dokonce se to dá použít i na problémy s obrovskými prvočísly.“
„Lidé takový algoritmus hledají už téměř 50 let,“ pokračuje. Nebylo samozřejmé, že se to nakonec někomu podaří. Mohlo se ukázat, že se Schönhage a Strassen mýlili a že žádný takový algoritmus není možný.
„Ale teď už to víme lépe,“ říká.