計算速度をはやくするには

問題 a^5 + b^5 + c^5 + d^5 = e^5 が成立する場合のa,b,c,d,eを計算するプログラムを作成したのですが、処理速度が30秒もかかってしまいます。
どこを変更、または何を追加すれば速くなるか教えてください。


条件は a < b < c < d < e
a,b,c,d,e, < 200 です。

どうかご教授お願いします。









#include <stdio.h>

int main (void)

{

int a,b,c,d,e ;

double A5,B5,C5,D5,E5;

for(a = 1; a <= 195 ; a++ )

{

A5 = a * a * a * a * (double)a ;


for(b = a+1; b <= 196 ; b++ )

{

B5 = b * b * b * b * (double)b ;

for(c = b+1; c <= 197 ; c++ )

{

C5 = c * c * c * c * (double)c ;

for(d = c+1; d <= 198 ; d++ )

{

D5 = d * d * d * d * (double)d ;

for(e = d+1; e <= 199 ; e++ )

{

E5 = e * e * e * e * (double)e ;





if((A5 + B5 + C5 + D5 ) == E5)

{

printf("a=%d,b=%d,c=%d,d=%d,e=%d\n",a,b,c,d,e);
printf("a^5=%.0lf,b^5=%.0lf,c^5=%.0lf,d^5=%.0lf,e^5=%.0lf\n",A5,B5,C5,D5,E5);

}

}
}
}
}
}

return 0;

}

No.1 回答者： Evreux 回答日時： 2007/10/25 10:42

判定条件は ゼロと等しいかどうかで判定するようにすると、早くなるという話を聞いたことがあります。

ゼロとの比較は専用の命令があるとかないとか

コンパイル時に最適化はしてますよね？
5重ループなので三十秒くらいは・・・とも思いますが

No.2 回答者： keikyu2101 回答日時： 2007/10/25 10:46

同じ５乗の計算を何度もやっているから遅いのです。

掛け算には時間が掛かるのに、５乗ですから時間の無駄です。配列に１回計算したら保存しておいて、取り出して使えばいいじゃないでしょうか？　例えば、eは、５から１９９の範囲で計算したのを取っておけば同じ計算をしないで済みます。同様にa～dの計算結果をとっておくことで、掛け算の回数が激減します。

No.3 回答者： keikyu2101 回答日時： 2007/10/25 10:58

＃２です。

落ち着いて考えてみたら、まず最初に１～199の5乗を計算し配列にしまっておいて、それを取り出しながら計算すればいんですね。aとかeとかは区別する必要はないですね。

この回答への補足

配列にしまっておく方法がよく分かりません。
もしよろしければ、具体的に助言お願いします。

補足日時：2007/10/25 11:00

No.4 回答者： DIooggooID 回答日時： 2007/10/25 11:01

math.h をインクルードして、５乗の計算を　pow(a, 5)　に変えてみてはいかがでしょうか？

５乗程度では、差がでないかもしれませんが。

No.5 回答者： keikyu2101 回答日時： 2007/10/25 11:17

＃３です。

＃４さんのも取り入れて５乗の計算結果の保存と取り出し部分については、以下のようになります。

#include <math.h>

double T[200];

for(a = 1; a <= 199 ; a++ )

{
T[a] = pow(a,5);
}

これで、貯めておくことが出来ます。

取り出して使うときは、

A5 = T[a];

になります。

この回答への補足

最初に配列に計算結果を保存しておいて
取り出すというのはできましたが、今度は取り出しのループのせいで
処理速度は変わりませんでした。
ループの方法から変えないといけないんでしょうか。。。

補足日時：2007/10/25 11:22

No.6 回答者： keikyu2101 回答日時： 2007/10/25 11:36

A5 + B5 + C5 + D5 の計算が無駄に多いですね。

double SUM;
と宣言しておいて、一番外側のループで
SUM=A5;
その内側で、
SUM += B5；
…
SUM += D5;
というふうに加算していって、
if(SUM == E5)
と比較すると、足し算の回数が少なく出来ると思います。

No.7 回答者： matyrcry 回答日時： 2007/10/25 12:41

５乗の数値はいちいち計算しなくても固定値配列で作れるはずです。

const int TBL[] = {
1*1*1*1*1,
2*2*2*2*2,
...
};
２００の５乗は３２ビット範囲（２＾３１－１まで）を超えるので
範囲内まで抑えてください。
合計値が比較対象を超えたらそれ以降の計算は無駄なのでブレーク
してください。
途中でオーバーフローする可能性も考慮必要です。
配列は右上がりなので、最後の判定部は逐次比較ではなく中点検索
でいけます。

No.8 回答者： AsanoNagi 回答日時： 2007/10/25 12:41

この場合、諸悪の根源は、約200回×５重のループの存在そのものです。

ループの回数を減らさないと、計算時間の向上は無理です。
例えば、
100^5 + 101^5 + 102^5 + 103^5 = 104^5
というのは、ちょっと考えれば、チェックする必要もないわけです。
実際には、（ちょっとではなく）よく考えて、チェックする必要のないものをあらかじめ除きます。

よく考えるのは苦手なので、思いつくのを２点
ループですが、
a < b < c < d < e
ですから、
for(e = 1; e <= 200; e++)
{
　for(d = 1; d < e; d++)
　{
　　for(c = 1; c < d; c++)
　　{
　　　for(b = 1; b < c; b++)
　　　{
　for(a = 1; a < b; a++)
　　　　{

とネストさせることで、計算回数はかなり減らせるはずです。
また、a^5 + b ^5 の計算中に、e^5 以上になれば、それ以降チェックする必要はありません。
これは、大きい方からチェックするとすぐにあふれますから、このネストの中で、
double sum = 0
　　　　　e5 = e*e*e*e*(double)e;
　　　　　sum += d*d*d*d*(double)d;
　　　　　if (sum>= e5) continue;
　　　　　sum += c*c*c*c*(double)c;
　　　　　if (sum >= e5) continue;

のようにすれば、それなりに計算量を減らすことができるはずです。

もっとじっくり考えれば、もっと計算量を減らすことができるでしょう。
もしかしたら、(a + b + c + d) が、「何とか以上」なら、計算不要というような関係が見つかるかもしれません。

No.9 回答者： AsanoNagi 回答日時： 2007/10/25 12:52

No.8 です。

もう一つ追加。
効果のほどはわかりませんが。

一般に、a ～ d が正の数であれば、
(a + b + c + d)^5 >= a^5 + b^5 + c^5 + d^5 です。
ですから、
(a + b + c + d)^5 < e^5 なら、a^5 + b^5 + c^5 + d^5 は、（もっと小さいので）e^5 に等しくなることはありません。
これを利用して、ループする処理の先頭で、

double sum = a + b + c + d;
sum = sum * sum * sum * sum * sum;
e5 = e * e * e * e * double(e);
if (sum < e5) continue;

という判断を入れると、ループの回数はかなり減るのではないかと思います。
これは、例えば、
1^5 + 2^5 + 3^5 + 4^5 = 100^5
のようなケースのチェックを回避するためのものです。

この判断をするための計算量とトレードオフではありますが。

No.10 回答者： bgbg 回答日時： 2007/10/25 15:10

No.2のように、予め5乗の計算結果を共通の配列に保存しておきます。

a,b,c,d,e すべての5乗の計算は共通の配列から取り出します。
処理速度が変わらないというのは無いはずです。私が検証した結果40%ほど処理速度が向上しました。

もう一つ、No.8のように枝刈りをする方法です。ソースではaから順に昇順で計算していますが、e^5を計算した後の判定において a^5 + b^5 + c^5 + d^5 < e^5 であれば、それ以降eを加算しても右辺と左辺は同値になりません。
よって、左辺 < 右辺となった時点でeのループはbreakさせることができ、ループ回数を減らせます。
この処理によりループ回数を約75%減らせます。

こちらの環境で試したところ、質問文のソースでは50秒、上記の改良後は6秒まで短縮できました。