Never thought 99 multiplication table was a unique arithmetic method in China. What method did western countries use to calculate product without 99 multiplication table? It turns out that many people in foreign countries are actually using convolutional multiplication. Here's a brief introduction to convolutional multiplication:
If the multi bit number is changed into the value of polynomial at x = 10 and the same multiplier can be written as the value at x = 10, then f and G are the product of Z-transform Z-transform of corresponding sequence, and the inverse transform is the convolution of original sequence.
The method we see at present is to use the definition of convolution to calculate convolution: after calculating convolution, the result is substituted into polynomial, and then carry out carry processing to calculate the result of multiplication. At first glance, it seems to be more complex than the traditional 99 multiplication in China, but when we use convolution to calculate the multiplication of multiple digits, we can use FFT to optimize our convolution, which will improve the efficiency to o (nlogn). So if we can manually calculate FFT, then any of us can quickly calculate the product of multiplication of two multiple digits.
Finally, I'd like to add that if we don't quite understand the concepts of Z-transform and so on, it doesn't matter. Considering that the polynomial multiplication of F (x) and G (x) can also work, we can see that the coefficient of X corresponding to the back is just m, so we can add all these formulas together to be the former coefficient, which is also a good conversion between multiplication and convolution The principle. The result of multiplication can be easily obtained by substituting it into the polynomial.
Although calculating FFT by hand is a very difficult challenge, in modern society, we can choose to use computers to get the product of two high-precision numbers (such as millions of bits multiplied by millions of bits) quickly through FFT. After the explanation is clear, the principle of convolution is the above. It can calculate the multiplication of many numbers quickly and accurately.