> <i>in 1960, the 23-year-old Russian mathematician Anatoly Karatsuba took a seminar led by Andrey Kolmogorov [....] Kolmogorov asserted that there was no general procedure for doing multiplication that required fewer than n^2 steps. Karatsuba thought there was—and after a week of searching, he found it.</i><p>Karatsuba's method is beautiful and actually quite simple to explain.<p>Suppose you want to multiply two 200-digit numbers. Write them as aX+b and cX+d, where X=10^100.
We want to compute the product (aX+b)(cX+d), which is (ac)X^2 + (ad+bc)X + (bd).<p>By the naive method, we'd end up effectively performing all four multiplications ac, ad, bc, bd.
Karatsuba observed that we can do it with just three multiplications: ac, bd, and (a+b)(c+d)
— and get our (ad+bc) as (a+b)(c+d)-ac-bd.<p>Doing this recursively (so that T(n) = 3T(n/2) + O(n)) gives Karatsuba's method, cutting down the n^2 time of the naive method to about n^1.58 time.<p>[1]: <a href="https://en.wikipedia.org/wiki/Karatsuba_algorithm" rel="nofollow">https://en.wikipedia.org/wiki/Karatsuba_algorithm</a>
,,Hardware changes with the times, but best-in-class algorithms are eternal''<p>Nowdays for these kind of problems the really interesting solution is the best parallel solution. It may be elegant to still prove things for turing machines, but a GPU has 2000 running threads (and if the tensor cores could be used, it's even more instructions), so an algorithm implementation that's not using it is about 100x inferior in practice.
Is "Perfect" really an appropriate qualifier here? Did the source article present a proof that O(n log n) is the lowest growth order for this kind of task? Or am I just out of the loop and it's already known that this is the case?<p><i>Update:</i> Apparently, the article actually says that the approach is <i>not</i> perfect.
This article was originally published in Quanta Magazine: <a href="https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/" rel="nofollow">https://www.quantamagazine.org/mathematicians-discover-the-p...</a>
"The speed gap between multiplication and addition has narrowed considerably over the past 20 years to the point where multiplication can be even faster than addition in some chip architectures."<p>Does anyone have an example of hardware where multiplication is actually faster than addition? That's not an intuitive result unless they're talking about floating point numbers, and even then...
I remember implementing strassen, only to be surprised that the naive implementation was actually faster, because it better exploited the machine architecture... that is until I tried using absolutely huge numbers.<p>This recent innovation is very exciting.
"It was kind of a general consensus that multiplication is such an important basic operation that, just from an aesthetic point of view, such an important operation requires a nice complexity bound"<p>It is just nuts that this kind of reasoning works out reliably.
Ok I'll be that guy - where is the reference implementation and at what n can I expect an improvement over existing libgmp multiplication on a core i7 ?
I was going to make a joke that they could have found out years ago by talking to biologists, but then it turned out that this article is really fascinating!
Strassen, perhaps unsurprisingly, also has something to say about matrix multiplication:<p><a href="https://en.wikipedia.org/wiki/Strassen_algorithm" rel="nofollow">https://en.wikipedia.org/wiki/Strassen_algorithm</a><p>"Strassen's algorithm works for any ring, such as plus/multiply..."
Could someone explain how one can use the FFT in an algorithm for multiplication?<p>I guess I would understand if I understood what FFT actually does 'under the hood', but I assumed fft itself required multiplication.
Are exponentiation operations much faster than multiplication since an exponentiation b^n is just n additions? Given that is true, I wonder if there is a fast approximation method of solving a multiplication by solving an exponentiation that would have a close result?