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.
the past 12 years of algorithm optimizations remove a fator of log(log(n)) from Strassen -- which means multiplying 1million bit numbers is 20x faster, ignoring constant factors and cost of cache misses. Constant factors and hardware architecture are still hugely important in choosing the best practical implementations for a problem.
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?
Update: Apparently, the article actually says that the approach is not perfect.
From the article: “Harvey and van der Hoeven’s algorithm proves that multiplication can be done in n × log n steps. However, it doesn’t prove that there’s no faster way to do it. Establishing that this is the best possible approach is much more difficult.”
> At the end of February, a team of computer scientists at Aarhus University posted a paper [ https://arxiv.org/abs/1902.10935 ] arguing that if another unproven conjecture is also true, this is indeed the fastest way multiplication can be done.
It's a really great paper.
It is a bit funny though to state it as giving more confidence to the multiplication lower bound, since multiplication has clearly been studied a lot more than network coding. So it makes more sense to think of it as a new possible attack vector to prove the lower bound, if that makes sense.
From this article written by the author [0], the overhead is very high. So I don't think you'll be seeing this implemented in your CPU any time soon. The usefulness seems to be that (1) it's a cool new piece of theory and (2) it's significant if you're doing computational work on ridiculously large numbers, like massive primes or something. Gaps between theoretically optimal and practically optimal algorithms are extremely common.
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 ?
https://hal.archives-ouvertes.fr/hal-02070778/document is the paper, which contains the closest thing to an implementation that I believe exists, and the answer for n is 'so large it would never fit in memory'. This is an important result mathematically, not something intended for practical use.
Not that it matters, but the constant used in the paper is 4096, not 4000. This algorithm is proven to be O(n log n) only for numbers with at least 2^4096 ≪ 10^1200 bits.
For comparison, we estimate there are 10^80 or so atoms in the known universe, so we would need quite a bit of progress in physics to even store one such number; this clearly is theoretical computer science.
On the plus side, they didn’t set out to minimize that constant, and think it can easily [1] be decreased significantly.
[1] ‘easily’ in the mathematical sense of “we think everybody who understands this paper and is willing to do potentially a lot of hard work will be able to pull it of”
This is what bothers me when someone uses Core i7 for performance comparisons: it covers a range of CPUs since 2008. Even saying "modern x86" would be more specific.
Multiplication using FFTs was one of the most mind-blowing things I encountered in my professional career. It involved realizing that third-grade multiplication is in fact polynomial convolution, and in the frequency domain that just becomes coefficient-wise multiplication.
The Karatsuba method is almost as cool and more practical for smallish numbers.
I gave a quasi-explanation in response to lamename's comment. If you want some search queries, learn what convolution is, then observe the connection between discrete convolution and polynomial multiplication, then learn about the convolution theorem.
If you know what an FFT is you know that it's very often used for signal processing. You probably also know that convolution in the time domain is the same as multiplication in the frequency domain, and vice-versa.
So now imagine a multiplication of two numbers, say 12345 * 67890. Imagine each number is a signal where the digits are samples. Multiplying like you were taught in third grade is effectively convolving one signal by the other.[0] Do this with pen and paper to see it clearly.
So if we call normal third-grade multiplication "time domain convolution," we can imagine converting both signals (both numbers) into the "frequency" domain with two applications of the FFT, then multiplying their frequency domain samples component-wise (which is much faster than convolution) and then taking an inverse FFT of the result. That's the algorithm in a nutshell.
It would buy you nothing on the numbers above because they're much too small. But for numbers with thousands of digits, it's a big speedup from O[n^2] to roughly O[nlogn].
[0] I'm oversimplifying. It's actually polynomial convolution and you have to do carries. That's slightly harder than signal convolution, but the idea is the same.
,,Hardware changes with the times, but best-in-class algorithms are eternal''
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.
Also traditionally steps of computations are counted for finding the best algorithm, but today the bottleneck for many problems is memory bandwidth. An algorithm that used to be best-in-class can become quite bad by just changing the ratio of CPU speed to memory speed.
I saw Jack Dongarra say that plain parallelism is now old and the thing is “communication avoidance”. Also made the point (relevant to your quotation) that changing hardware means redoing the algorithms every ten years to exploit it.
But 100x is just a constant factor. What bearing does it have on the asymptotic complexity of the algorithm? (Or to put it differently: It may very well work in practice, but how does it work in theory?)
If you want to go even further into the details (caching/RAM/Swap), you really get closer to the fact that the communication density between computations is what really matters, and n steps in the Turing machine runs in n*log(n) time in reality.
Just a correction: the Random Access Machine needs n*log(n) time, the Turing machine doesn't, as bandwidth is not a problem for the caching layers for sigle threaded execution, just the random access latency.
FFT requires (matrix) multiplication, but I assume it's only being used with relatively small chunks of the input numbers, which would be billions of digits long. This algorithm is not optimal for multiplying 3x4.
I haven't studied the Schönhage–Strassen algorithm closely so take this with a grain of salt. But I think I can give you at least a vague, simplified sense of how the FFT is relevant.
Multiplying polynomials is the same as convolving their coefficients, which is the same as multiplying the Fourier transforms of their coefficients (this is the convolution theorem), which can be done efficiently with the FFT. Now a base-10 number like 971 can be represented as the polynomial 9x^2 + 7x + 1 evaluated at x = 10. So multiplying base-10 numbers (or base-whatever for that matter) can sort of be seen as a special case of multiplying polynomials (plus a step afterward for carrying the digits), which can be done with the FFT.
Discrete fourier transforms have always been a way of doing fast polynomial multiplication -- which is also called convolution. That is we can do
(a0 + a1^z + a2*z^2...) * (b0 + b1^z + b2*z^2...)
As
fa = DFT([a0, a1, a2...]) # O(N log N)
fa = DFT([b0, b1, b2...]) # O(N log N)
fab = element-by-element multiply fa by fb # O(N)
return InverseDFT(fab) # O(N log N)
Now this is well established if we are literally doing a convolution of two sequences of complex numbers. But this is different from integer quite multiplication because:
1. Polynomial multiplication doesn't have carries.
2. It does inexact arithmetic on complex-numbers, we want exact results on integer digits.
I am guessing (2) is solved by getting modulo-arithmetic do the same algebraic gymnastics that make the FFT work.
Also I didn't think any of this was new -- I vaguely remember reading about fast convolutions using discrete algebras in old textbooks from the '70s. Maybe the hard thing was to do it in a way that leaves enough information left over to do the carries.
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!
"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"
It is just nuts that this kind of reasoning works out reliably.
It is pretty weird. I don't think there's a simple, empirical answer available. But if you would like to read more about incredible mathematical intuition and elegance, give the book Love and Math a read.
The human brain is an incredibly powerful unconscious pattern recognition device. The conscious mind is unaware of most of this processing.
For chess positions where there is no tactic that gives a clear advantage, the best move is determined by subtle positional/strategic considerations. It's interesting that often, top players will all agree what the best move is, but be incapable of explaining why except in very vague terms. It just "feels right".
I haven't read about computer chess in a while so I'm not sure if this is still the case, but at least for several years after it became impossible for a human to beat a computer, a human+computer team was still much stronger than a computer alone, because of this intuitive strategic/positional ability that computers lack.
I guess to explain my comment a bit further: I conjecture (as a pure layman) that a similar process is going on when a chess grandmaster says "I played Nf7 because it looked natural" as when a mathematician says "I expect this statement to be true for aesthetic/intuitive/moral reasons".
I think in this case the mathematician's unconscious mind has correctly identified some pattern that his or her conscious mind is unable to access.
Just like I can't really explain why I know my dad's face is his, and not that of some other man of similar race, age, and build.
“We use [the fast Fourier transform] in a much more violent way, use it several times instead of a single time, and replace even more multiplications with additions and subtractions,”
The algorithm itself doesn't seem particularly aesthetic.
> 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.
Karatsuba's method is beautiful and actually quite simple to explain.
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).
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.
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.
(Was hoping someone else may answer your question, but as it appears that no one has…)
Firstly, just in case it wasn't clear already, note that the algorithm is not intended for mental or manual arithmetic; its gains become apparent only when multiplying very large numbers (which is why I used 200 digits as an example). In particular, it wouldn't make sense to use it other than in cases where an addition and two subtractions are together faster than one multiplication at least — e.g. it wouldn't make sense to use it for numbers that can fit in a couple of machine words (say about 128 bits, or about 40 digits). If using it to multiply numbers by hand, I might use it for multiplying two 10-digit numbers but not anything smaller.
So assuming you understand all that and are asking about the 103 * 1022 example just to see concretely what the idea is, then read on. With 1022 being a 4-digit number, we can take X=100, and write 103 as aX+b with a=1 and b=3, and similarly 1022 as cX+d with c=10 and d=22. Then just compute a+b, c+d, and the three products ac, bd, and (a+b)(c+d):
a b a+b
1 03 4
10 22 32
c d c+d
ac bd (a+b)(c+d)
10 66 128
(Each number in the last row above was computed by multiplying the two numbers directly above it.)
Finally it only remains to compute (ad+bc) as a subtraction (here's where the savings come from; we don't have to multiply a with d, nor b with c — though in this example they'd be quite trivial anyway):
52 (a+b)(c+d)-ac-bd = 128-66-10
So we have the three quantities ac=10, (ad+bc)=52, and bd=66, giving the product to be (ac)X^2 + (ad+bc)X + bd (recall that X=100), which is 105266.
Again, it's quite pointless to use this for such tiny examples, and in fact we haven't even used the recursive nature of the algorithm. If you write some code to multiply large integers (implementing the method), you can appreciate it better.
Karatsuba’s algorithm is a shining example of creative applications of simple concepts.
I used to teach math to gifted elementary school students and used some problems from Japanese exams for the talented. I think the creativity and complexity of thought required to come up with this algorithm is about the same as some solutions to a harder problem in those exams. (The creativity required to solve them is significantly more than for American Math Competition, which typically involves difficult but quite conventional thinking.) [1]
More countries should adopt these Japanese-style problems in their gifted education as well as simpler versions for normal students. They are a great training ground for creative problem solving, which has become increasingly essential for successful careers in most fields.
PS. Hong Kong holds annual creative math problem solving competition for primary and secondary school students:
Interesting; I thought that a common criticism of Japanese-style education was that it's based to a large extent on rote memorization, whereas the West tends to focus more on concepts and creative thinking. Can you speak to that? Is the conventional wisdom wrong, or am I just wrong about what the conventional wisdom is?
One anecdote: My North American math education seemed to focus on rote memorization, with little creative thinking at all. Did you have a different experience? Not sure how they teach math in Japan though.
Not necessarily related (and avoiding the attached political junk)—
here in Ontario (Canada), the current government as ... strongly advocated... for going back to the "good old days" of rote memorization for the math curriculum versus modern discovery math methodology—ie: problem solving and creative thinking.
I was not getting into the political junk, as I said. Only pointing out that there are pillars of thought in NA who think that rote memorization as the sole method for learning mathematics was “the good old days” and is the only worthy method (with a practical example).
I do not know much about Japanese education system in general (I used translated version of the problems) but from what I observe in their challenge math problems used for admission into selective schools and creative output in other industries like popular mangas, the culture clearly values creativity.
The emphasis on skill mastery is most likely there and popularized in the US and globally by Kumon which might skew the perception somewhat.
The component which I am unsure if they emphasize enough is the understanding of math concepts, which is possibly a strength of American math education relative to Asia from what I see from textbooks for training American teachers.
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?
Except it's not, because exponentiation is not something reserved for integers. Just because you can write out b^4 as b * b * b * b doesn't mean that "that must be the rule". How would that rule even begin to explain how to calculate b^2/3 or b^π?
It's a cute little rule to use in middle school, when you get your very first glimpse at exponentiation, but it's also incredibly wrong if you try to actually use it with the rational, real, or complex numbers =)
"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."
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 don't know of a architechure that actually does this, but I suspect they're comparing a N->N->N truncating multiply with a N->N->N+1 addition that sets the carry flag. In addition to forcing the compiler to reorder test-fiddle-branch sequences in a potentially suboptimal way, you'd also introduce speculation hazards for any instructions that depend on the flags.
I'd be interested to see any hardware where that's enough to make addition slower, though, since usually you can make up for it by dumping a extra (very cheap) adder into the execution system.
71 comments
[ 6.4 ms ] story [ 152 ms ] threadThis recent innovation is very exciting.
Update: Apparently, the article actually says that the approach is not perfect.
> At the end of February, a team of computer scientists at Aarhus University posted a paper [ https://arxiv.org/abs/1902.10935 ] arguing that if another unproven conjecture is also true, this is indeed the fastest way multiplication can be done.
If it takes 15 minutes to multiply two 64-bit numbers, it might not be as "perfect".
[0]: https://theconversation.com/weve-found-a-quicker-way-to-mult...
This is a theoretical paper, but it is possible that some of the new fourier transform ideas can be used by libgmp down the line.
For comparison, we estimate there are 10^80 or so atoms in the known universe, so we would need quite a bit of progress in physics to even store one such number; this clearly is theoretical computer science.
On the plus side, they didn’t set out to minimize that constant, and think it can easily [1] be decreased significantly.
[1] ‘easily’ in the mathematical sense of “we think everybody who understands this paper and is willing to do potentially a lot of hard work will be able to pull it of”
No worries, all the rest runs in O(1)..
The Karatsuba method is almost as cool and more practical for smallish numbers.
So now imagine a multiplication of two numbers, say 12345 * 67890. Imagine each number is a signal where the digits are samples. Multiplying like you were taught in third grade is effectively convolving one signal by the other.[0] Do this with pen and paper to see it clearly.
So if we call normal third-grade multiplication "time domain convolution," we can imagine converting both signals (both numbers) into the "frequency" domain with two applications of the FFT, then multiplying their frequency domain samples component-wise (which is much faster than convolution) and then taking an inverse FFT of the result. That's the algorithm in a nutshell.
It would buy you nothing on the numbers above because they're much too small. But for numbers with thousands of digits, it's a big speedup from O[n^2] to roughly O[nlogn].
[0] I'm oversimplifying. It's actually polynomial convolution and you have to do carries. That's slightly harder than signal convolution, but the idea is the same.
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.
It's not just specific algorithms, but entire methods of problem solving. Graph traversal is so incredibly slow because of data locality.
Are there researchers working on finding the theoritical communicication limits of classical numerical problems?
https://en.wikipedia.org/wiki/Strassen_algorithm
"Strassen's algorithm works for any ring, such as plus/multiply..."
I guess I would understand if I understood what FFT actually does 'under the hood', but I assumed fft itself required multiplication.
Multiplying polynomials is the same as convolving their coefficients, which is the same as multiplying the Fourier transforms of their coefficients (this is the convolution theorem), which can be done efficiently with the FFT. Now a base-10 number like 971 can be represented as the polynomial 9x^2 + 7x + 1 evaluated at x = 10. So multiplying base-10 numbers (or base-whatever for that matter) can sort of be seen as a special case of multiplying polynomials (plus a step afterward for carrying the digits), which can be done with the FFT.
1. Polynomial multiplication doesn't have carries.
2. It does inexact arithmetic on complex-numbers, we want exact results on integer digits.
I am guessing (2) is solved by getting modulo-arithmetic do the same algebraic gymnastics that make the FFT work.
Also I didn't think any of this was new -- I vaguely remember reading about fast convolutions using discrete algebras in old textbooks from the '70s. Maybe the hard thing was to do it in a way that leaves enough information left over to do the carries.
It is just nuts that this kind of reasoning works out reliably.
For chess positions where there is no tactic that gives a clear advantage, the best move is determined by subtle positional/strategic considerations. It's interesting that often, top players will all agree what the best move is, but be incapable of explaining why except in very vague terms. It just "feels right".
I haven't read about computer chess in a while so I'm not sure if this is still the case, but at least for several years after it became impossible for a human to beat a computer, a human+computer team was still much stronger than a computer alone, because of this intuitive strategic/positional ability that computers lack.
I guess to explain my comment a bit further: I conjecture (as a pure layman) that a similar process is going on when a chess grandmaster says "I played Nf7 because it looked natural" as when a mathematician says "I expect this statement to be true for aesthetic/intuitive/moral reasons".
I think in this case the mathematician's unconscious mind has correctly identified some pattern that his or her conscious mind is unable to access.
Just like I can't really explain why I know my dad's face is his, and not that of some other man of similar race, age, and build.
The algorithm itself doesn't seem particularly aesthetic.
Karatsuba's method is beautiful and actually quite simple to explain.
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).
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.
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.
[1]: https://en.wikipedia.org/wiki/Karatsuba_algorithm
Firstly, just in case it wasn't clear already, note that the algorithm is not intended for mental or manual arithmetic; its gains become apparent only when multiplying very large numbers (which is why I used 200 digits as an example). In particular, it wouldn't make sense to use it other than in cases where an addition and two subtractions are together faster than one multiplication at least — e.g. it wouldn't make sense to use it for numbers that can fit in a couple of machine words (say about 128 bits, or about 40 digits). If using it to multiply numbers by hand, I might use it for multiplying two 10-digit numbers but not anything smaller.
So assuming you understand all that and are asking about the 103 * 1022 example just to see concretely what the idea is, then read on. With 1022 being a 4-digit number, we can take X=100, and write 103 as aX+b with a=1 and b=3, and similarly 1022 as cX+d with c=10 and d=22. Then just compute a+b, c+d, and the three products ac, bd, and (a+b)(c+d):
(Each number in the last row above was computed by multiplying the two numbers directly above it.)Finally it only remains to compute (ad+bc) as a subtraction (here's where the savings come from; we don't have to multiply a with d, nor b with c — though in this example they'd be quite trivial anyway):
So we have the three quantities ac=10, (ad+bc)=52, and bd=66, giving the product to be (ac)X^2 + (ad+bc)X + bd (recall that X=100), which is 105266.Again, it's quite pointless to use this for such tiny examples, and in fact we haven't even used the recursive nature of the algorithm. If you write some code to multiply large integers (implementing the method), you can appreciate it better.
I used to teach math to gifted elementary school students and used some problems from Japanese exams for the talented. I think the creativity and complexity of thought required to come up with this algorithm is about the same as some solutions to a harder problem in those exams. (The creativity required to solve them is significantly more than for American Math Competition, which typically involves difficult but quite conventional thinking.) [1]
More countries should adopt these Japanese-style problems in their gifted education as well as simpler versions for normal students. They are a great training ground for creative problem solving, which has become increasingly essential for successful careers in most fields.
PS. Hong Kong holds annual creative math problem solving competition for primary and secondary school students:
https://www.edb.gov.hk/en/curriculum-development/major-level...
There was also at least one international math competition for primary students in Asia-Pacific which focuses on creative math problem solving.
[1] AMC problems and solutions https://artofproblemsolving.com/wiki/index.php/AMC_Problems_...
here in Ontario (Canada), the current government as ... strongly advocated... for going back to the "good old days" of rote memorization for the math curriculum versus modern discovery math methodology—ie: problem solving and creative thinking.
There tend to be pillars of thought in NA.
The emphasis on skill mastery is most likely there and popularized in the US and globally by Kumon which might skew the perception somewhat.
The component which I am unsure if they emphasize enough is the understanding of math concepts, which is possibly a strength of American math education relative to Asia from what I see from textbooks for training American teachers.
I would appreciate more insight from others here.
It's a cute little rule to use in middle school, when you get your very first glimpse at exponentiation, but it's also incredibly wrong if you try to actually use it with the rational, real, or complex numbers =)
(https://www.reddit.com/r/3Blue1Brown/comments/a6mqsf/how_is_... has some more information in case you want to know what _would_ be a way to understand exponentiation for all numbers, not just integers)
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'd be interested to see any hardware where that's enough to make addition slower, though, since usually you can make up for it by dumping a extra (very cheap) adder into the execution system.