啊…，看别人的回答，突然勾起了小时候被抓去练速算的回忆。
（虽然好像听了一节课之后就再也不去了）
那么我们先说「为什么从左向右」
一个很简单的原因——因为人脑的栈空间并不大。而「从右向左运算」就意味着在输出最后结果之前，我们需要把至少整个结果缓存在栈里…
首先我们要排除掉「算一位数乘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也能收敛了吧！（摔）
