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

24

■

2

章 アルゴリズムの数学

2.4.4

 線形性能

問題によっては、他よりも明らかに多くの努力を要するものがある。子供でも

7

＋

5

が

12

になることがわかる。それでは、

37

＋

45

という問題は、どれだけより難

しくなるのだろうか。

例えば

2

つの

n

桁の数の加算、

a

n

−

1

…

a

0

＋

b

n

−

1

…

b

0

が、

n

＋

1

桁の数

c

n

…

c

0

にな

る計算の難しさはどの程度だろうか。この

加算アルゴリズム

に使われる基本演算は

次のようになる。

c

i

←

(a

i

＋

b

i

＋

carry

i

)

mod

10

carry

i

＋

1

←

{

もし

a

i

＋

b

i

＋

carry

i

≥

10

なら

1

そうでないなら

0

加算の

Java

実装の例を例2-2に示す。

n

桁の数が

int

値の配列で表現される。最

上位、すなわち左端の桁が添字

0

とする。本節の例では、配列要素の値は、

0

≦

d

≦

9

の整数値

d

とする。

例

2-2

 

add

の

Java

実装

public static void add(int[] n1, int[] n2, int[] sum) {

int position = n1.length-1;

int carry = 0;

while (position >= 0) {

int total = n1[position] + n2[position] + carry;

sum[position+1] = total % 10;

if (total > 9) { carry = 1; } else { carry = 0; }

position--;

}

sum[0] = carry; ...