Mathematicians Discover the Perfect Way to Multiply
wired.com
wired.com
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.
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
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
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.
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?
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...
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.
This recent innovation is very exciting.
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.
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)..
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.
(a0 + a1^z + a2*z^2...) * (b0 + b1^z + b2*z^2...)
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)
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.
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.
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)