4 ms·
Is this something users of GNU MP will get to see the benefits of?
by TazeTSchnitzel 12y ago
Is this something users of GNU MP will get to see the benefits of?
- fdej 12y agoIt's mostly a theoretical result. The previous FFT-based multiplication algorithms (including the one in GMP) all have almost linear complexity. For integers that can be stored within the observable universe, overhead and memory locality matter much more than nested logarithmic factors in the asymptotic complexity bound. It's conceivable that the new algorithm is superior in the real world, but nothing really suggests that it should be.
- jekub 12y agoThe improvement is only theoretical. The Fürer algorithm is quicker than Schönhage-Strassen only for impractical numbers and no arbitrary precision toolkit use it as far as I know. The Fürer algorithm change the loglog term of the complexity to 2^log* which doesn't change anything in practice for workable numbers but it also add a lot to the constant term which is not counted by the big O notation but is very important in practice.
- userbinator 12y agoThat reminds me of the fastest known (in terms of number of multiplications) matrix-multiplication algorithm, where the constant factor is so huge that it's of no practical use. Even the more practical ones e.g. http://en.wikipedia.org/wiki/Strassen_algorithm http://en.wikipedia.org/wiki/Strassen_algorithm trades 8 multiplications and 4 additions with 7 multiplications and 18 additions, won't be all that much faster on modern architectures where multiplication is often surprisingly fast (almost the same as addition) and how much data is read/written also matters (memory bandwidth and latency).
- arghbleargh 12y agoThose are actually matrix multiplications and additions, so it can make a significant difference (e.g. it's way faster to add two 50x50 matrices than to multiply them).
- throwaway_yy2Di 12y agoIt's not likely; the authors checked, "We have implemented an unoptimised version of the algorithm from section 8 in the Mathemagix system [29] and found our implementation to be an order of magnitude slower than the Gmp library [23]. There is certainly room for improvement, but we doubt that even a highly optimised implementation of the new algorithm will be competitive in the near future." As the other people point out, when an algorithm has asymptotic complexity improvements (like here), it's often much slower on small problem sizes (the constant factor), on real hardware (i.e. memory locality). And check out the table of multiplication algorithms in the paper's introduction, and the table in the GMP manual [0]. The FFT (Schönhage–Strassen) GMP uses is O(n log n log log n), and the algorithm in this paper is O(n log n 8^(log* n)). Those functions [1] diverge a bit slowly: they have the same value at n=2^2^2^21 (2^2^2,097,152). [0] https://gmplib.org/manual/Multiplication-Algorithms.html#Multiplication-Algorithms https://gmplib.org/manual/Multiplication-Algorithms.html#Mul... [1] https://en.wikipedia.org/wiki/Iterated_logarithm https://en.wikipedia.org/wiki/Iterated_logarithm