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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityI 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?
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).
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.