微博上外國人算乘法用的方法是什麼原理？

01-03

交叉數交叉點竟然能得到結果Σ( ?□?)?

這是什麼原理啊？
視頻鏈接：
http://m.weibo.cn/2141823055/3998696033720802?uicode=10000002featurecode=10000001mid=3998696582199043luicode=10000001_status_id=3998696033720802rid=9_0_8_2815982603415261250fromlog=100015356103423_forcelfid=100015356103423

驚呆，他們居然用卷積算乘法

中國或成最大輸家233

把多位數 $overline{a_na_{n-1}...a_0}$ 寫成多項式 $f(x) = sum_ka_k x^k$ 在x = 10時候的值，同樣另一個乘數可以寫成 $g(x)$ 在x = 10時的值，則f和g是對應序列的z變換，z變換的乘積的反變換是原序列的卷積

而這個方法就是用卷積定義來計算卷積：

$(a ast b)_m = sum_ka_kb_{m-k}$

計算完之後代回多項式中然後處理一下進位就可以算出乘法的結果了。

別看跟中國傳統的豎式比起來蠻蠢的，但是用卷積計算多位數乘法可以使用FFT優化卷積，將效率提升到O(nlogn)，所以如果你可以手算FFT的話你就可以快速算出兩個多位數的乘法（大霧）

=============================================================

這怎麼還火了……補充一點註解，如果不了解z變換之類的概念也不要緊，考慮f(x)和g(x)的多項式乘法就可以了， $a_k b_{m-k}$ 的這一項對應的是 $a_k x^k cdot b_{m-k} x^{m-k}$ ，後面對應的x的係數剛好是m，所以把所有這樣的項加起來就是 $x^m$ 前面的係數，這就是乘法與卷積相互轉換的原理。在乘得的多項式里代入 $x=10$ ，就可以得到乘法的結果。雖然手算FFT是個笑話，不過計算機的確可以通過FFT來快速得到兩個高精度數（比如幾百萬位乘以幾百萬位）的乘積，原理就是上面這樣。

原理跟我們列豎式難道不是一樣的嗎!

區別就在於我們中國學生背了99乘法表所以能夠省略掉個位數相乘的步驟!

既然大家都說豎式了，我來直接說明一下

$left(sum_{i=0}^n10^ia_i ight)left(sum_{i=0}^m10^ib_i ight)=sum_{i=0}^{n+m}left(10^isum_{j=0}^ia_jb_{i-j} ight)$