Follow

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)

[1] hal.archives-ouvertes.fr/hal-0
[2] en.wikipedia.org/wiki/Sch%C3%B

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

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

@amiloradovsky
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.

@varx
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
Mathstodon

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