冪乗


冪乗の program は非常に単純である。必要な桁数の配列を用意し, 上から順に掛け算して, 繰上げが起こるかどうか順に check していけばよい。

先ず, JAVA に於いて int は最大 231 - 1 = 2,147,483,647 で, long は最大 263 - 1 = 9,223,372,036,854,775,808 である。つまり (263 - 1)1/2 = 3,037,000,499.97604969245138853002631 であるから, 掛け算の場合, overflow を起こさないように考えると, 一つの配列当たり, 109 - 1 = 999,999,999 までが安全な範囲である。(C では int も long も 32 bit 整数だから, もっとちまちまやらなくてはならず, 非常に苦労した覚えがある。尤も algorithm は同じなのだが。)

高校で対数函数を習うと分かるように, 十進法で実数 x の整数部分が何桁になるかというのは log10x で判定できる。同様にして, この場合, 配列が幾つ必要になるかというのを次の函数で判定している。


static int getsize(long x, int y, int size)
{
	double temp = y * Math.log(x) /(size * Math.log(10));
	int ret = (int)Math.ceil(temp);

	if(temp - ret == 0)	// if temp is integer
		ret++;
	return ret;
}

変数 size は繰上げの起こる桁数 9 を格納している (外部変数として final 宣言したのだが, 一つの函数をまたがると, その変数がなんだか分からんと抜かすので, 仕方なく引数として渡してある)。 変数 temp は底の変換公式を用いているので分かりにくくなっているが, 要するに log1,000,000,000xy が幾つになるかを計算している。変数 ret はその値を下回らない最小の整数を返すが, もしも temp 自体が整数であった場合には, もう一桁大きいのでその処理がしてある。

このあとは簡単である。


//main calculation
y--;
for(dig[0] = x; y > 0; y--){
	for(i = dim -1; i >= 0; i--){
		dig[i] *= x;
		//carry up process
		for(j = i; dig[j] >= CARRYSIZE; j++){
			dig[j+1] += dig[j]/CARRYSIZE;
			dig[j] %= CARRYSIZE;
		}
	}
}

最初 for 文の中に y-- を入れておいたのだが, JAVA ではそれは許されないらしく, はねられたので, 外に出してある。上位の桁から掛け算をしているので掛け算をする度に, その上の方で繰り上がりが起こっていないのかどうかを調べるのが味噌である。勿論式中に現れる CARRYSIZE は Math.pow(10, SIZE) == 109 (SIZE == 9) である。

出力の方も printf のような高度に書式処理の出来る函数がないので, 一寸工夫がしてあるが, それは誰でも思いつく程度のものなので, 省略しておく。

Thursday, 4th May, 2000.


BACK