算法技术手册（原书第2 版）

30

｜

第

2

章

2.4.6 二次方的算法性能

现在考虑一个类似的问题：两个

n

位的整数相乘。例

2-4

展示了使用小学课堂上学过的

算法实现的乘法运算，其中

n

位数字的表示方法与之前的加法一样。

例

2-4

：

mult

乘法的

Java

实现

public static void mult (int[] n1, int[] n2, int[] result) {

int pos = result.length-1;

//

清除所有的值

for (int i = 0; i < result.length; i++) { result[i] = 0; }

for (int m = n1.length-1; m>=0; m--) {

int off = n1.length-1 - m;

for (int n = n2.length-1; n>=0; n--,off++) {

int prod = n1[m]*n2[n];

//

计算部分和，并且加上进位

result[pos-off] += prod % 10;

result[pos-off-1] += result[pos-off]/10 + prod/10;

result[pos-off] %= 10;

}

}

}

同样的，这里也会给出另外一种实现算法——

times

。这 种算法避免了取模运算的高费用，

并且忽略了当

n1[m]

等于

0

时不必要的内层计算（注意，这里并没有给出