[url]https://hal.archives-ouvertes.fr/hal-02070778/document[/url]

Integer multiplication in time O(n log n).

A 1971 conjecture of Schönhage and Strassen about the complexity of integer multiplication, proven. By presenting a new algorithm that works in O(n log n).

(Directly linking the paper rather than what news sites wrote about it because the news site i saw wrote something more on the stoopid side)

(please, move to appropriate topic or split into a new one in an appropriate subforum as neccessary)

[QUOTE=DukeBG;512741][url]https://hal.archives-ouvertes.fr/hal-02070778/document[/url]

Integer multiplication in time O(n log n).

A 1971 conjecture of Schönhage and Strassen about the complexity of integer multiplication, proven. By presenting a new algorithm that works in O(n log n).

(Directly linking the paper rather than what news sites wrote about it because the news site i saw wrote something more on the stoopid side)

(please, move to appropriate topic or split into a new one in an appropriate subforum as neccessary)[/QUOTE]Erm, did I misread this part?[quote]Let n[sub]0[/sub] >= 2[sup]4096[/sup], and suppose that we wish to multiply integers with n bits. For n < n[sub]0[/sub], we may use any convenient base-case multiplication algorithm, such as the classical O(n[sup]2[/sup]) algorithm.[/quote]So it only applies to numbers greater than 2[sup]2^4096[/sup]? That is rather large and not practical today.

And why are they suggesting a crappy O(n[sup]2[/sup]) for numbers less than 2[sup]2^4096[/sup]?

[size=1]Why can't we nest the [sup] operator :mad:[/size]

[QUOTE=retina;512742]Erm, did I misread this part?So it only applies to numbers greater than 2[sup]2^4096[/sup]? That is rather large and not practical today.

And why are they suggesting a crappy O(n[sup]2[/sup]) for numbers less than 2[sup]2^4096[/sup]?[/QUOTE]The authors acknowledge it is not currently practical.

As to your second point, who cares what you use for the small number multiplication? It makes absolutely no difference whatsoever to the asymptotic performance. If a "small number" is bounded, so is the time taken to multiply two together. Indeed, it can be done in constant time. To see this latter point, multiply together all possible pairs of small numbers and measure how long it takes to perform each. Then take as your constant time the maximum value in your list of timings. If you want truly constant time under all circumstances, the small number algorithm is to perform the multiplication and then wait until the maximum time has passed before doing anything else.

[QUOTE=xilman;512743]As to your second point, who cares what you use for the small number multiplication?[/QUOTE]Only most people using this forum and running code that multiplies numbers. And indeed anyone that is using a TLS/SSL connection will also care. So yeah, just most of the world, leaving only those living in a cave with no electronic devices, they won't care. :reality-check:

[QUOTE=retina;512742]Erm, did I misread this part?So it only applies to numbers greater than 2[sup]2^4096[/sup]? That is rather large and not practical today.

And why are they suggesting a crappy O(n[sup]2[/sup]) for numbers less than 2[sup]2^4096[/sup]?
[/QUOTE]

No, in the proof they're using the classical algorithm for n<n0, so for n<2^4096. But yeah, it is easy to misread.

[QUOTE=retina;512745]Only most people using this forum and running code that multiplies numbers. And indeed anyone that is using a TLS/SSL connection will also care. So yeah, just most of the world, leaving only those living in a cave with no electronic devices, they won't care. :reality-check:[/QUOTE]Given that it's impractical, why should anyone care?

This is a mathematical breakthrough. Absolutely no-one believes it is a technological achievement.

[QUOTE=xilman;512754]Given that it's impractical, why should anyone care?

This is a mathematical breakthrough. Absolutely no-one believes it is a technological achievement.[/QUOTE]I thought we were discussing the O(n[sup]2[/sup]) portion.

[QUOTE=retina;512742][size=1]Why can't we nest the [sup] operator :mad:[/size][/QUOTE]
Have you tried this?
[TEX]2^{2^{2^2}}[/TEX]

[QUOTE=Uncwilly;512766]Have you tried this?
[TEX]2^{2^{2^2}}[/TEX][/QUOTE][tex]I haven't. I don't understand tex.[/tex]

And tex requires images to be enabled, so it isn't as universal as html codes.

ETA: We used to be able to nest sup and sub and mix into spoilers, and whatever. But now it is broken.

[QUOTE=retina;512742]And why are they suggesting a crappy O(n[sup]2[/sup]) for numbers less than 2[sup]2^4096[/sup]?

[size=1]Why can't we nest the [sup] operator :mad:[/size][/QUOTE]

You mean, the standard text editing tool? Dunno. But that's why tex tags are available:

[tex]2^{2^{4096}}\text{ or }2^{2^{2^{12}}}[/tex]

I wound up learning basic tex stuff on my own as an absolute beginner. It was an adventure.

[QUOTE=Dr Sardonicus;512771]You mean, the standard text editing tool?[/QUOTE]I mean the BB codes.

2[sup]2[sup]4096[/sup][/sup]

That used to work okay, but now it is broken.

I could maybe cheat with this

2[sup]2⁴⁰⁹⁶[/sup]

But that only works for one more level.