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

21

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

Andy
źródło
1
Czy jesteś zainteresowany pytaniem teoretycznym lub praktycznym?
Yuval Filmus,
Oba, ale bardziej skłonne do praktycznego!
Andy,
1
W przypadku pytania praktycznego zalecam użycie GMP. Jeśli jesteś ciekawy, z czego korzystają, zajrzyj do dokumentacji lub kodu źródłowego.
Yuval Filmus,
Nikt nie wie. Jeszcze go nie znaleźliśmy.
JeffE

Odpowiedzi:

22

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ąnlog(n)2Θ(log(n))Θ(nlog(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(nlog23)O(n1.585)Θ(n1.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
avi
źródło
Zwróć uwagę na ostatni artykuł D. Harveya i J. van der Hoevena (marzec 2019 r.) Opisujący algorytm o złożoności . O(nlnn)
hardmath
9

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)
  • O(n2logn)1O(n2)O(logn)
  • 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×32=2log216+log232=24+5=29
        • 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×48=3251×223141=22324151
      • 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.
Realz Slaw
źródło
1
Uważam, że podejście oparte na twierdzeniu o pozostałościach / chińskich pozostałościach z właściwymi modułami może prowadzić do przyspieszenia w porównaniu z tradycyjnym pomnażaniem, nawet z powrotem konwersji; w pewnym momencie było to w rozdziale 4 TAOCP, przynajmniej jako przypis. (Wciąż nie zbliża się do metod opartych na FFT, ale jest to interesująca nuta historyczna)
Steven Stadnicki
@StevenStadnicki oh spoko, muszę na to spojrzeć; zdajesz sobie sprawę ze złożoności?
Realz Slaw