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] https://hal.archives-ouvertes.fr/hal-02070778/document

[2] https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm

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! 😅

"The main results of this paper also hold in the Boolean circuit model [40, Sec. 9.3], with essentially the same proofs." 👍

@erou neat!!!

@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 😎!

Andrew Miloradovsky@amiloradovsky@functional.cafe@erou

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