Breaking news in the algorithmic/arithmetic world!

Integer multiplication in time O(n · log n). [1]

It means you can multiply two n-bits integer using roughly n log n operations. It's a *very* important problem because a lot of mathematical software rely on efficient integer multiplication.

It breaks the last best known algorithm [2] (Schönhage–Strassen), that was in O(n · log n · log log n)


But, most importantly, this asymptotic can ve memorized more easily!…

And, if seriously, one question right away: what about hardware, can it be translated into the number of gates?

I have no idea, this is something I know nothing about, sorry! 😅

@erou Seems like it can:
"The main results of this paper also hold in the Boolean circuit model [40, Sec. 9.3], with essentially the same proofs." 👍

@erou log log n is practically 1, tho :-P

I wonder how the coefficients compare for actual uses.

Yep that's still an open question. In the paper they explicitly say that they were interested in the theoretical complexity!

Go on and make the comparisons 😎!

Sign in to participate in the conversation

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!