俄罗斯农民乘法

简介

在很久很久以前。。。人们是这样做乘法的。。。这是一种古老的乘法算法，但是在如今的计算机中却还能发现它的身影。它，就是以俄罗斯农民命名的乘法算法！

原文地址：http://mathforum.org/dr.math/faq/faq.peasant.html

 

规则：什么是俄罗斯农民乘法？我要怎么使用它？
原理：俄罗斯农民乘法的工作原理是什么？
联系：俄罗斯农民乘法是如何与二进制相关联的呢？

 

什么是俄罗斯农民乘法？我要怎么使用它？

 

我们绝大多数人学的都是这样做大数字乘法的：

 

          86
      x  57
      ------
        602
   + 4300
      ------
      4902

 

如果你懂得乘法算式，那么这种“长式相乘”的方法是快速和相对简单的。不过，还有许多其它的计算方法。其中之一通常被称之为俄罗斯农民算法。使用它时不需要你懂得乘法算式，你只需要将数字加倍，减半再进行合计。具体规则如下：

 

  * 把每一个数字分别写在列头。
  * 将头一列的数字加倍，将第二列的数字减半。
     如果在第二列的数字是奇数，将它除以二并把余数去掉。
  * 如果第二列的数字是偶数，将其所在行删除。
  * 继续加倍、减半和删除直到第二列的数字为1。
  * 将第一列中剩余的数字相加。于是就得出了根据原始数字计算出的结果。

 

让我们以计算57乘以86为例。
    把每一个数字分别写在列头。
        57     86
    将头一列的数字加倍，将第二列的数字减半。
        57     86
      114     43
    如果第二列的数字是偶数，将其所在行删除。
        57     86
      114     43
    继续加倍、减半和删除直到第二列的数字为1。
        57     86
      114     43
      228     21
      456     10
      912      5
      1824     2
      3648     1
    将第一列中剩余的数字相加。于是就得出了根据原始数字计算出的结果。
        57     86
      114     43
      228     21
      456     10
      912      5
      1824     2
  +  3648     1
      4902

 

真实的俄罗斯农民们可能会用好几碗的鹅卵石来记录他们加倍的数字，用来代替写在列里面的数字。（当然，他们或许不会对我们的例子里那么大的数字感兴趣，要知道四千多个鹅卵石可是很难操作的哟！）俄罗斯的农民们并不是唯一使用这种算法的人，在数千年之前古埃及人就已经发明了类似的方法，而同时在今天的计算机中仍然在使用与之相关的程序。

 

俄罗斯农民乘法的工作原理是什么？

 

让我们以计算9×8为例：

 

          9      8
        18      4
        36      2
        72      1

 

72是唯一一个留在左列里的数字，所以我们的答案就是72。请注意我们在其中一边乘以2，在另一边除以2，2 × 1/2 = 1，所以对最终结果并没有影响:

 

       9 * 8                         

       = 18 * 4                   

       = 36 * 2        

       = 72 * 1

 

我们刚才对数字进行了不同的组合，而对结果并没有影响。如果我们将8乘以9，我们应该得到同样的答案。那我们能用同样的方法来解释吗？

 

         8     9
       16     4
       32     2
    + 64     1
       72

 

当我们将9除以2，我们将余数去除因为9是一个奇数。由于我们“丢失”了一个，所以接下去的产生的每一行都会变得更小。让我们从第一行和第二行中寻找不同。

 

      8*9 - 16*4
      = 72 - 64
      = 8

 

我们可以重写个减法来计算总和：

 

8 * 9                             

= 16 * 4 + 8                 

因为我们的结果少了8,所以我们就必须在最后把8给加回去。我们可以把这种追加认为是恢复了1组8，就是在前面我们丢掉的余数1。在不同的问题里，我们有可能会恢复不同组的数字。

 

俄罗斯农民乘法是如何与二进制相关联的呢？

 

二进制是以2代替10来作为基数的进制。这就意味着在位数上我们要用2的次方来代替10的次方：代替个位、十位和百位，二进制有一位、二位和四位等等。例如，14在二进制里表示为1110：

 

       1110 (base 2)
       = 1 * 2^3 + 1 * 2^2 + 1 * 2^1 + 0 * 2^0
       = 8 + 4 + 2 + 0
       = 14

 

俄罗斯农民乘法能快速有效的将数字转换成二进制模式，将它们相乘，然后再转换回我们日常所使用的数字系统。这种关联两种进制的能力并不惊奇，因为二进制使用2作为基数，同时俄罗斯农民乘法使用2来相乘和相除。为了使这种关联更为清晰，让我们来研究一下12*13。

 

减半

 

你能够通过对数字进行重复的除以2并且留下余数来将其转换成二进制。让我们试一下12：

 

        12/2 = 6  余数 0
         6/2 = 3   余数 0
         3/2 = 1   余数 1
         1/2 = 0   余数 1

 

从下往上读取余数，我们得到了1100,所以12所对应的二进制数字为1100。

 

这种转换方法的工作原理是什么呢？让我们再一次试着用同样的方法将12减半。这一次，我们将把所有的数字都基于二进制（当然，数字2在二进制里头是10）。

 

            1100/10 = 110  余数 0
              110/10 =   11  余数 0
                11/10 =     1  余数 1
                  1/10 =     0  余数 1

 

将数字除以2然后再取其余数，最终我们所得到的就是基于二进制的数字。

 

关于数字12，到目前为止我们所得出的：

 

       12 = 1100 (base 2)
       = 1*2^3 + 1*2^2 + 0*2 + 0*1
       = 2^3 + 2^2
       = 8 + 4

 

通过反复的对12减半，我们就可以将其分解成2的次方。

 

因式分解

 

我们现在来试着将12乘以13。一种方法是使用长式相乘：

 

          13
       * 12
         ----
          26
     + 130
        -----
        156

 

注意我们通过将 2*13 和 10*13 相加来得出我们的最终结果。它的工作原理是因式分解：

 

       12 * 13
       = (2 + 10) * 13
       = 2*13 + 10*13

 

当然，我们能将12分解成任何我们想要的形式，并且仍然能得到正确的答案。现在让我们用前面所做的工作来将这个题目分解成2的次方：

 

       12 * 13
       = (4 + 8) * 13
       = (2^2 + 2^3) * 13
       = 2^2 * 13 + 2^3 * 13

 

如果我们能将 13 乘以 2^2 和 2^3，那我们就完成了。

 

加倍

 

重复的将一个数字乘以2的次方。让我们试试将13加倍：

 

       数字        累计相乘过程          2的次方
        13               13                         2^0
        26             13*2                       2^1
        52            13*2*2                    2^2
       104          13*2*2*2                 2^3

 

我们的图表告诉我们 2^2 * 13 + 2^3 * 13 = 52 + 104 = 156，所以 12 * 13 = 156，我们完成计算了。

 

把所有的一切放在一起

 

我们刚才通过重复的减半和相乘将12转成二进制模式，然后将其与13相乘。俄罗斯农民算法做得是同样的事情，但是它节省了很多的步骤，过程也更快。让我们结合我们加倍和减半的步骤来比较这两种方法的不同。

 

数字加倍     累计相乘过程     2的次方       数字减半        除以2         余数
    13                 13                      2^0               12               12/2 = 6         0
    26                13*2                   2^1                 6                 6/2 = 3         0
    52              13*2*2                 2^2                 3                 3/2 = 1         1
  104            13*2*2*2              2^3                 1                 1/2 = 0         1

 

加粗的列使用的是俄罗斯农民乘法。注意当余数列为0时，其所对应的俄罗斯乘法行要删去。

评论

10 楼 achun 2009-02-16  

很久没有见到这样的好文了

9 楼 linliangyi2007 2009-02-15  

很赞，典型的二元思维方式
大家仔细看看被除的数，那个就是10进制转二进制的算法了

8 楼 javakid 2009-02-13  

计算机学家，呵呵

7 楼 kangsg219 2009-02-13  

jessdy 写道

来个中国农民的   57*  86 ----   42  -------个位相乘6*7   40    -------十位相乘5*8  30   -------交叉相乘5*6+ 56   -------交叉相乘7*8-------- 4902

身为中国农民而自豪啊

6 楼 jessdy 2009-02-13  

来个中国农民的
   57
*  86
----
   42  -------个位相乘6*7 
40    -------十位相乘5*8
  30   -------交叉相乘5*6
+ 56   -------交叉相乘7*8
--------
4902

5 楼 magnesium 2009-02-12  

很好很强大

4 楼 beside 2009-02-11  

楼主太棒了！

3 楼 bimarcher 2009-02-11  

真是有意思的算法  楼主真棒。

2 楼 omett 2009-02-11  

俄罗斯算法厉害，但是您更厉害~~~~~~

1 楼 whaosoft 2009-02-11  

俄罗斯老坦儿 都那么厉害?????