看了一宿的 Trachtenberg 速算法截歉，終于弄明白了胖腾。不得不承認(rèn)，腦力不夠??
簡單地說瘪松，這是一種低空間復(fù)雜度的線性算法胸嘁。也就是說，占用的心理內(nèi)存很少凉逛。看破了其實很簡單群井。我們以一個三位數(shù)×兩位數(shù)為例：
對于 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 。所以荐吉，其乘積也不會過百焙糟。于是，我們定義兩個函數(shù)：
-
t(a×b): the tens digit of a×b; -
u(a×b): the units digit of a×b;
這樣样屠，我們只需要從低位往高位依次計算穿撮，并把進(jìn)位傳遞到高位就可以得到一個線性算法了。
以百位 (10^2) 為例痪欲，我們需要做的就是把所有下標(biāo)加起來等于 2 的「個」位悦穿，以及所有下標(biāo)加起來等于 2 - 1 的「十」位，還有上一位上傳來的進(jìn)位业踢，加起來栗柒。
現(xiàn)在，我們的任務(wù)只剩下找到一種好記的記法知举，記住哪些取個位瞬沦、哪些取十位太伊，就大功告成了。
而 Trachtenberg 的天才就在于逛钻，他把算式橫過來寫了僚焦！還可以有這種騷操作?? 豎線表示取個位，斜線表示取十位绣的，像一個滑動窗口一樣滑過被乘數(shù)：
現(xiàn)在叠赐，當(dāng)我們回過頭去看那個通用公式，會發(fā)現(xiàn)：其實它已經(jīng)揭示了所有的秘密屡江。我們要做的是兩件事：
- 找對一種方法芭概，能夠方便地記住「下標(biāo)加起來等于 k 」的所有項乘積的「個」位之和；
- 找對一種方法惩嘉，能夠方便地記住「下標(biāo)加起來等于 k - 1 」的所有項乘積的「十」位之和罢洲；
好吧，這其實就一件事：
也就是說耸峭，不存在什么「豎線規(guī)則」「斜線規(guī)則」桩蓉，我們只需要在頭腦中想象好一組配對，先計算「個位和」劳闹，再計算「十位和」（作為下一組的進(jìn)位）院究。
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 實在太聰明了，并不僅僅是因為他竟然能夠找到這種圖形化表示方法本涕，而在于把這套速算系統(tǒng)分解開來业汰，每個部分都很簡單（包括「調(diào)整計算順序以簡化計算」其實也是一種很常見的思路），但是你就是想不到菩颖。也許就像豎式乘法之于橫式乘法样漆，他的心理寄存器遠(yuǎn)大于我們吧，所以才能把這些部件組合出如此精妙的算法來晦闰。
大家要想知道更多細(xì)節(jié)放祟，去看 wiki 吧。
