http://www.paper.edu.cn
- 3 -
2.4 普乘算法的推导过程
为研究方便,不妨先分析 n=2 情况,并设相乘的两个多位数分别为:
1
0
10
im
i
i
i
Aa
=−
=
=
∑
和
1
0
10
jn
j
j
j
b
=−
=
=
∑
;则再设 P=A*B=P
m+n-1
P
m+n-2
P
m+n-3
……P
2
P
1
P
0
。其中
i
P 表示最后结果中
优先权值为 i 的数。显然,速算的关键是如何快速求出上述的
i
P 值。
普乘算法的理论基础是上述给出的乘法普推论,即先由乘法普推论求出
k
S ,之后再递
推求出
k
P ,直至求出结果。故本文把实现
k
P 的算法,称为普乘算法或 P-C 算法。
下面是 P-C 算法的简要推导,其中
i
S 就是乘法普 2 论中的
i
S ,L
i
=J
i
/10(取整数部分)。
普乘算法的推导:
0000 00
0 : ; /10; %10;step J S L J P J== =
11011 11
1: ; /10; %10;step J S L L J P J=+ = =
……
1
:;/10;%10;
iii ii ii
stepi J S L L J P J
−
=+ = = (5)
……
33433 33
( 3) : ; /10; %10;
mn mn mn mn mn mn mn
step m n J S L L J P J
+− +− +− +− +− +− +−
+− = + = =
223 22
(2): ; ;
mn mn mn mn mn
step m n J S L J
+− +− +− +− +−
+− = + = P
11 2
00 0
10 * 10 10 10 ;
mn mn
ij ij k
ij k
ij k
bab p
−− +−
+
== =
==
∑∑ ∑∑ ∑
m-1 n-1
ii
i=0 j=0
综上知:P=AB= a (6)
同理,对于多个多位数相乘也类似,可得出:
11
000
11
[] 10 []
iinin
wi m k m m m n k m m m n
in in
wi
wi k k
wi k k
ii
Ai Ai S P
==+++−=+++−
==
===
==
⎛⎞
===
⎜⎟
⎝⎠
∑∑∑
∏∏
LL LL
P= (7)
普乘算法可快速实现速算的原因有以下几点:
1)独立性:从普乘算法中的推导过程易知:
i
P 的求法都是独立进行的,例如在求两数
相乘时,求当前的
i
P 值,只需记录下上一步求
1i
P
的进位
1i
L
有关和当前要计算的
i
S 有关,
而与其它的都
k
P 、
k
J 、
k
L 的值都无任何关系。故只需按普乘算法中的步骤,从 i=0 开始逐
步代入到普乘算法的通式(5)中去计算,直至 i=m+n-2,就可以快速得到结果。
2)易分解与简单性:即该速算算法可将 n 个多位数相乘的求法分解成几组由 n 个简单
的 1 位数与 1 位数相乘的求法来计算,即将复杂的问题分解成几个简单的问题来解答,故可
以达到速算目的。
由乘法普推论知,假如是两个多位数相乘,则乘法普 2 论易知,
k
S 是由几组 1 位数与 1
位数相乘的结果相累加,而 1 位数与 1 位数相乘的最大结果不超过 9*9=81,故
k
S 的值很容
易快速地通过口算或心算得出,进而可以快速地求出相应的
k
P 值,从而达到可以快速实现