啊…，看別人的回答，突然勾起了小時候被抓去練速算的回憶。
（雖然好像聽了一節課之後就再也不去了）
那麽我們先說「為什麽從左向右」
一個很簡單的原因——因為人腦的棧空間並不大。而「從右向左運算」就意味著在輸出最後結果之前，我們需要把至少整個結果緩存在棧裏…
首先我們要排除掉「算一位數乘n位數再相加」的想法，而是進一步拆開。
像我們平時應該是這樣計算的對吧…
而我們現在要做的是。
啊，寫過高精度乘法的人可能比較容易理解吧……
或者說的奇怪一點——我們要先透過摺積運算 (3,4,5)\ast(1,2)=(3,10,13,10) 再最後考慮進位…
啊，當然，我不是想說用快速傅立葉變換求摺積可以實作高速的高精度乘法…（雖然好像確實可以）畢竟人腦跑FFT這事怎麽看也不現實…
我說的是，摺積是可以從左到右輸出的對吧…
當然，進位是個麻煩事…但是如果透過某種剪枝手段判定了後面的內容一定進多少位，那麽就可以把前面的內容「flush」出來…
還是上面的例子，我們有整數流(3,10,13,10),由計算位數就可以知道一個很粗糙的上界，就是流裏的每一個數碼都不超過81*2……那麽在13輸入之後就可以輸出3了……
如果我沒記錯的話，這應該就是我小時候學的所謂「速算」的基本原理了……而且如果我調查的資料沒錯的話，這也是市面上很多所謂「速演算法」的理論背景…
（說起來我依稀記得當時的老師似乎還在計算中做過分支預測和回滾？不過我也記不太清了…也可能只是在黑板上演示數據更新…）
不過，這樣一來，哪怕不是毒瘤命題人的我們也可以很容易構造出退化，使得流在較長的時間內一直不能夠「輸出」，從而卡棧…
比如說11111111111111*111111111……
摺積之後是(1,2,3,4,5,6,7,8,9,9,9,...,9,8,7,6,5,4,3,2,1)這樣的流……
那麽中間那一串9就註定都會壓在棧裏…畢竟你也不知道後面會不會突然出現一個進位然後一連串回溯上去…
所以我就一直說，速算比賽受限於選手精力，不能跑全覆蓋測試，那至少也請允許白箱構造退化……
就哪怕是允許速算選手之間互相hack也比這種random的毫不毒瘤的數據有意思（暴論）
用連naive的演算法都卡不住的數據可太無聊了！
另一方面，比較大名鼎鼎的史豐收演算法我也調查了一下…
看起來是這樣的一個情況…為了避免爆棧的問題，它稍微借助了一下外存——也就是筆算。
總之是這樣的一個「彎道超車」……
也就是說我們只考慮下一位的進位…而對於大於99的數的所謂「超前進位」，還是按照正常的方式標記下來等著最後進行處理。
也就是說，對於66666*55555,也即流(30 60 90 120 150 120 90 60 30)
輸入30,輸出3
輸入60,輸出6
輸入90,輸出9
輸入120,輸出2，並給上一位標記進位。
輸入150,輸出5，並給上一位標記進位。
輸入120,輸出2，並給上一位標記進位。
輸入90,輸出9
輸入60,輸出6
輸入30,輸出30
我們得到了（3，6，9+1，2+1，5+1，2，9，6，3，0），解決進位之後就是3703629630…
畢竟是所謂「動手動筆又動腦」的演算法嘛…所以這一步還是拉到了紙上……不過很禿的問題就是，對於比較大的多位計算，這一串進位操作本身就可能是完全退化的（如果堅持從左向右計算，按順序輸出的話…）
當然，這裏還是有最佳化空間的…比如說這個流裏面不會有（+4）以外的進位（畢竟只是五位乘五位，最多9*9*5=405，所謂的「超前進位」也只有4）…
那麽當你算到9+1的時候，就可以把前面的3和7輸出了…而3+1計算之後上一位的0也可以輸出…
這實際上可以進一步減少草稿紙的使用————但是一旦演算法退化就只能嚶嚶嚶了…
說句不好聽的…這個演算法除了「從左向右」之外，我沒看到什麽優勢…
本質上說，我們還是需要對每個位和每個位之間做一次乘法…更糟糕的，因為這丟人的進位順序，我們反而可能需要做更多的加法運算（但不可能更少）……（本質上講，乘法也變多了，因為這個演算法裏計算乘法的高位和計算乘法的個位是兩種不同的運算…）
當然，有人也許會問，那為什麽那些學速算的人算的那麽快？
啊，減少外存存取，用記憶體運算替代，固然是速算最基本的優勢了……（也就是說，少在紙上演算，在腦子裏進行大部份…）
但是另一方面…各種繁雜的口訣表，各種特判的退化情況……
像極了考場上瘋狂打表補corner case的卑微的我
再說被訓練了那麽久，就是最基本的五層摺積網絡和瞎寫的learning rate也能收斂了吧！（摔）
