配列を利用して大きな整数の計算を可能にしてみよう。
普段使用している int 型は、実質long 型
つまり32ビットで表される範囲の整数である。この上限は(符号つきであれば)
2147483647 (約21億; 10桁)である。long long にしたとしても20桁
の数が上限である。
ではここで問題。111111111111111111111111111111 (30個の1)と 222222222222222222222222222222 (30個の2)を足すといくつだろう? 答えは簡単、333333333333333333333333333333 (30個の3)である。 算数を習っていれば分かる計算である。しかし、C言語でint型変数を使っても 30桁になる整数を扱うことができない。
では、完全に不可能かというとそうではない。人間が筆算をするときのよう
に計算させると何桁でも足し算できる。たとえば、25桁と25桁の二つの数値
3634654235432438943534512 と
2345132546578263422154652 を足す場合を考えよう。人間が足し算する場合、
1の位から1桁ずつ見ながら足し算して、足した結果が10以上になったら
10の位の数値を左隣の桁に繰り上げて行く。
111 111 1 (くり上がり)
3634654235432438943534512
+)2345132546578263422154652
------------------------------
5979786782012702365689164
この「筆算」のやり方は桁数が100桁になっても200桁になっても通用する。
数を表すのに、変数一つだけでなく、複数の変数を組み合わせて非常に大き な桁の数を扱えるようにして計算することを多倍長演算という。
たとえば、一つの変数が表す10進数を0〜9の一桁だけと決めておいて、 配列を使って何桁も表す。
char x[10]; /* 10個の char (8ビット) 変数 */
x[09] |
x[08] |
x[07] |
x[06] |
x[05] |
x[04] |
x[03] |
x[02] |
x[01] |
x[00] |
2 |
0 |
4 |
4 |
6 |
2 |
8 |
3 |
5 |
1 |
これを10進数 2044628351 だと思うことにする。各配列の要素は 全て char 型変数なので本来は -128 〜 -127 までの整数を表現できるが、 「全て10進数の1桁を表すのだ」、というルールの元に、0〜9の値以外は 代入しないようにする。
さて、2044628351 という数に、同じ10桁の数を足してみよう。
3173648074 を表す配列 y[] を用意して、x[]
の表す数と足してみよう。
「1の位から計算します!」
配列 x[ ] |
2 |
0 |
4 |
4 |
6 |
2 |
8 |
3 |
5 |
1 |
配列 y[ ] |
3 |
1 |
7 |
3 |
6 |
4 |
8 |
0 |
7 |
4 |
こたえ |
|
|
|
|
|
|
|
|
|
5 |
「1たす4は、5」
1の位が終わったら、10の位。
「1の位から計算します!」
配列 x[ ] |
2 |
0 |
4 |
4 |
6 |
2 |
8 |
3 |
5 |
1 |
配列 y[ ] |
3 |
1 |
7 |
3 |
6 |
4 |
8 |
0 |
7 |
4 |
こたえ |
|
|
|
|
|
|
|
|
12 |
5 |
「5たす7は、12」
となるところだが、筆算では足した結果が10以上になったら、 10の位を繰り上がりとして上に書いておく。多倍長演算でも、 全ての配列要素は「0〜9だけ!」というルールであることは変わらないので、 結果が10以上になったら1の位だけ配列要素に代入し、10の位を次の位に繰り越 す。「1の位」、「10の位」は、C言語のintの計算でいえばそれぞれ、 「10で割った余り」、「10で割った商」に相当する。
これを考慮して、「5たす7は、12」を繰り上げにしよう。
繰り上がり |
|
|
|
|
|
|
|
1 |
|
|
配列 x[ ] |
2 |
0 |
4 |
4 |
6 |
2 |
8 |
3 |
5 |
1 |
配列 y[ ] |
3 |
1 |
7 |
3 |
6 |
4 |
8 |
0 |
7 |
4 |
こたえ |
|
|
|
|
|
|
|
|
2 |
5 |
12 / 10 = 1 (intは切り捨て) 12 % 10 = 2 (剰余演算)
次の桁は、繰り上がりと x[], y[] を足す。
「100の位を計算します」
繰り上がり |
|
|
|
|
|
|
|
1 |
|
|
配列 x[ ] |
2 |
0 |
4 |
4 |
6 |
2 |
8 |
3 |
5 |
1 |
配列 y[ ] |
3 |
1 |
7 |
3 |
6 |
4 |
8 |
0 |
7 |
4 |
こたえ |
|
|
|
|
|
|
|
4 |
2 |
5 |
1たす3たす0は、4」
後は説明しなくても分かるだろう。1000の位の「8足す8」では、 16ではなく、10で割った余りの6を「こたえ」に、10で割って切り捨てた1を 「繰り上がり」にいれる。これをくり返すと計算結果は以下のようになる。
配列の添字 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
繰り上がり |
|
1 |
|
1 |
|
1 |
|
1 |
|
|
配列 x[ ] |
2 |
0 |
4 |
4 |
6 |
2 |
8 |
3 |
5 |
1 |
配列 y[ ] |
3 |
1 |
7 |
3 |
6 |
4 |
8 |
0 |
7 |
4 |
こたえ |
5 |
2 |
1 |
8 |
2 |
7 |
6 |
4 |
2 |
5 |
上記の「筆算」の手順を、C言語プログラムにするには、以下のような流れで とらえる。
まずは簡単のため、x と y の配列はあらかじめ数値をいれておく。
/* 2044628351 を要素10個の配列 x に。添字0から1の位 */
char x[] = {1, 5, 3, 8, 2, 6, 4, 4, 0, 2};
/* 3173648074 を要素10個の配列 y に。添字0から1の位 */
char y[] = {4, 7, 0, 8, 4, 6, 3, 7, 1, 3};
/* 答えを入れる配列 z[]; */
char z[10];
1の位、つまり添字0から足し算して行く。添字の繰り返しは0から9。
int i, sum; /* sum は各桁を足した結果一時保存 */
int kuriage=0; /* 繰り上げを保存 */
for (i=0; i<10; i++) {
sum = x[i]+y[i]+kuriage;
z[i] = sum%10; /* 10で割った余り == その桁の答 */
kuriage = sum/10; /* 10で割った商 == 繰り上げ */
}
上記のループで1の位から109の位まで筆算が終わる。
最後に、答となっている配列 z を添字の大きい方から
出力する。
for (i=9; i>=0; i--) {
printf("%d", z[i]);
}
puts(""); /* 改行のみ出力 */
以上のプログラムをまとめると以下のようになる。
#include <stdio.h>
int main()
{
/* 2044628351 を要素10個の配列 x に。添字0から1の位 */
char x[] = {1, 5, 3, 8, 2, 6, 4, 4, 0, 2};
/* 3173648074 を要素10個の配列 y に。添字0から1の位 */
char y[] = {4, 7, 0, 8, 4, 6, 3, 7, 1, 3};
/* 答えを入れる配列 z[]; */
char z[10];
int i, sum; /* sum は各桁を足した結果一時保存 */
int kuriage=0; /* 繰り上げを保存 */
for (i=0; i<10; i++) {
sum = x[i]+y[i]+kuriage;
z[i] = sum%10; /* 10で割った余り == その桁の答 */
kuriage = sum/10; /* 10で割った商 == 繰り上げ */
}
for (i=9; i>=0; i--) {
printf("%d", z[i]);
}
puts(""); /* 改行のみ出力 */
}
上記のプログラムでは、二つの大きな数値を書くのにプログラム中に 埋め込まなければならない。違う数値の足し算をしたかったら、 プログラムを書き換えてまたコンパイルし直さなければならず、 全く実用的でない。ユーザが入力した(巨大な)数値を多倍長配列 に読み取れるようにするにはどうしたらいいだろうか。