7 ms·

Mathematicians Discover the Perfect Way to Multiply

194 points by WMCRUN 7y ago

_bxg1 7y ago
"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.
- wilg 7y ago
  That is amazing. Do we understand why aesthetics and intuition are so effective here? Or actually if that's even trueish in the general case?
  - _bxg1 7y ago
    It's a staple of higher-math and theoretical physics. I'm not the first one to note how eerie it all is: https://news.ycombinator.com/item?id=19588971 https://news.ycombinator.com/item?id=19588971
  - fj39dkf 7y ago
    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.
  - umanwizard 7y ago
    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.
    - _bxg1 7y ago
      The marvel isn't that we're good at picking up on patterns, it's that nature itself is so patterned to begin with.
      - umanwizard 7y ago
        Both are incredible! 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.
- incompatible 7y ago
  “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.
asimpletune 7y ago
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. This recent innovation is very exciting.
- gowld 7y ago
  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.
- thomasahle 7y ago
  Strassen is for multiplying matrices. This is integers.
  - ahelwer 7y ago
    They probably meant Schönhage–Strassen, which is for integers.
frosted-flakes 7y ago
This article was originally published in Quanta Magazine: https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/ https://www.quantamagazine.org/mathematicians-discover-the-p...
- pradn 7y ago
  Ah! I was wondering why the Wired graphic is similar to how Quanta does it.
davesque 7y ago
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.
- smadge 7y ago
  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.”
  - davesque 7y ago
    Thanks. I skimmed it but didn't read thoroughly.
- gumby 7y ago
  The article says that it may be the fastest: > At the end of February, a team of computer scientists at Aarhus University posted a paper [ https://arxiv.org/abs/1902.10935 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.
  - thomasahle 7y ago
    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.
- notfed 7y ago
  Even if n*log(n) turns out to be asymptotically "perfect", I'm curious what the constant overhead is. If it takes 15 minutes to multiply two 64-bit numbers, it might not be as "perfect".
yahrly 7y ago
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 ?
- ekimekim 7y ago
  https://hal.archives-ouvertes.fr/hal-02070778/document 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.
- thomasahle 7y ago
  It only really kicks in over the previous best at about n>2^2^4000 iirc. 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.
  - Someone 7y ago
    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”
    - klyrs 7y ago
      > This algorithm is proven to be O(n log n) only for numbers with at least 2^4096... No worries, all the rest runs in O(1)..
- vardump 7y ago
ecesena 7y ago
Paper: https://hal.archives-ouvertes.fr/hal-02070778/document https://hal.archives-ouvertes.fr/hal-02070778/document
gigatexal 7y ago
Might be fastest but it’s not intuitive for my way of thinking. Perhaps because I am so entrenched with the n^2 method.
- dreamcompiler 7y ago
  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.
  - lordnacho 7y ago
    Can you explain the connection with FFT? Or provide some useful links? Sounds really interesting.
    - sumnole 7y ago
      If you have CLRS 3rd edition, check out chapter 30
    - tprice7 7y ago
      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.
      - lordnacho 7y ago
        This bringing back control theory for me. Thanks.
    - dreamcompiler 7y ago
      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.
makapuf 7y ago
Preceding discussion on hackernews https://news.ycombinator.com/item?id=19474280 https://news.ycombinator.com/item?id=19474280
xiphias2 7y ago
,,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.
- wongarsu 7y ago
  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.
  - learc83 7y ago
    Writing game logic, I run into this all the time. Many classic algorithms were written when data locality wasn't nearly as big an issue. It's not just specific algorithms, but entire methods of problem solving. Graph traversal is so incredibly slow because of data locality.
- bigred100 7y ago
  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.
  - xiphias2 7y ago
    That's a great model that even helps running algorithms on FPGAs. Are there researchers working on finding the theoritical communicication limits of classical numerical problems?
  - 4thaccount 7y ago
    As if the algorithms behind numerical methods weren't hard enough, now we have to add parallelism :)
deleted 7y ago
[deleted]
lordnacho 7y ago
Strassen, perhaps unsurprisingly, also has something to say about matrix multiplication: https://en.wikipedia.org/wiki/Strassen_algorithm https://en.wikipedia.org/wiki/Strassen_algorithm "Strassen's algorithm works for any ring, such as plus/multiply..."
lamename 7y ago
Could someone explain how one can use the FFT in an algorithm for multiplication? I guess I would understand if I understood what FFT actually does 'under the hood', but I assumed fft itself required multiplication.
- jakeinspace 7y ago
  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.
- tprice7 7y ago
  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.
- adrianratnapala 7y ago
  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.
Lowkeyloki 7y ago
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!
NelsonMinar 7y ago
This is a lovely, readable summary of a relatively abstract mathematical result.
svat 7y ago
> 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. [1]: https://en.wikipedia.org/wiki/Karatsuba_algorithm https://en.wikipedia.org/wiki/Karatsuba_algorithm
- mabbo 7y ago
  You explain it really well. Thanks!
- 120bits 7y ago
  Thank you for the explanation. I was wondering how I can apply karatsuba's method to multiply for e.g. 103 X 1022.
  - svat 7y ago
    (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.
wppick 7y ago
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?
- clircle 7y ago
  b^n is b * ... * b, not b + ... + b.
- TheRealPomax 7y ago
  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 =) (https://www.reddit.com/r/3Blue1Brown/comments/a6mqsf/how_is_exponentiation_different_from_repeated/ 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)
kristianp 7y ago
"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...
- a1369209993 7y ago
  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.

194 points by WMCRUN 7y ago

"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.

wilg 7y ago
That is amazing. Do we understand why aesthetics and intuition are so effective here? Or actually if that's even trueish in the general case?
- _bxg1 7y ago
  It's a staple of higher-math and theoretical physics. I'm not the first one to note how eerie it all is: https://news.ycombinator.com/item?id=19588971 https://news.ycombinator.com/item?id=19588971
- fj39dkf 7y ago
  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.
- umanwizard 7y ago
  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.
  - _bxg1 7y ago
    The marvel isn't that we're good at picking up on patterns, it's that nature itself is so patterned to begin with.
    - umanwizard 7y ago
      Both are incredible! 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.
incompatible 7y ago
“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.

asimpletune 7y ago

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. This recent innovation is very exciting.

gowld 7y ago
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.
thomasahle 7y ago
Strassen is for multiplying matrices. This is integers.
- ahelwer 7y ago
  They probably meant Schönhage–Strassen, which is for integers.

frosted-flakes 7y ago

This article was originally published in Quanta Magazine: https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/ https://www.quantamagazine.org/mathematicians-discover-the-p...

pradn 7y ago
Ah! I was wondering why the Wired graphic is similar to how Quanta does it.

davesque 7y ago

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.

smadge 7y ago
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.”
- davesque 7y ago
  Thanks. I skimmed it but didn't read thoroughly.
gumby 7y ago
The article says that it may be the fastest: > At the end of February, a team of computer scientists at Aarhus University posted a paper [ https://arxiv.org/abs/1902.10935 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.
- thomasahle 7y ago
  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.
notfed 7y ago
Even if n*log(n) turns out to be asymptotically "perfect", I'm curious what the constant overhead is. If it takes 15 minutes to multiply two 64-bit numbers, it might not be as "perfect".

yahrly 7y ago

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 ?

ekimekim 7y ago
https://hal.archives-ouvertes.fr/hal-02070778/document 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.
thomasahle 7y ago
It only really kicks in over the previous best at about n>2^2^4000 iirc. 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.
- Someone 7y ago
  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”
  - klyrs 7y ago
    > This algorithm is proven to be O(n log n) only for numbers with at least 2^4096... No worries, all the rest runs in O(1)..
vardump 7y ago

ecesena 7y ago

Paper: https://hal.archives-ouvertes.fr/hal-02070778/document https://hal.archives-ouvertes.fr/hal-02070778/document

gigatexal 7y ago

Might be fastest but it’s not intuitive for my way of thinking. Perhaps because I am so entrenched with the n^2 method.

dreamcompiler 7y ago
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.
- lordnacho 7y ago
  Can you explain the connection with FFT? Or provide some useful links? Sounds really interesting.
  - sumnole 7y ago
    If you have CLRS 3rd edition, check out chapter 30
  - tprice7 7y ago
    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.
    - lordnacho 7y ago
      This bringing back control theory for me. Thanks.
  - dreamcompiler 7y ago
    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.

makapuf 7y ago

Preceding discussion on hackernews https://news.ycombinator.com/item?id=19474280 https://news.ycombinator.com/item?id=19474280

xiphias2 7y ago

,,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.

wongarsu 7y ago
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.
- learc83 7y ago
  Writing game logic, I run into this all the time. Many classic algorithms were written when data locality wasn't nearly as big an issue. It's not just specific algorithms, but entire methods of problem solving. Graph traversal is so incredibly slow because of data locality.
bigred100 7y ago
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.
- xiphias2 7y ago
  That's a great model that even helps running algorithms on FPGAs. Are there researchers working on finding the theoritical communicication limits of classical numerical problems?
- 4thaccount 7y ago
  As if the algorithms behind numerical methods weren't hard enough, now we have to add parallelism :)

deleted 7y ago

[deleted]

lordnacho 7y ago

Strassen, perhaps unsurprisingly, also has something to say about matrix multiplication: https://en.wikipedia.org/wiki/Strassen_algorithm https://en.wikipedia.org/wiki/Strassen_algorithm "Strassen's algorithm works for any ring, such as plus/multiply..."

lamename 7y ago

Could someone explain how one can use the FFT in an algorithm for multiplication? I guess I would understand if I understood what FFT actually does 'under the hood', but I assumed fft itself required multiplication.

jakeinspace 7y ago
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.
tprice7 7y ago
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.
adrianratnapala 7y ago
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.

Lowkeyloki 7y ago

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!

NelsonMinar 7y ago

This is a lovely, readable summary of a relatively abstract mathematical result.

svat 7y ago

> 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. [1]: https://en.wikipedia.org/wiki/Karatsuba_algorithm https://en.wikipedia.org/wiki/Karatsuba_algorithm

mabbo 7y ago
You explain it really well. Thanks!
120bits 7y ago
Thank you for the explanation. I was wondering how I can apply karatsuba's method to multiply for e.g. 103 X 1022.
- svat 7y ago
  (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.

wppick 7y ago

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?

clircle 7y ago
b^n is b * ... * b, not b + ... + b.
TheRealPomax 7y ago
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 =) (https://www.reddit.com/r/3Blue1Brown/comments/a6mqsf/how_is_exponentiation_different_from_repeated/ 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)

kristianp 7y ago

"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...

a1369209993 7y ago
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.