Jaki jest najszybszy algorytm mnożenia dwóch liczb n-cyfrowych?

Chcę wiedzieć, który algorytm jest najszybszy do pomnożenia dwóch liczb n-cyfrowych? Złożoność przestrzeni można tutaj rozluźnić!

Obecnie algorytm Fürera autorstwa Martina Fürera ma złożoność czasową która wykorzystuje transformaty Fouriera w liczbach zespolonych. Jego algorytm jest oparty na algorytmie Schönhage'a i Strassena, który ma złożoność czasową$n \log(n)2^{Θ(log*(n))}$$Θ(n\log(n)\log(\log(n)))$

Innymi algorytmami, które są szybsze niż algorytm mnożenia szkół, są mnożenia Karatsuba, które mają złożoność czasową ≈ i algorytm Toom 3, który ma złożoność czasową zO ( n 1,585 ) Θ ( n 1,465$O(n^{\log_{2}3})$$O(n^{1.585})$$Θ(n^{1.465})$

Zauważ, że są to szybkie algorytmy. Znalezienie najszybszego algorytmu mnożenia jest otwartym problemem w informatyce.

Bibliografia :

1. Algorytm Fürera
2. Mnożenie dużych liczb na podstawie FFT
3. Szybka transformata Fouriera
4. Mnożenie Toom-Cook
5. Algorytm Schönhage – Strassen
6. Algorytm Karatsuba

Zauważ, że algorytmy FFT wymienione przez avi dodają dużą stałą, co czyni je niepraktycznymi dla liczb mniejszych niż tysiące + bitów.

Oprócz tej listy istnieją inne ciekawe algorytmy i otwarte pytania:

• Mnożenie czasu liniowego na modelu pamięci RAM (z obliczeniami wstępnymi)
• $\mathcal{O}\left(\frac {n^2} {\log n} \right)$$1$$\mathcal{O}\left({n^2} \right)$$\mathcal{O}\left(\log n\right)$
• System numerów pozostałości i inne reprezentacje liczb; mnożenie jest czasem prawie liniowym. Minusem jest to, że mnożenie jest modularne, a {wykrywanie przepełnienia, parzystość, porównanie wielkości} są tak samo trudne lub prawie tak trudne, jak konwersja liczby z powrotem do reprezentacji binarnej lub podobnej i wykonanie tradycyjnego porównania; ta konwersja jest co najmniej tak zła jak tradycyjne mnożenie (w tej chwili AFAIK).
  • Inne przedstawicielstwa:
    • $$16 \times 32 = 2^{\log_2 16 + \log_2 32} = 2^{4+5} = 2^{9}$$
      • Minusem jest konwersja do iz reprezentacji logarytmicznej może być tak trudna jak mnożenie lub trudniejsza, reprezentacja może być również ułamkowa / nieracjonalna / przybliżona itp. Inne operacje (dodawanie?) Są prawdopodobnie trudniejsze.
    • $$36 \times 48 = 3^2\cdot 5^1\times 2^{2}\cdot 3^1\cdot 4^1 = {2^2}\cdot {3^2} \cdot 4^1 \cdot 5^1$$
    • Minusem jest to, że wymaga czynników lub faktoryzacji, o wiele trudniejszego problemu niż mnożenie. Inne operacje, takie jak dodawanie, są prawdopodobnie bardzo trudne.