由速算思路想到的大数相乘算法(一)

81 阅读 0 评论 54 点赞

我是靠谱客的博主英俊月亮，最近开发中收集的这篇文章主要介绍由速算思路想到的大数相乘算法(一)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

前几天逛网，发现一段视频很有意思：
http://www.6rooms.com/player.swf?vid=STJd2KkluxggOS7kwW7wuA
视频演示了二位数相乘及三位相乘的速算思路。
看不了视频的可以看下面这张图

自己整理了一下：

12*34=?
乘数：12
被乘数：34

先把乘数列出来,第i行列左起第i位数，列N次（N为乘数的位数）
第二行起每次右移一位
(1) (1)
(2) (2)

写入被乘数,按先列后行的方式
(1,3) (1,4)
(2,3) (2,4)

将（）内的数两乘
(1,3=3) (1,4=4)
(2,3=6) (2,4=8)

相加,注意进位
(1,3=3) (1,4=4)
        (2,3=6) (2,4=8)
-------------------------
     3      10       8
         .
-------------------------
     4       0       8

12*34=408

再看三位数乘法

123*456=?

第一步：
(1) (1) (1)
(2) (2) (2)
(3) (3) (3)

第二步：
(1,4) (1,5) (1,6)
(2,4) (2,5) (2,6)
(3,4) (3,5) (3,6)

第三步：
(1,4= 4) (1,5= 5) (1,6= 6)
(2,4= 8) (2,5=10) (2,6=12)
(3,4=12) (3,5=15) (3,6=18)

第四步：
(1,4= 4) (1,5= 5) (1,6= 6)
         (2,4= 8) (2,5=10) (2,6=12)
                  (3,4=12) (3,5=15) (3,6=18)
----------------------------------------------
      4       13       28       27       18
           .        .        .        .
----------------------------------------------
      5        6        0        8        8

123*456=56088

分析一下每一位的值是如何计算出来的，以下说的位都是从个位算起：
结果的第i位，是乘数的第i位乘以被乘数的1位，再加上乘数的第i-1位乘
以被乘数的第2位，一起加到乘数的第1位乘以被乘数的第i位。这样描述起
来有点不明白，画个图就很清楚了：
123*456的第3位：从乘数的第3位(1)起到第1位（3），按从右向左的方式
逐个乘以被乘数：
1*6+2*5+3*4=28

再把进位加上就可以了。
到这里，已经可以得出一个通用的计算方法，把结果逐位计算出来。

现在来看大数的相乘：先把乘数和被乘数按位存到数组。这个比较简单
在C++中，可以直接在IO中就把输入内容视为字串；在VB中，可以用
MID(CStr(K),i,1)来得到K的左起第I位。
假设已经把乘数和被乘数分别放入了数组A()和B()，现在再定义一个数组C（）
来存放结果。C（）的大小就是结果的位数，可以这样计算：
假设要计算A*B的结果有几位：
A*B=C
两边取10为底的对数：
Log10(A*B)=Log10(C)
Log10(C)就是位数了，Log10(A*B)=Log10(A)+Log10(B)，这样就到的公式：
A*B的位数是表达式（VB的）：
(Log(A) + Log(B)) / Log(10)

知道位数后可以定义结果数组C()了
然后按上面的方式进行计算每一位，这时要定义一个临时变量来保存进位，
由于数组中的每个数都是1位数，所以最大的结果就是9*9=81，进位变量最大
也不会超过9。

大数相乘，速度还可以