- Multiplying large numbers is hard. W 1971 roku dwóch niemieckich profesorów przewidziało algorytm, który uczyniłby je łatwiejszym, ale nikt nigdy go nie udowodnił.
- Do teraz.
- Matematycy z Australii i Francji twierdzą, że ich algorytm może uczynić mnożenie i inne rodzaje arytmetyki znacznie bardziej wydajnymi.
Począwszy od szkoły podstawowej, skomplikowane mnożenie było bólem głowy. Ale docent z Uniwersytetu Nowej Południowej Walii w Sydney w Australii opracował nową metodę mnożenia olbrzymich liczb razem, która jest bardziej wydajna niż „długie mnożenie”, którego tak wielu jest uczonych w młodym wieku.
„Bardziej technicznie, udowodniliśmy przypuszczenie Schönhage’a i Strassena z 1971 roku dotyczące złożoności mnożenia liczb całkowitych”, mówi docent David Harvey w poniższym filmie.
Algorytm Schönhage’a-Strassena, opracowany przez dwóch niemieckich matematyków, był w rzeczywistości najszybszą metodą mnożenia od 1971 do 2007 roku. Chociaż w 2007 roku opracowano szybszą metodę, jest ona dziś rzadko używana.
Schönhage i Strassen przewidzieli, że algorytm mnożenia n-cyfrowych liczb przy użyciu n * log(n) podstawowych operacji powinien istnieć, mówi Harvey. Jego praca jest pierwszym znanym dowodem, że tak jest.
Harvey wybiera przykład 314 pomnożonego przez 159 – duże równanie, z pewnością, ale o wiele większe są używane codziennie w rzeczywistych scenariuszach. Aby rozwiązać ten problem, większość ludzi uczy się mnożyć każdą pojedynczą liczbę razem, a następnie dodawać sumy:
9 jest mnożone przez 4, 1, i 3; następnie 5 jest mnożone przez 4, 1, i 3, i tak dalej. W wyniku otrzymujemy 9 iloczynów cyfra po cyfrze.
Ta metoda jest nazywana n2 lub n podniesione do kwadratu, ponieważ trzeba pomnożyć n przez n pewną liczbę razy. Otrzyma poprawną odpowiedź, ale Schönhage i Strassen zaprojektowali szybszą metodę. To było w stanie wyjść poza n2 i do czegoś mniejszego, ale wyzwanie nadal przedstawiał się w formie n * log(n).
Dla niektórych, widząc słowo w środku problemu matematycznego może być wystarczające, aby ich oczy szkliły się jak oni w klasie algebry. Dla odświeżenia: log to skrót od logarytmu, który pomaga ludziom rozszyfrować wykładniki, które sprawiają, że liczby są podniesione do kwadratu lub sześcianu, a nawet czegoś wyższego. Zatem 2⁵ to 32, ale wyrażone logarytmicznie, wyglądałoby to tak, że log₂(32)=5. Choć może się to wydawać skomplikowane, logarytmy są kluczowe, gdy liczby stają się dużo większe.
Metoda Schönhage-Strassena jest bardzo szybka, mówi Harvey. Jeśli komputer miałby użyć metody kwadratów nauczanej w szkole na problemie, gdzie dwie liczby miały miliard cyfr każda, zajęłoby to miesiące. Komputer korzystający z metody Schönhage-Strassena mógłby to zrobić w 30 sekund.
Ale jeśli liczby rosną do trylionów i dalej, algorytm opracowany przez Harveya i współpracownika Jorisa van der Hoeven w École Polytechnique we Francji może znaleźć rozwiązania szybciej niż algorytm Schönhage-Strassen z 1971 roku.
„Oznacza to, że można wykonywać wszystkie rodzaje arytmetyki bardziej wydajnie, na przykład dzielenie i pierwiastki kwadratowe,” mówi. „Można również obliczać cyfry liczby pi bardziej efektywnie niż wcześniej. Ma to nawet zastosowanie do problemów związanych z wielkimi liczbami pierwszymi.
„Ludzie polowali na taki algorytm przez prawie 50 lat”, kontynuuje. To nie był przesądzony wniosek, że ktoś w końcu osiągnie sukces. Mogło się okazać, że Schönhage i Strassen nie mieli racji i że taki algorytm nie jest możliwy.
„Ale teraz wiemy lepiej”, mówi
.