もう1つの例として、大きな数値の取り扱い方について考えてみたいと思います。
人間は理論上、どんな大きな値でも計算することができます。ただし暗算の名人でなければ、紙と鉛筆を使うでしょう。紙に書ききれないぐらい大きな値だとしても、もう1枚紙を持ってきて継ぎ足せば、計算することができますね。
しかし、コンピュータが1つの変数で扱える数値の大きさは、32ビットや64ビットで表現できるものまでです。そういった1つの変数で扱えない大きな数字を扱うことになった場合、コンピュータにどう処理させますか？
（1） 53 （2） 53
×72 ×72
―― ――
6 106
（3） 53 （4） 53
×72 ×72
―― ――
106 106
21 ＋371
―――
3816 |
| 図2 2けた同士の掛け算 |
それを考えるために、皆さんが実際に計算をするとき、どうやっているか思い出してみましょう。2けた同士の掛け算を解く方法を考えてみます。「53×72」を計算する場合、多くの人は紙に書いて計算するでしょう。1けた同士の掛け算を複数回実施し、出てきた積の足し算を行うことで答えが得られます（図2）。3けた同士の掛け算、4けた同士の掛け算も、時間はかかりますが同様に行えます。
コンピュータが1つの変数で扱えない大きな数字を扱う場合も、同じように考えます。1つの数字としては扱えなくても、上位何けた、下位何けたに分割し、複数の変数の組み合わせとすれば扱うことができます。下位×下位、下位×上位、上位×下位、上位×上位を計算し、足し合わせればいいのです（足し算時の繰り上がりには注意してください）。
以下は、このアルゴリズムをC言語とJavaで表したものです。
C言語
#include<stdio.h>
#define LIMIT 10
int keta_check();
void main(){
unsigned short ans[LIMIT],x[LIMIT],y[LIMIT];
int keta_x,keta_y;
unsigned int temp1,temp2;
int i,j;
for (i=0;i<LIMIT;i++){
x[i]=0;
y[i]=0;
ans[i]=0;
}
printf("4けたまでの2つの数を入力してください");
scanf("%d %d",&temp1,&temp2);
if(temp1 <1 || temp2<1){
printf("1より大きな自然数を入れてください");
return;
}
keta_x = keta_check(temp1);
keta_y = keta_check(temp2);
if(keta_x>4 || keta_y>4){
printf("5けた以上の値が入ってます");
return;
}
for(i=0;i<keta_x;i++){
x[i]=temp1%10;
temp1/=10;
}
for(i=0;i<keta_y;i++){
y[i]=temp2%10;
temp2/=10;
}
for(j=0;j<keta_y;j++){
for(i=0;i<keta_x;i++){
ans[i+j]+=x[i]*y[j];
if(keta_check(ans[i+j])>1){
ans[i+j+1]+=+ans[i+j]/10;
ans[i+j]%=10;
}
}
}
printf("答えは:");
for(i=0;i<LIMIT;i++){
printf("%d",ans[LIMIT-1-i]);
}
}
int keta_check(int a){
int i=0;
do{
a = a/10;
i++;
}while(a);
return (i);
} |
Java
import java.io.*;
public class multi {
public final static int LIMIT = 10;
public static void main(String[] args)throws Exception{
short[] ans,x,y;
int keta_x,keta_y;
short temp1,temp2;
int i,j;
BufferedReader str = new BufferedReader(new InputStreamReader(System.in), 1);
ans = new short[LIMIT];
x = new short[LIMIT];
y = new short[LIMIT];
for(i=0;i<LIMIT;i++){
x[i] = 0;
y[i] = 0;
ans[i] = 0;
}
System.out.println("4けたまでの自然数を入力してください");
temp1 = Short.parseShort(str.readLine());
System.out.println("4けたまでの自然数をもう1つ入力してください");
temp2 = Short.parseShort(str.readLine());
if(temp1 <1 || temp2<1){
System.out.println("1より大きな自然数を入れてください");
return;
}
keta_x = keta_check(temp1);
keta_y = keta_check(temp2);
if(keta_x>4 || keta_y>4){
System.out.println("5けた以上の値が入ってます");
return;
}
for(i=0;i<keta_x;i++){
x[i]=(short) (temp1%10);
temp1=(short) (temp1/10);
}
for(i=0;i<keta_y;i++){
y[i]=(short)(temp2%10);
temp2=(short)(temp2/10);
}
for(j=0;j<keta_y;j++){
for(i=0;i<keta_x;i++){
ans[i+j]+=x[i]*y[j];
if(keta_check(ans[i+j])>1){
ans[i+j+1]+=+ans[i+j]/10;
ans[i+j]%=10;
}
}
}
System.out.print("答えは:");
for(i=0;i<LIMIT;i++){
System.out.print(ans[LIMIT-1-i]);
}
}
public static int keta_check(int a){
int i=0;
do{
a /= 10;
i++;
}while(a!=0);
return(i);
}
} |
現在よく使われているPCは32ビットで動作するものがほとんどですが、今後64ビットになれば整数型で扱える数値の範囲が広がります。いま考えたような方法を使わなくても大きな値が計算できるようになることには、大きな意味があります。
4回の掛け算が1回でできるようになれば、性能は4倍になりますよね。逆に変数の型を間違えれば、本来の性能の4分の1しか発揮できないということにもなりかねません（実際にはコンパイラで最適化される場合もありますので、一概にはいえませんが）。
変数を宣言するときに小さ過ぎる値を使ってしまうと、あとあと計算で困ることがあるかもしれません。無駄な処理を省き、長く使ってもパフォーマンスが落ちにくい設計を心掛けましょう。
今回は、コンピュータで加減乗除、1つの変数では扱えないような大きなけたの掛け算をする場合の考え方を紹介しました。次回は数値や文字列の並べ替えや検索の仕方、それぞれの方法による処理速度の違いについて考えてみたいと思います。
鹿野恵祐
1978年夏、東京生まれ。東京電機大学理工学部経営工学科卒業後、システムインテグレータにてシステム設計・構築を担当。「長期にわたって使えるシステム」を模索する日々。最近は、コンピュータ以外にも視野を広げようといろいろチャレンジ中。西武ライオンズファン歴24年。好物は鶏の空揚げ。
ITmediaはアイティメディア株式会社の登録商標です。