Chcę wiedzieć, który algorytm jest najszybszy do pomnożenia dwóch liczb n-cyfrowych? Złożoność przestrzeni można tutaj rozluźnić!
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ć!
Odpowiedzi:
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 :
źródło
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:
źródło