Algorytm Fürera

Algorytm Fürer jest algorytm dla mnożenia bardzo dużych liczb całkowitych. Został opublikowany w 2007 roku przez szwajcarskiego matematyka Martina Fürera z State University of Pennsylvania . Algorytm ten asymptotycznie ma jedną z najmniejszych złożoności wśród algorytmów mnożenia i dlatego jest lepszy niż algorytm Schönhage-Strassena . Jej reżim asymptotyczny jest osiągany tylko dla bardzo dużych liczb całkowitych.

Historia

Przed algorytmem Fürera, algorytm Schönage-Strassena, pochodzący z 1971 roku, pozwalał na pomnożenie dwóch liczb całkowitych w czasie . Arnold Schönhage i Volker Strassen również przypuszczali, że minimalna złożoność produktu szybkiego wynosi , gdzie n jest liczbą bitów użytych w binarnym zapisie dwóch liczb całkowitych jako danych wejściowych. O(nielog⁡nielog⁡log⁡nie){\ Displaystyle O (n \ log n \ log \ log n)}O(nielog⁡nie){\ Displaystyle O (n \ log n)}

Złożoność

Algorytm Fürera ma złożoność in , gdzie oznacza iterowany logarytm . Różnica między terminami i jest asymptotyczna na korzyść algorytmu Fürera, ale reżim asymptotyczny jest osiągany tylko dla bardzo dużych liczb. O(nielog⁡nie 2O(log∗⁡nie)){\ Displaystyle O (n \ log n \ 2 ^ {O (\ log ^ {*} n)})}log∗⁡nie{\ displaystyle \ log ^ {*} n}log⁡log⁡nie{\ Displaystyle \ log \ log n}2log∗⁡nie{\ Displaystyle 2 ^ {\ log ^ {*} n}}

Artykuł napisany w 2014 roku przez Harveya, van der Hoevena i Lecerfa pokazuje, że zoptymalizowany algorytm Fürera wymaga operacji i daje algorytm wymagający tylko operacji, a także trzeci algorytm w czasie, ale którego trafność opiera się na przypuszczeniu dotyczącym liczb Mersenne . Algorytmy te są czasami grupowane razem pod pojęciem algorytmu Harveya-van der Hoevena-Lecerfa. O(nielog⁡nie 16log∗⁡nie){\ Displaystyle O (n \ log n \ 16 ^ {\ log ^ {*} n})}O(nielog⁡nie 8log∗⁡nie){\ Displaystyle O (n \ log n \ 8 ^ {\ log ^ {*} n})}O(nielog⁡nie 4log∗⁡nie){\ Displaystyle O (n \ log n \ 4 ^ {\ log ^ {*} n})}

W 2019 roku Harvey i van der Hoeven osiągnęli złożoność algorytmiczną mnożenia, pokonując złożoność algorytmu Fürera. Reżim asymptotyczny jest jednak osiągany dla liczb o rozmiarze większym niż . O(nielog⁡nie){\ Displaystyle O (n \ log n)}2172912{\ Displaystyle 2 ^ {1729 ^ {12}}}

Bibliografia

1. [PDF] M. Fürer (2007). Faster Integer Multiplication Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), 11-13 czerwca 2007 r., San Diego, Kalifornia, USA.
2. A. Schönhage i V. Strassen, „Schnelle Multiplikation großer Zahlen”, Computing 7 (1971), s. 281–292.
3. Używając liczb z rzędu .2264{\ displaystyle 2 ^ {2 ^ {64}}}
4. David Harvey, Joris van der Hoeven i Grégoire Lecerf, Jeszcze szybsze mnożenie liczb całkowitych .
5. David Harvey i Joris van der Hoeven, Mnożenie liczby całkowitej w czasie O (n log n)

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">