看了一宿的 Trachtenberg 速算法，终于弄明白了。不得不承认，脑力不够😪
简单地说，这是一种低空间复杂度的线性算法。也就是说，占用的心理内存很少。看破了其实很简单。我们以一个三位数×两位数为例：
三位数×两位数
对于 m 位 × n 位：
这个公式其实暗含了整个算法的原理。但现在还不容易看出来。
验证一下：
m = 987
n = 65
as = m.digits
bs = n.digits
padding_as = as + Array.new(bs.size - 1, 0) # => [7, 8, 9, 0]
padding_bs = bs + Array.new(as.size - 1, 0) # => [5, 6, 0, 0]
d = 0
(0..(as.size + bs.size - 2)).each do |k|
memo = 0
(0..k).each do |i|
# puts "i: #{i}, j: #{k - i} --> #{padding_as[i]} * #{padding_bs[k - i]}"
memo += padding_as[i] * padding_bs[k - i]
end
memo *= (10 ** k)
d += memo
end
d # => 64155
这里的 a 也好，b 也好，都不超过 9 。所以，其乘积也不会过百。于是，我们定义两个函数：
-
t(a×b): the tens digit of a×b; -
u(a×b): the units digit of a×b;
这样，我们只需要从低位往高位依次计算，并把进位传递到高位就可以得到一个线性算法了。
记得加上「进位 c_i 」
以百位 (10^2) 为例，我们需要做的就是把所有下标加起来等于 2 的「个」位，以及所有下标加起来等于 2 - 1 的「十」位，还有上一位上传来的进位，加起来。
987×65
现在，我们的任务只剩下找到一种好记的记法，记住哪些取个位、哪些取十位，就大功告成了。
而 Trachtenberg 的天才就在于，他把算式横过来写了！还可以有这种骚操作😱 竖线表示取个位，斜线表示取十位，像一个滑动窗口一样滑过被乘数：
987×65
现在，当我们回过头去看那个通用公式，会发现：其实它已经揭示了所有的秘密。我们要做的是两件事：
- 找对一种方法，能够方便地记住「下标加起来等于 k 」的所有项乘积的「个」位之和；
- 找对一种方法，能够方便地记住「下标加起来等于 k - 1 」的所有项乘积的「十」位之和；
好吧，这其实就一件事：
竖线规则也好，斜线规则也好，都干的这一件事。
也就是说，不存在什么「竖线规则」「斜线规则」，我们只需要在头脑中想象好一组配对，先计算「个位和」，再计算「十位和」（作为下一组的进位）。
class Array
def l; self[0] end
def r; self[1] end
end
class Trachtenberg
def initialize(m, n)
m, n = n, m if m < n
as = m.digits
bs = n.digits
@as = Array.new(bs.size - 1, 0) + as + Array.new(bs.size, 0) # => [0, 7, 8, 9, 0, 0]
@bs = bs # => [5, 6]
@base = bs.size - 1
end
def tens(l, r = 1) l * r / 10 end
def units(l, r = 1) l * r % 10 end
def calculate
d = []
carry = 0
@as[@base..-1].each_with_index do |a, ia|
pairs = @as[ia...ia + @bs.size].zip(@bs.reverse)
sum = pairs.reduce(0) { |memo, tuple| memo + units(tuple.l, tuple.r) } + carry
d << units(sum)
carry = pairs.reduce(0) { |memo, tuple| memo + tens(tuple.l, tuple.r) } + tens(sum)
end
# d => [5, 5, 1, 4, 6]
d.reverse.reduce('') { |memo, digit| memo + digit.to_s }.to_i
end
end
t = Trachtenberg.new(987, 65)
t.calculate # => 64155
Trachtenberg 实在太聪明了，并不仅仅是因为他竟然能够找到这种图形化表示方法，而在于把这套速算系统分解开来，每个部分都很简单（包括「调整计算顺序以简化计算」其实也是一种很常见的思路），但是你就是想不到。也许就像竖式乘法之于横式乘法，他的心理寄存器远大于我们吧，所以才能把这些部件组合出如此精妙的算法来。
大家要想知道更多细节，去看 wiki 吧。
