I was reading the article Integer multiplication in time O(n log n) by David Harvey and Joris Van Der Hoeven, 2019.
Could this discovery increase the throughput of future CPU's? If so could we determine by how much preemptively?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Could any CPU instruction get noticeably faster due to a better multiplication method for large numbers? $\endgroup$– greybeardMay 9, 2019 at 20:00
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
I don't see the relevance.
New multiplication algorithms only offer a practical improvement for numbers with huge numbers of bits and probably don't beat existing algorithms until you're dealing with numbers with thousands or even millions of bits. For an extreme example, Fürer's algorithm, which runs in time $O(n\log n\, 2^{O(\log^*n)})$ will only become competitive with Schönhage and Strassen's $O(n\log n\log\log n)$ algorithm for $n>2^{64}$ bits and, let's be honest, whatever it is that you're multiplying, it doesn't have $2^{64}$ bits. In contrast, CPUs operate on fixed-length words with a few tens of bits.
Most of what a CPU does isn't multiplying numbers, anyway.
Also, note that Harvey and van der Hoeven "make no attempt to... exhibit a practical multiplication algorithm" (page 2 of their preprint).
answered May 9, 2019 at 20:13
$\begingroup$
$\endgroup$
No, it's not helping.
You can do n bit multiplication in O (log n) time, not O (n log n). The only problem is that you need an enormous amount of hardware to do this, growing as O (n^2), while this paper describes multiplication with a fixed amount of hardware.
But since a CPU typically just has only a 64 bit multiply unit, that O (n^2) space is no big deal, and the O (log n) is unbeatable. Even 256 bit would be doable, but there doesn't seem much need for it.
