int 型は 231 - 1 までの整数しか扱えない。 double 型はもう少し大きな整数まで扱えるが、 正確に扱える整数には限度がある。 それらを超えた計算を正確におこなうのが多倍長計算である。
ここでは、int 型の配列を用いて、 ひとつひとつの int 型変数には十進の一桁を格納するという、 手軽な方法を紹介する。 これで、100! や 1000! が正確に計算できるようになる。
a += b は a = a + b と同じである。 a -= b は a = a - b と同じである。 a *= b は a = a * b と同じである。 a /= b は a = a / b と同じである。 a %= b は a = a % b と同じである。
下のプログラム例では、 a[ ], b[ ], t[ ] という、三つの配列を用意した。 これで三つの巨大な数が扱える。 a[0] には一の桁を、 a[1] には十の桁を、 a[2] には百の桁を、 a[3] には千の桁を、……と格納する。 もしも 12345 を格納する場合、a[5] から先はすべて 0 にする。 （t[ ] は一時的に使うものである。）
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 200 /* 十進での桁数 */
#define M 50 /* テストの回数 */
int a[N];
int b[N];
int t[N]; /* 一時的に使うもの */
void set_a(int n);
void set_b(int n);
void check_a(void);
void print_a(void);
int get_a(void);
void add(void);
int main() {
int i, x, y;
{ /* この中カッコの中（乱数の種の設定）はわからなくてもよい */
unsigned seed = (unsigned)time(NULL); /* 現在時刻を取得して */
srand(seed); /* それを乱数の種に */
}
for (i = 0; i < M; i++) {
x = rand() % 32768; /* この「% 32768」は、コンパイラによっては */
y = rand() % 32768; /* もっと桁数の大きな乱数を返すため、つけた */
printf("%d + %d = ", x, y);
set_a(x); set_b(y); /* x, y を a[ ], b[ ] に格納する */
add(); check_a(); /* a[ ] に b[ ] を足し、結果をチェック */
print_a(); /* その結果を出力する */
if (get_a() != x + y) { /* その結果が x + y と異なっていたら */
printf("[error!]"); /* エラーメッセージを出力 */
}
printf("\n");
}
}
/* n を配列 a[ ] に格納 */
void set_a(int n) {
int i;
for (i = 0; i < N; i++) {
a[i] = n % 10; n /= 10;
}
}
/* n を配列 b[ ] に格納 */
void set_b(int n) {
int i;
for (i = 0; i < N; i++) {
b[i] = n % 10; n /= 10;
}
}
/* 配列 a[ ] に格納された数を出力 */
void print_a(void) {
int i;
for (i = N-1; i > 0 && a[i] == 0; i--) { /* 0 をスキップ */
; /* 「i > 0」に等号がつかない */
} /* のは 0 にも対応するため */
for ( ; i >= 0; i--) {
printf("%d", a[i]);
}
}
/* 配列 a[ ] に格納された数を返す */
int get_a(void) {
int i, r, power; /* r は返す値、power には 10 のベキがはいる */
r = 0; power = 1;
for (i = 0; i < N; i++) {
r += a[i] * power; power *= 10;
}
return r;
}
/* 配列 a[ ] に格納された数に配列 b[ ] に格納された数を足す */
void add(void) {
int i, k;
for (i = 0; i < N; i++) {
a[i] += b[i];
for (k = i; a[k] >= 10; k++) { /* くり上がりの処理 */
a[k] -= 10; a[k+1]++;
}
}
}
/* 配列 a[ ] をチェック */
void check_a(void) {
int i;
for (i = 0; i < N; i++) {
if (a[i] < 0 || a[i] > 9) { /* 負の数や 10 以上の数がはいっていないかチェック */
printf("[ERROR!]");
}
}
}
関数 set_a(), set_b(n) は、 その要領で 0 以上の整数 n を配列 a[ ], b[ ] に格納する。 （ポインタを知っていれば、このふたつを一つの関数にまとめることができる。）
関数 print_a() は、 配列 a[ ] に格納された数を画面に出力する。 000...00012345 が格納されている場合は 12345 と書く。 0 が格納されている場合は 0 と出力する。
関数 get_a() は、 配列 a[ ] に格納されている数を返す。 a[ ] にint 型に収まらない巨大な数が格納されていればこの関数は失敗に終わる。
関数 add() は、 配列 a[ ] に格納されている整数に、 配列 b[ ] に格納されている整数を加える関数である。 a[ ] に、b[ ] を一桁ずつ加えてゆく。 （ここでは、桁あふれはないものとした。 つまり、上のままでは、十進 N 桁に結果が収まらない場合、 配列の外にアクセスすることになり、本当は、まずい。 （修正は簡単である。））
関数 check_a() は、 配列 a[ ] に不適切な形で整数が格納されていないかチェックする。
main() では、乱数を二つ発生させ、 巨大数として足したものと普通に足したものとを比べることにより、 自作関数のチェックをしている。 くわしくはコメントを参照のこと。 0 から 32767 までの整数でのチェックだが、 これで間違いがなければ add() は正しく書けているとみてよいだろう。
上と同じことを、掛け算についておこなえ。 すなわち、配列 a[ ] に格納された数に、 配列 b[ ] に格納された数を掛ける関数、 void mul(void) を書け。 main() ではそのチェックをせよ。
一時的に、配列 t[ ] を使ってよいものとする。 つまり、a[ ] と b[ ] との積をいったん t[ ] に収め、 それを a[ ] にコピーする。
まずは t[ ] にすべて 0 を代入する。その後、 もしも a[i] が 6, b[j] が 7 だったとすると、 t[i+j] には 2 を、t[i+j+1] には 4 を、加えることになる。 足し算と比べて、それほどむずかしくはない。
以上を組み合わせると、階乗の計算ができる。
0! = 1 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 6! = 720 7! = 5040 8! = 40320 9! = 362880 10! = 3628800 11! = 39916800 12! = 479001600 13! = 6227020800
のようにして、100! まで出力させてみよ。
引き算は足し算をまねればできる。 ただし、答えが負になる場合、無限にくり下がりが続かないように。 その場合、答えは「補数」（のようなもの）になる。 たとえば、N が 8 で 12345 - 67890 を計算させると 99944455 になる。これを 100000000 から引いた 55545 に負号をつけた -55545 が正しい答えである。
割り算は、「引けるなら引く」の方針でできる。 たとえば 12345 を 67 で割る場合、1 からは 67 は引けない。 12 からも 67 は引けない。123 からは 67 が引ける。一つ引いて 56, だからもう引けない。次は 564 から 67 を引けるかぎり引いてゆく。 「564 を 67 で割るといくつが立つか？」と考えるのはむずかしいように思う。 一時的に数を格納する配列は必要なだけ作ってよい。