不会乘法表怎么做乘法？这个远古的算法竟然可以！

很多人都说背乘法表是他们教育经历中特别痛苦的一件事。问父母为什么要背乘法表，父母通常会说不背就不会做乘法。他们大错特错。

俄罗斯农夫乘法（Russian  peasant multiplication, RPM）就是在不了解大部分乘法表的情况下进行大数相乘的方法。

这是一种算术方法，尽管它叫这个名字，但也可能是埃及人，或者与农民没什么关系。

RPM 的起源尚不清楚。一份名为《莱因德纸草书》的古埃及卷轴记载了该算法的一个版本，一些历史学家提出（几乎没有说服力的）猜想，推测这种算法是如何从古埃及学者传播到辽阔的俄罗斯农夫那里的。

不论历史细节如何，RPM 都是一种有趣的算法。

手工实现 RPM

例如，计算 89 乘以 18。俄罗斯农夫乘法的过程如下。

首先，创建两个相邻的列。第一列称为半列（halving），第一项是 89。第二列是倍列（doubling），第一项是 18（表 1）。

表 1 半/倍表 第一部分

先填半列。半列的每一行是前一项的值除以 2，余数忽略不计。例如，89 除以 2 等于 44 余 1，所以把 44 写在半列的第二行（表 2）。 

表 2 半/倍表 第二部分

不断除以 2，每次都去掉余数，把结果写在下一行，直到最后得到 1。接着，44 除以 2 是 22，然后 22 的一半是 11，然后再一半（去掉余数）是 5，之后得到 2，最后是 1。将这些值写在半列，得到表 3。

表 3 半/倍表 第三部分

半列填完了。顾名思义，倍列的每一行是前一项的值乘以 2。18 乘以 2 等于 36， 因此倍列的第二行是 36（表 4）。

表 4 半/倍表 第四部分

按照同样的规则继续向倍列填值：前一项乘以 2。直到倍列与半列行数相同为止（表 5）。

表 5 半/倍表 第五部分

下一步，将半列值是偶数的整行删掉，结果得到表 6。 

表 6 半/倍表 第六部分

最后，将倍列所有项相加，结果是 1602。可以用计算器检查一下：89 乘以 18 也行于 1602。我们通过减半、翻倍和加法完成了乘法运算，这些都不需要背诵乘法表。为了理解为什么这种方法行得通，试着将倍列改写为 18 的倍数（表 7）。

表 7 半/倍表 第七部分

现在，倍列中有 1、2、4、8……直到 64，这些都是 2 的幂数，因此可以把它们写成  、  、  等。最终求和（即奇数行的倍列值相加）的时候，我们得到的是：

RPM 之所以有效取决于

仔细观察半列，就能理解为什么以上等式是正确的。我们把半列也写成 2 的幂 （表 8）。从最后一行开始，自下而上进行更容易些。记住，  是 1，  是 2。每一 行都乘以  ，其中半列值是奇数的行，还要加上  。可以看到这个表达式越来越像 上面的等式。到第一行，我们得到了一个表达式，简化后刚好就是  。

表 8 半/倍表 第八部分

设置半列的行号第一行是 0，最后一行是 6，可以看到半列值为奇数的行号是 0、 3、4、6。现在，请注意这个关键模式：这些行号恰好是 89 的表达式中的指数。这不是巧合；我们构造半列的方式意味着这个 2 的幂之和表达式中的指数，恰好总是奇数值的行号。把这些行对应的倍列值相加，其实就是 18 乘以 2 的幂之和，这个幂之和刚好等于 89，即 18 和 89。

其实，RPM 实际上是算法的算法。半列本身是一种算法实现，即寻找与第一个数相等的 2 的幂之和。2 的幂之和也称 89 的二进制展开（binary expansion）。二进制是只用 0 和 1 表示数字的一种方法，近几十年来它变得极其重要，因为计算机以二进制存储信息。我们可以把 89 写成二进制即 1011001，在第 0、3、4、6（从右开始 数）位上都有 1，这和半列的奇数行号一样，也和前面等式的指数一样。我们可以将二进制中的 1 和 0 解释为 2 的幂之和的系数。举个例子，二进制的 100 解释为

也就是 4。再比如，二进制的 1001 解释为

也就是 9。运行这个小算法可得到 89 的二进制展开值，然后我们就可以轻松地 运行整个算法来完成乘法过程。

用 Python 实现 RPM

用 Python 实现 RPM 比较简单。假设我们要把两个数 n1 和 n2 相乘，首先，打开 一个 Python 脚本，定义以下变量：

n1 = 89n2 = 18

接下来，开始处理半列。如上所述，半列的第一个值是其中一个乘数：

halving = [n1]

下一项是 halving[0]/2，去掉余数。在 Python 中，使用 math.floor()函数 实现。这个函数返回小于给定数字的最大整数。例如，半列的第二项计算如下：

import mathprint(math.floor(halving[0]/2))

在 Python 运行后，结果是 44。

以同样的方式对半列的每一行进行迭代，直至得到 1 结束：

while(min(halving) > 1):    halving.append(math.floor(min(halving)/2))

使用 append()方法将结果拼接起来。while 循环的每次迭代，是将上一个值的 1/2 附加到 halving 向量，使用 math.floor()函数忽略余数。

同样，对于倍列：从 18 开始，然后循环。这个循环的每次迭代，是将上一个值乘以 2 添加到倍列，当倍列的长度与半列的长度相等时停止：

doubling = [n2]while(len(doubling) < len(halving)):    doubling.append(max(doubling) * 2)

最后，将两个列放在一个名为 half_double 的数据框中：

import pandas as pdhalf_double = pd.DataFrame(zip(halving,doubling))

这里我们导入了 Python 模块 pandas。这个模块处理表很方便。在本例中，我们使用了 zip 命令，顾名思义，该命令将 having 和 doubling 链接起来，就像拉链将衣服的两边连接在一起一样。

这两组数字（having 和 doubling）一开始是独立的列表（list），打包后转换为一个 pandas 数据框，然后作为两个对齐列存储在表 5 那样的表中。

由于对齐并打包在一起，所以引用任意一行将返回完整的行，包括半列和倍列的元素，比如表 5 的第三行，是 22 和 72。对这些行进行引用和处理，删掉不想要的行，将表 5 转换为表 6。

现在，我们需要删除半列值是偶数的行。使用 Python 的 %（取模）运算符测试奇偶性，返回除法的余数。如果数字 x 是奇数，那么 x%2 等于 1。执行下面这行代码， 则只保留半列值是奇数的行：

half_double = half_double.loc[half_double[0]%2 == 1,:]

这里使用 pandas 模块的 loc 函数选择想要的行。使用 loc 时，在它后面的方 括号中指定我们想要选择的行和列。在方括号内按顺序指定行和列，用逗号分隔，格式是[行, 列]。例如，如果想要索引为 4 的行、索引为 1 的列，可以写为 half_double.loc[4,1]。

这个例子使用了一个逻辑表达式：半列值是奇数的所有 行。用 half_double[0]指定半列，半列的索引为 0；用 %2 == 1 指定奇数；在逗号 之后使用冒号指定所有列，这是得到所有列的一种快捷方式。

最后，对剩下的倍列进行简单加和：

answer = sum(half_double.loc[:,1])

这里我们又用到了 loc。在方括号内使用冒号指定所有行，逗号后面指定索引为 1 的倍列。注意，如果计算 18 × 89——即把 18 放在半列、89 放在倍列，可以更快更容易地完成。我鼓励你去尝试一下，看看有什么提升。一般来说，如果将较小的乘数放在半列、较大的乘数放在倍列，RPM 运行更快。

对于那些已经记住了乘法表的人来说，RPM 似乎毫无意义。但是除了它的历史魅力，RPM 还有几个值得学习的原因。

首先，RPM 表明，即使是像乘法这样枯燥的事情，也可以通过多种方法来实现，而且是创造性方法。为了某个事情学会一种算法并不意味着它就是唯一的或最好的算法——对新的、潜在的更好的方法要敞开心扉。

RPM 可能比较慢，但是它不需要消耗太多内存，因为它不要求掌握乘法表的大部分知识。有时候为了降低内存需求而牺牲一点速度是非常有用的，很多情况下我们设计和实现算法的时候，这种速度和内存的权衡是一个重要的考虑因素。

正如很多最佳算法那样，RPM 还体现了两种截然不同的理念之间的关系。二进制扩展好像看起来不过是猎奇，只有晶体管工程师感兴趣，对外行人或者专业程序员都没什么用处。

但是，RPM 展示了数字的二进制展开与一种便捷的乘法方法之间的深层联系，这个乘法方法只需要最低限度的乘法表知识。这便是你需要不断学习的另一个原因：你永远不知道什么时候一些看似无用的事实可能会成为强大算法的基础。

▼

除了俄罗斯农夫乘法，还有一些远古起源的算法，比如欧几里得算法、来自日本的生成幻方的算法等，如果大家想要继续了解的话，可以阅读《算法深潜：勇敢者的 Python 探险》一书。

这是一本内容广泛的 Python 算法书。你将看到很多很有意思的算法，包括：搜索、排序和最优化算法；以人为本的算法，帮助人们确定如何接球；先进的高级算法，比如机器学习和人工智能相关算法；以及古代文明时期的算法，比如数字相乘、寻找最大公约数以及幻方生成算法。

本书将带你学习：

◎生成 Voronoi 图，用于各种几何应用

◎使用算法构建聊天机器人、赢得棋类比赛、解决数独谜题

◎编写梯度上升和下降算法的代码，求解函数的最大值和最小值

◎使用模拟退火算法实现全局最优化

◎构建一个预测个人幸福的决策树

◎使用算法进行代码调试、收益最大化以及随机数生成

◎衡量算法的效率和速度

此外，本书还探索在纯数学中有用的算法，并学习如何基于数学思想改进算法。

跟着本书边做边学，你将了解当今许多超强算法的烦琐细节，包括如何在 Python 3 中编程实现这些算法，以及如何衡量和优化算法性能。

扫码了解本书详情