Nawet najprostsze działania mogą kryć w sobie wielkie tajemnice. Po pół wieku matematycznych poszukiwań naukowcy potwierdzili istnienie algorytmu, który mnoży ogromne liczby szybciej, niż dotychczasowe metody.
W 1971 r. dwóch niemieckich matematyków, Arnold Schönhage i Volker Strassen, przewidziało, iż istnieje jeszcze szybszy sposób mnożenia dużych liczb niż jakikolwiek znany wówczas algorytm. Problem polegał jednak na tym, iż ich pomysł pozostał jedynie hipotezą. Przez 50 lat nikomu nie udało się udowodnić, iż taki algorytm rzeczywiście istnieje. Aż do teraz…
David Harvey – matematyk z Uniwersytetu Nowej Południowej Walii w Sydney wraz z Jorisem van der Hoevenem z École Polytechnique we Francji, opracowali dowód potwierdzający przewidywania Niemców. Oznacza to, iż istnieje sposób, by mnożyć n-cyfrowe liczby w czasie proporcjonalnym do n * log(n). Jest to ogromnym krokiem naprzód względem tradycyjnego mnożenia, którego uczymy się w szkole.
Po co to komu?
Już w latach 70. Schönhage i Strassen stworzyli szybszy algorytm, który przez dekady pozostawał najszybszą znaną metodą, ale tylko do pewnego momentu. Gdy liczby osiągały naprawdę gigantyczne rozmiary (miliardy czy biliony cyfr), to choćby ten algorytm stawał się niewystarczający. Nowy algorytm, który właśnie udało się potwierdzić, nie tylko przebija poprzedni pod względem szybkości, ale też działa efektywnie przy największych możliwych liczbach.
David Harvey i Joris van der Hoeven nie tylko udowodnili, iż taki superwydajny algorytm teoretycznie istnieje. Oni pokazali, jak go skonstruować.
Ich metoda to dalsze optymalizowanie transformaty Fouriera w tzw. dziedzinie modularnej (czyli na liczbach całkowitych, ale w cyklu jak na zegarze), rozkładanie liczb na bloki, wykonywanie operacji na tych blokach z użyciem złożonych transformacji matematycznych, a następnie łączenie wyników w sposób, który minimalizuje ilość operacji pośrednich. Nowe podejście nie tylko przyspiesza samo mnożenie, ale też sprawia, iż efektywniejsze stają się inne operacje matematyczne.
Wiedza nie od razu trafi do podręczników, ale już teraz może znaleźć swoje zastosowanie
O ile większość z nas nie zamierza mnożyć bilionowych liczb, to takie działania w wielu dziedzinach są codziennością. Obliczanie kolejnych cyfr liczby Pi, badanie gigantycznych liczb pierwszych, szyfrowanie danych w kryptografii, czy choćby operacje wykonywane w procesorach komputerów. To właśnie wszędzie tam liczy się szybkość i precyzja.
Jeśli użyjemy tradycyjnej metody do mnożenia dwóch liczb o miliardzie cyfr, komputer do wykonywania obliczeń może potrzebować miesięcy. Współczesne algorytmy, na czele z nowym, skracają ten czas do sekund. Co więcej, szybsze mnożenie oznacza też szybsze dzielenie, wyciąganie pierwiastków czy obliczanie logarytmów. To może mieć wpływ na rozwój szybszych i bardziej wydajnych systemów obliczeniowych.
Nowy algorytm nie od razu trafi do podręczników szkolnych, ale już teraz może znaleźć zastosowanie w najbardziej zaawansowanych systemach obliczeniowych świata. Oznacza to, iż choćby najprostsze działania mogą mieć ogromne znaczenie dla naszej cyfrowej przyszłości.
*Źródło zdjęcia wprowadzającego: Andrew Angelov / Shutterstock
