累乗を行うとき

[sign]

数値を処理するプログラムにおいて、xⁿを行いたいとき、
x が整数で、n が非負整数であることを前提にしているような場合、その結果も整数になりますが、

特に実数型を用いないような処理（プログラム）において累乗を扱うには、
value = (int)pow(x, n);
のように毎度キャストするのが妥当なのでしょうか。

x²などと指数が決まっていれば、x*xのように書いても良いのかもしれませんが。
仮に2乗の場合にx*xと記述することを決めたとすると、何乗までをそのように書くのかということも考えてしまいます。

x^n や x**n のような表記ができれば越したことはないのですが、Cに関しては一般的にどうなのでしょうか。


別件ですが、
ある自然数を、3乗して、4乗根の整数部を求めて、2乗する、
というようにpow関数を連続した場合、プログラムの処理は著しく遅くなるでしょうか？
この程度の処理をさせて、入力される自然数に対して求めたい値を算出するようなプログラムを書いたのですが、
別のプログラムに比べると、100個程度のデータ入力に対して出力が終わるまでに数秒かかったので気になりました…。

回答いただければ幸いです。

[ぽん太]

xが非0整数でnが非負整数の場合の冪乗計算でnが大きい場合は
こんなのが早かったりします.

vaule=1;
for(;n>0;n>>=1){
if(n%2)
value*=x;
x=x*x;
}

[box]

> 別のプログラムに比べると、100個程度のデータ入力に対して出力が終わるまでに数秒かかったので気になりました…。

どのようなコードを書かれましたか？

[sign]

返信が遅くなり申し訳ありません。

＞ぽん太さん
なるほど。
具体値で追跡して概ね理解できました。
途中で n が奇数になったときにそれまでの x を value に乗算するところがうまく理解できていませんが；
これに関してですが、「xが非0整数」と書かれていますが、x=0 だと理想値は得られないのでしょうか…。

＞boxさん
「 n>=3 のとき、x^n + y^n = z^n を満たす自然数の組 x, y, z は存在しない」というフェルマーの最終定理に関して、
2以上の自然数 z が与えられたとき、
x^n + y^n < z^n を満たす x^n + y^n が最大となるとき、『 z^n - (x^n + y^n) 』を求める。
といった内容です。
プログラムを書く上で、さらに条件として n=3, (1<)z<1000 を加えます。

実際はファイル入力ですが、以下のソースではfor文で z を回したものを示します。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main(void){
	const int n=3;
	int x, y, z, t;
	int zn, xy, max;
	for(z=900; z<=999; z++){
	[color=tea[/url]/* z^n を zn に代入 */[/color]
		zn = (int)pow(z, n);
	[color=tea[/url]/* (x^3)+(x^3) < z となる最大のxを t に代入 */[/color]
		t = (int)pow(zn/2, 1.0/n);
	[color=tea[/url]/* x と y に t をに代入 */[/color]
		x = y = t;
	[color=tea[/url]/* (x^3)+(y^3) を max に代入 */[/color]
		max = 2 * (int)pow(t, n);
	[color=tea[/url]/* x を z-1 から t+1 まで */[/color]
		for(x=z-1; x>t; x--){
		[color=tea[/url]/* y を t から デクリメント */[/color]
		[color=tea[/url]/* (x^3)+(y^3) が zn 以下になったら抜ける */[/color]
			for(y=t; (xy=(int)(pow(x, n)+pow(y, n)))>zn; y--);
		[color=tea[/url]/* 最新の (x^3)+(y^3) が 今までの max より大きかったら max を更新*/[/color]
			if(max < xy) max = xy;
		}
		printf("%d\n", zn-max);
	}
	return(0);
}

テストデータが1000近くの場合に、x, y のループが多くなるせいで処理に時間がかかっているのですね…；

と書いたのですが、冗長な処理を見つけました。

[color=tea[/url]/* x を z-1 から t+1 まで */[/color]
	for(x=z-1; x>t; x--){
	[color=tea[/url]/* y を t から デクリメント */[/color]
	[color=tea[/url]/* (x^3)+(y^3) が zn 以下になったら抜ける */[/color]
		for(y=t; (xy=(int)(pow(x, n)+pow(y, n)))>zn; y--);
	[color=tea[/url]/* 最新の (x^3)+(y^3) が 今までの max より大きかったら max を更新*/[/color]
		if(max < xy) max = xy;
	}

y のループの中では不変の x が引数のpow関数を動かしていました…。

[color=tea[/url]/* x を z-1 から t+1 まで */[/color]
	for(x=z-1; x>t; x--){
		xn = (int)pow(x, n);
	[color=tea[/url]/* y を t から デクリメント */[/color]
	[color=tea[/url]/* (x^3)+(y^3) が zn 以下になったら抜ける */[/color]
		for(y=t; (xy=(int)(xn+pow(y, n)))>zn; y--);
	[color=tea[/url]/* 最新の (x^3)+(y^3) が 今までの max より大きかったら max を更新*/[/color]
		if(max < xy) max = xy;
	}

と変更したら随分速くなりました…。
自己解決してしまいましたが、boxさんの回答がなければ気付くまで検証しなかったかもしれません；
回答ありがとうございました。

誠に勝手ではございますが、もしこのプログラムに関して改善可能な点が見受けられるようでしたらご指摘お願いします。


※ font 要素を pre 要素の内容とすることはできませんが、可読性を考慮して文法無視で色を変えています…。

[ぽん太]

あのプログラムで
x=0
n=0
とすると
0^0=1 になります。
しかし0^0は不定であるという見解もある
ようなので非０整数と書いておきました。

[sign]

そういう考慮でしたか。
理解いたしました。
ありがとうございました。

[しっぽ]

> 誠に勝手ではございますが、もしこのプログラムに関して改善可能な点が見受けられるようでしたらご指摘お願いします。



無意味なコードがあります。

/* x と y に t をに代入 */
		x = y = t;

yの初期値を変えてみたらどうでしょうか。

/* x を z-1 から t+1 まで */
	for(x=z-1; x>t; x--){
		xn = (int)pow(x, n);
		s = (int)pow((zn - xn), 1.0/n);
	/* y を s+1 から デクリメント */
	/* (x^3)+(y^3) が zn 以下になったら抜ける */
		for(y=s+1; (xy=(int)(xn+pow(y, n)))>zn; y--);
	/* 最新の (x^3)+(y^3) が 今までの max より大きかったら max を更新*/
		if(max < xy) max = xy;
	}

下記でも良いような気がしますが、未確認。

/* x を z-1 から t+1 まで */
	for(x=z-1; x>t; x--){
		xn = (int)pow(x, n);
		y = (int)pow((zn - xn), 1.0/n);
		xy=(int)(xn+pow(y, n));
		max = xy;
	}

[しっぽ]

私の三番目のコードには明らかな誤りがあるので訂正します。

/* x を z-1 から t+1 まで */
	for(x=z-1; x>t; x--){
		xn = (int)pow(x, n);
		y = (int)pow((zn - xn), 1.0/n);
		xy=(int)(xn+pow(y, n));
		if(max < xy){
			max = xy;
		}
	}

[sign]

＞しっぽさん

> 無意味なコードがあります。
完全にデバッグ用の記述でした…。（コメントの助詞も誤記；）
ご指摘ありがとうございます。

> yの初期値を変えてみたらどうでしょうか。
確かに仰るとおりですね。
ここまで読んで確認したら、まさに s が そのときの x に対する y だと気付き…
> 下記でも良いような気がしますが、未確認。
まさに仰られる通りになりました。
ありがとうございます。

このような（数学的観点から）効率の良いプログラム（アルゴリズム）に気付けるようになりたいです…；

ありがとうございました。
一応…解決マークにさせていただきます。