アルゴリズムクイックリファレンス 第2版

28

■

2

章 アルゴリズムの数学

2.4.6

 二乗の性能

さて、サイズ

n

の

2

つの整数を掛け合わせるという同じような問題を考えよう。

例2-4は、小学校のアルゴリズム、

乗算

（

Multiplication

）の足し算と同じ

n

桁表現

を用いた実装を示す。

例

2-4

 

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;

}

}

}

この場合も、高コストなモジュロ演算子を置き換え、さらに、

n1[m]

が

0

のときに

一番奥の計算をスキップして効率を高めた

times

というもう

1

つのプログラムを書

くことができる（

times