I realize this is 100% not the point, but is this an immediately practical breakthrough that will change computing?
My extremely limited understanding is “no” as I sorta assume that would be the headline. The main point being that while a MASSIVE improvement over any previous progress it’s still “small” from a practical standpoint.
This is not to downplay the very well conveyed problem this might be, but I just want to make sure I even got that right.
I do wonder if this will be a major issue for future development or if the math experts in diapers right now will grow up in this world and have tools and understanding to assist and we’re just in a rough transition, but unfortunately that’s about as much as I can contribute.
This is very much a theoretical result. The author quotes a redditor or who jokes that the previous bound was nice and round and that was of practical importance:
>The result is of extreme practical importance. Not for actually
multiplying integers (as usual with these algorithms it’s probably not
faster than existing algorithms for integers that can be stored in the
observable universe), but for writing papers. It has always been a hassle
to write down the complexity of integer multiplication or algorithms based
on integer multiplication by introducing soft-O notation, little-o
exponents, epsilons greater than 0, or iterated logarithms. From now on I
can just write O(n log n) in my papers and be done with it!
not at all. even the previous O(n \log n) multiplier is almost never used in practice. In general fourier-based multipliers only start being useful at a minimum when you are multiplying 1000-digit numbers, but even that threshold is low/contentious. they have a definite advantage for ~10,000-digit numbers. this likely has larger overhead, so is only plausibly useful for even larger numbers. you do not often have to multiply these extremely large numbers.
My extremely limited understanding is “no” as I sorta assume that would be the headline. The main point being that while a MASSIVE improvement over any previous progress it’s still “small” from a practical standpoint.
This is not to downplay the very well conveyed problem this might be, but I just want to make sure I even got that right.
I do wonder if this will be a major issue for future development or if the math experts in diapers right now will grow up in this world and have tools and understanding to assist and we’re just in a rough transition, but unfortunately that’s about as much as I can contribute.