■10進数で大きな桁数の計算を行う

10進数を配列で表現して、非常に大きな桁数の計算を行う方法を考えて見たいと思います


▼値の表現方法


大きな桁数の計算を行うために、値を配列で持たせるとします
一つの要素に10進数で2桁づつ値を格納し、それを配列として持つことにより大きな桁数を扱います


500 を表現する場合
ar[4]=00 ar[3]=00 ar[2]=00 ar[1]=05 ar[0]=00
注)c言語で実際のプログラムでは値の前に0をつけると8進数になってしまう

1234567890 を表現する場合
ar[4]=12 ar[3]=34 ar[2]=56 ar[1]=78 ar[0]=90

マイナス値の場合は配列の総ての要素がマイナスになると考えます
-1234567890 を表現する場合
ar[4]=-12 ar[3]=-34 ar[2]=-56 ar[1]=-78 ar[0]=-90




▼足し算を考える




足し算の桁の繰り上がりを考えると、上のパターンが考えられます
上のパターンをまとめてみると


@99より大きな値を見つけたら現在の要素から100を引き、上の要素に1を繰り上げる
A-99より小さな値を見つけたら現在の要素から-100を引き、上の要素に-1を繰り上げる
B全体が+であり、現在の要素が−である場合、上の要素から1を引き、現在の要素に100を足す
C全体がーであり、現在の要素が+である場合、上の要素から-1を引き、現在の要素に-100を足す


二つの配列の要素を足して、@からCの処理を添え字の小さい値から順に繰り返していけば足し算が出来ると考えられます。




▼引き算を考える


引き算は、引くほうの値の符号を反転させることにより足し算で代用できると考えられます

100-10 → 100+(-10)




▼かけ算を考える


かけ算は足し算を繰り返し行えば出来ますが、それでは時間が掛かりすぎます
そこで手計算で計算するのと同じ方法で計算してみます

1020×0523の場合




これと同じことをプログラムで記述すれば計算できるはずです




▼割り算を考える


割り算は被除数から法を繰り返し引けば計算できますが、それでは時間が掛かりすぎます
そこで、シフトを使って計算してみます





これと同じことをプログラムで記述すれば計算できるはずです




■上記の計算方法からイメージして作成したプログラム

#include <stdio.h>

//  ar+ar2=ar3
void add(const short*ar,const short*ar2,short*ar3,const int size);
//  ar-ar2=ar3
void sub(const short*ar,short*ar2,short*ar3,const int size);
//  ar*ar2=ar3
void mul(const short*ar,const short*ar2,short*ar3,int size);
//  ar/ar2=ar3...ar
void div(short*ar,short*ar2,short*ar3,const int size);
//  printf(ar)
void ar_print(short*ar,const int size);
//配列を固定小数点型として画面表示する ar[size-1].ar[size-2]~ar[low]
void dp_print(short*ar,const int size,const int low);

void turn(short*ar,const int size);
int cmp(const short*ar,const short*ar1,const int size);
int cmp0(const short*ar,const int size);
void r_shift(short*ar,const int size);
void l_shift(short*ar,const int size);

#define SIZE 10

int main(){
	short ar[SIZE],ar2[SIZE],ar3[SIZE];

	//ar=1000000000000000 
	ar[9]=0  ;ar[8]=0  ;ar[7]=10 ;ar[6]=0  ;ar[5]=0  ;
	ar[4]=0  ;ar[3]=0  ;ar[2]=0  ;ar[1]=0  ;ar[0]=0  ;

	//ar2=-1234
	ar2[9]=0  ;ar2[8]=0  ;ar2[7]=0  ;ar2[6]=0  ;ar2[5]=0  ;
	ar2[4]=0  ;ar2[3]=0  ;ar2[2]=0  ;ar2[1]=-12;ar2[0]=-34;

	sub(ar,ar2,ar3,SIZE);//引き算
	ar_print(ar,SIZE);printf("-");ar_print(ar2,SIZE);printf("=");ar_print(ar3,SIZE);printf("\n");

	add(ar,ar2,ar3,SIZE);//足し算
	ar_print(ar,SIZE);printf("+");ar_print(ar2,SIZE);printf("=");ar_print(ar3,SIZE);printf("\n");

	mul(ar,ar2,ar3,SIZE);//かけ算
	ar_print(ar,SIZE);printf("*");ar_print(ar2,SIZE);printf("=");ar_print(ar3,SIZE);printf("\n");

	ar_print(ar,SIZE);printf("/");ar_print(ar2,SIZE);printf("=");
	div(ar,ar2,ar3,SIZE);//割り算
	ar_print(ar3,SIZE);printf("...");ar_print(ar,SIZE);printf("\n");

	return 0;
}

//ar+ar2=ar3
void add(const short*ar,const short*ar2,short*ar3,const int size){
	int i,p_flag;
	for(i=0;i<size;i++){
		ar3[i]=ar[i]+ar2[i];
	}
	for(i=0;i<size;i++){
		if(ar3[i]>99){
			ar3[i]-=100;
			ar3[i+1]+=1;
		}else if(ar3[i]<-99){
			ar3[i]-=-100;
			ar3[i+1]+=-1;
		}
	}

	p_flag=cmp0(ar3,size);
	if(p_flag==0) return;

	for(i=0;i<size;i++){
		if(p_flag>0){
			if(0>ar3[i]){
				ar3[i+1]-=1;
				ar3[i]+=100;
			}
		}else{
			if(0<ar3[i]){
				ar3[i+1]-=-1;
				ar3[i]+=-100;
			}
		}
	}
}

//ar-ar2=ar3
void sub(const short*ar,short*ar2,short*ar3,const int size){
	turn(ar2,size);
	add(ar,ar2,ar3,size);
	turn(ar2,size);
}

//ar*ar2=ar3
void mul(const short*ar,const short*ar2,short*ar3,int size){
	int i,j,pos;
	for(i=0;i<size;i++){
		ar3[i]=0;
	}
	for(i=0;i<size;i++){
		if(ar2[i]){
			for(j=0;j<size;j++){
				ar3[j+i]+=ar[j]*ar2[i];
				//3桁目を繰り上げる
				if(ar3[j+i]>99 || ar3[j+i]<-99){
					pos=ar3[j+i]/100;	
					ar3[j+i]-=(pos*100);
					ar3[j+1+i]+=pos;
				}
			}
		}
	}
}

//  ar/ar2=ar3...ar
//  arが書き換えられて余りになる
void div(short*ar,short*ar2,short*ar3,const int size){
	int i,pos=0;
	int div_flag;//被除数の符号フラグ
	int met_flag;//法の符号フラグ

	for(i=0;i<size;i++){
		ar3[i]=0;
	}

	div_flag=cmp0(ar,size);
	met_flag=cmp0(ar2,size);

	if(!div_flag || !met_flag) return;//法、被除数のどちらかが0であるため計算中止
	if(-1==div_flag) turn(ar,size);//被除数が負数であるため正数にする
	if(-1==met_flag) turn(ar2,size);//法が負数であるため正数にする

	while(1){
		if(cmp(ar,ar2,size)==1 && (ar2[size-1]/10)==0){
			pos++;
			l_shift(ar2,size);
		}else break;
	}

	while(pos>=0){
		if(cmp(ar,ar2,size)>=0){
			sub(ar,ar2,ar,size);
			if(pos%2){
				ar3[pos/2]+=10;
			}else{
				ar3[pos/2]++;
			}
		}else{
			if(pos) r_shift(ar2,size);
			pos--;
		}
	}

	if(-1==div_flag) turn(ar,size);//被除数の符号を戻す
	if(-1==met_flag) turn(ar2,size);//法の符号を戻す
	if(div_flag!=met_flag) turn(ar3,size);//被除数と法の符号が違うため、答えをマイナスにする
}

//画面表示
void ar_print(short*ar,const int size){
	int i;
	int start_flag=0;
	int p_flag=cmp0(ar,size);
	if(p_flag==0){
		printf("0");
		return;
	}
	if(p_flag==-1){
		printf("-");
		turn(ar,size);
	}
	for(i=size-1;i>=0;i--){
		if(ar[i] || start_flag){
			if(!start_flag) printf("%d",ar[i]);
			else printf("%02d",ar[i]);
			start_flag=1;
		}
	}
	if(p_flag==-1) turn(ar,size);
}

//配列を固定小数点型として画面表示する ar[size-1].ar[size-2]~ar[low]
void dp_print(short*ar,const int size,const int low){
	int i,j=0,k=0;
	int p_flag=cmp0(ar,size);
	if(p_flag==0){
		printf("0");
		return;
	}
	if(p_flag==-1){
		printf("-");
		turn(ar,size);
	}

	printf("%d.",ar[size-1]);

	for(i=size-2;i>=low;i--){
		if(j++%5==0) printf(" ");
		if(k++%25==0) printf("\n");
		printf("%02d",ar[i]);

	}
	if(p_flag==-1) turn(ar,size);
}

//符号の反転
void turn(short*ar,const int size){
	int i;
	for(i=0;i<size;i++){
		ar[i]=-ar[i];
	}
}

//ar<ar1 の場合は-1を返す
//ar>ar1 の場合は+1を返す
//ar==ar1 の場合は0を返す
int cmp(const short*ar,const short*ar1,const int size){
	int i;
	for(i=size-1;i>=0;i--){
		if(ar[i]<ar1[i]) return -1;
		if(ar[i]>ar1[i]) return 1;
	}
	return 0;
}

//arがプラスの値をとる場合は+1を返す
//arがマイナスの値をとる場合は-1を返す
//arがゼロの値をとる場合は0を返す
int cmp0(const short*ar,const int size){
	int i;
	for(i=size-1;i>=0;i--){
		if(ar[i]<0) return -1;
		if(ar[i]>0) return 1;
	}
	return 0;
}


//右1シフト
void r_shift(short*ar,const int size){
	int i,pos;
	ar[0]=ar[0]/10;
	for(i=1;i<size;i++){
		pos=ar[i];
		ar[i]=ar[i]/10;
		ar[i-1]+=((pos-(ar[i]*10))*10);
	}

}

//左1シフト
void l_shift(short*ar,const int size){
	int i,pos;
	for(i=size-1;i>=0;i--){
		ar[i]=ar[i]*10;
		pos=ar[i]/100;
		ar[i]-=(pos*100);
		if(pos) ar[i+1]+=pos;
	}

}





▼実行結果

1000000000000000--1234=1000000000001234
1000000000000000+-1234=999999999998766
1000000000000000*-1234=-1234000000000000000
1000000000000000/-1234=-810372771474...1084


上の計算結果が正しいのかを確認するために、コマンドライン電卓を使い 検算してみます

$ bc

1000000000000000-(-1234)
1000000000001234
1000000000000000+(-1234)
999999999998766
1000000000000000*(-1234)
-1234000000000000000
1000000000000000/(-1234)
-810372771474
1000000000000000%(-1234)
1084


計算結果が一致し、計算が正しく行われていることが確認できました



■作成した計算方法を使って2の累乗を計算する

2の199乗までを計算してみます
プログラムのメイン関数部分を次のように書き換えました

▼かけ算で求める

このぐらいの桁数では大きな違いは見られませんが、
計算する桁数をもっと大きくした場合は、 かけ算より足し算の方で求めたほうがかなり速く処理できます
#define SIZE 30 //計算結果がオーバーフローしない程度の大きさを用意する

short ar[SIZE],ar2[SIZE],ar3[SIZE];//実行時にゼロ初期化される

int main(){
	int i,j;
	
	//ar=2
	ar[0]=2;

	//ar2=1
	ar2[0]=1;


	for(i=1;i<200;i++){
		mul(ar,ar2,ar3,SIZE);//かけ算
		printf("%d:",i);
		ar_print(ar3,SIZE);
		printf("\n");
		for(j=0;j<SIZE;j++) ar2[j]=ar3[j];//配列のコピー
	}
	return 0;
}
▼足し算で求める

#define SIZE 30 //計算結果がオーバーフローしない程度の大きさを用意する

short ar[SIZE],ar2[SIZE];//実行時にゼロ初期化される

int main(){
	int i,j;
	
	//ar=1
	ar[0]=1;

	for(i=1;i<200;i++){
		add(ar,ar,ar2,SIZE);//足し算
		printf("%d:",i);
		ar_print(ar2,SIZE);
		printf("\n");
		for(j=0;j<SIZE;j++) ar[j]=ar2[j];//配列のコピー
	}

	return 0;
}


▼実行結果

1:2
2:4
3:8
4:16
5:32
6:64
7:128
8:256
9:512
10:1024
11:2048
12:4096
13:8192
14:16384
15:32768
16:65536
17:131072
18:262144
19:524288
20:1048576
21:2097152
22:4194304
23:8388608
24:16777216
25:33554432
26:67108864
27:134217728
28:268435456
29:536870912
30:1073741824
31:2147483648
32:4294967296
33:8589934592
34:17179869184
35:34359738368
36:68719476736
37:137438953472
38:274877906944
39:549755813888
40:1099511627776
41:2199023255552
42:4398046511104
43:8796093022208
44:17592186044416
45:35184372088832
46:70368744177664
47:140737488355328
48:281474976710656
49:562949953421312
50:1125899906842624
51:2251799813685248
52:4503599627370496
53:9007199254740992
54:18014398509481984
55:36028797018963968
56:72057594037927936
57:144115188075855872
58:288230376151711744
59:576460752303423488
60:1152921504606846976
61:2305843009213693952
62:4611686018427387904
63:9223372036854775808
64:18446744073709551616
65:36893488147419103232
66:73786976294838206464
67:147573952589676412928
68:295147905179352825856
69:590295810358705651712
70:1180591620717411303424
71:2361183241434822606848
72:4722366482869645213696
73:9444732965739290427392
74:18889465931478580854784
75:37778931862957161709568
76:75557863725914323419136
77:151115727451828646838272
78:302231454903657293676544
79:604462909807314587353088
80:1208925819614629174706176
81:2417851639229258349412352
82:4835703278458516698824704
83:9671406556917033397649408
84:19342813113834066795298816
85:38685626227668133590597632
86:77371252455336267181195264
87:154742504910672534362390528
88:309485009821345068724781056
89:618970019642690137449562112
90:1237940039285380274899124224
91:2475880078570760549798248448
92:4951760157141521099596496896
93:9903520314283042199192993792
94:19807040628566084398385987584
95:39614081257132168796771975168
96:79228162514264337593543950336
97:158456325028528675187087900672
98:316912650057057350374175801344
99:633825300114114700748351602688
100:1267650600228229401496703205376
101:2535301200456458802993406410752
102:5070602400912917605986812821504
103:10141204801825835211973625643008
104:20282409603651670423947251286016
105:40564819207303340847894502572032
106:81129638414606681695789005144064
107:162259276829213363391578010288128
108:324518553658426726783156020576256
109:649037107316853453566312041152512
110:1298074214633706907132624082305024
111:2596148429267413814265248164610048
112:5192296858534827628530496329220096
113:10384593717069655257060992658440192
114:20769187434139310514121985316880384
115:41538374868278621028243970633760768
116:83076749736557242056487941267521536
117:166153499473114484112975882535043072
118:332306998946228968225951765070086144
119:664613997892457936451903530140172288
120:1329227995784915872903807060280344576
121:2658455991569831745807614120560689152
122:5316911983139663491615228241121378304
123:10633823966279326983230456482242756608
124:21267647932558653966460912964485513216
125:42535295865117307932921825928971026432
126:85070591730234615865843651857942052864
127:170141183460469231731687303715884105728
128:340282366920938463463374607431768211456
129:680564733841876926926749214863536422912
130:1361129467683753853853498429727072845824
131:2722258935367507707706996859454145691648
132:5444517870735015415413993718908291383296
133:10889035741470030830827987437816582766592
134:21778071482940061661655974875633165533184
135:43556142965880123323311949751266331066368
136:87112285931760246646623899502532662132736
137:174224571863520493293247799005065324265472
138:348449143727040986586495598010130648530944
139:696898287454081973172991196020261297061888
140:1393796574908163946345982392040522594123776
141:2787593149816327892691964784081045188247552
142:5575186299632655785383929568162090376495104
143:11150372599265311570767859136324180752990208
144:22300745198530623141535718272648361505980416
145:44601490397061246283071436545296723011960832
146:89202980794122492566142873090593446023921664
147:178405961588244985132285746181186892047843328
148:356811923176489970264571492362373784095686656
149:713623846352979940529142984724747568191373312
150:1427247692705959881058285969449495136382746624
151:2854495385411919762116571938898990272765493248
152:5708990770823839524233143877797980545530986496
153:11417981541647679048466287755595961091061972992
154:22835963083295358096932575511191922182123945984
155:45671926166590716193865151022383844364247891968
156:91343852333181432387730302044767688728495783936
157:182687704666362864775460604089535377456991567872
158:365375409332725729550921208179070754913983135744
159:730750818665451459101842416358141509827966271488
160:1461501637330902918203684832716283019655932542976
161:2923003274661805836407369665432566039311865085952
162:5846006549323611672814739330865132078623730171904
163:11692013098647223345629478661730264157247460343808
164:23384026197294446691258957323460528314494920687616
165:46768052394588893382517914646921056628989841375232
166:93536104789177786765035829293842113257979682750464
167:187072209578355573530071658587684226515959365500928
168:374144419156711147060143317175368453031918731001856
169:748288838313422294120286634350736906063837462003712
170:1496577676626844588240573268701473812127674924007424
171:2993155353253689176481146537402947624255349848014848
172:5986310706507378352962293074805895248510699696029696
173:11972621413014756705924586149611790497021399392059392
174:23945242826029513411849172299223580994042798784118784
175:47890485652059026823698344598447161988085597568237568
176:95780971304118053647396689196894323976171195136475136
177:191561942608236107294793378393788647952342390272950272
178:383123885216472214589586756787577295904684780545900544
179:766247770432944429179173513575154591809369561091801088
180:1532495540865888858358347027150309183618739122183602176
181:3064991081731777716716694054300618367237478244367204352
182:6129982163463555433433388108601236734474956488734408704
183:12259964326927110866866776217202473468949912977468817408
184:24519928653854221733733552434404946937899825954937634816
185:49039857307708443467467104868809893875799651909875269632
186:98079714615416886934934209737619787751599303819750539264
187:196159429230833773869868419475239575503198607639501078528
188:392318858461667547739736838950479151006397215279002157056
189:784637716923335095479473677900958302012794430558004314112
190:1569275433846670190958947355801916604025588861116008628224
191:3138550867693340381917894711603833208051177722232017256448
192:6277101735386680763835789423207666416102355444464034512896
193:12554203470773361527671578846415332832204710888928069025792
194:25108406941546723055343157692830665664409421777856138051584
195:50216813883093446110686315385661331328818843555712276103168
196:100433627766186892221372630771322662657637687111424552206336
197:200867255532373784442745261542645325315275374222849104412672
198:401734511064747568885490523085290650630550748445698208825344
199:803469022129495137770981046170581301261101496891396417650688




▲トップページ > プログラミングの実験