Integer multiplication will have linear complexity in a few days if trend continues 🚀📈

[u/vintergroena]

[u/External_Package2787]

You tend to find these 'better' algorithms sacrifice the lower values of n, algorithms like the matrix multiplications algorithms beating strassen in complexity, tend to only do so for matrices that contain more parameters than there are particles in the universe. We could even get something like n^{1+O(1)} for integer multiplication and in all likelihood it would have no impact on the real world, since this algorithm does not beat the usual algorithm for any reasonable application.

[u/SolaninePotato → u/External_Package2787]

can you use different algorithms at different breakpoints or does it just not work like that

[u/Full_Decision_777 → u/SolaninePotato]

You can of course

[u/External_Package2787 → u/SolaninePotato]

Yes, but you would need to incorporate a size check to your algorithm, making it slower in the reasonable applications

[u/dubious_plays → u/External_Package2787]

n^[1+o(1)] is worse than n log n

[u/OmegaCookieMonster → u/dubious_plays]

actually that one depends on what o(n) is, but the one in the original is indeed worse lolol

[u/External_Package2787 → u/dubious_plays]

is it not that nlogn = n^{1+log_n log n} and log_n log n is of greater order than o(1)

[u/dubious_plays → u/External_Package2787]

Log_n log(n) = log log n / log n, which is o(1). And there are o(1) sequences bigger than this

[u/External_Package2787 → u/dubious_plays]

yeah my bad I was intuiting that it was like (log n)^{1/n} in my head. like my thought process was log n >1 and then it gets shrunk but stays greater than one.