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

問題 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.16 回答者： matyrcry 回答日時： 2007/10/29 12:35

固定値のテーブル作成例です。

(分量多いので少し横着しました）
#define SSS(S) S(1),S(2),S(3),S(4),S(5),S(6),S(7),S(8),S( 9),S( 10),\
S( 11),S( 12),S( 13),S( 14),S( 15),S( 16),S( 17),S( 18),S( 19),S( 20),\
S( 21),S( 22),S( 23),S( 24),S( 25),S( 26),S( 27),S( 28),S( 29),S( 30),\
S( 31),S( 32),S( 33),S( 34),S( 35),S( 36),S( 37),S( 38),S( 39),S( 40),\
S( 41),S( 42),S( 43),S( 44),S( 45),S( 46),S( 47),S( 48),S( 49),S( 50),\
S( 51),S( 52),S( 53),S( 54),S( 55),S( 56),S( 57),S( 58),S( 59),S( 60),\
S( 61),S( 62),S( 63),S( 64),S( 65),S( 66),S( 67),S( 68),S( 69),S( 70),\
S( 71),S( 72),S( 73),S( 74),S( 75),S( 76),S( 77),S( 78),S( 79),S( 80),\
S( 81),S( 82),S( 83),S( 84),S( 85),S( 86),S( 87),S( 88),S( 89),S( 90),\
S( 91),S( 92),S( 93),S( 94),S( 95),S( 96),S( 97),S( 98),S( 99),S(100),\
S(101),S(102),S(103),S(104),S(105),S(106),S(107),S(108),S(109),S(110),\
S(111),S(112),S(113),S(114),S(115),S(116),S(117),S(118),S(119),S(120),\
S(121),S(122),S(123),S(124),S(125),S(126),S(127),S(128),S(129),S(130),\
S(131),S(132),S(133),S(134),S(135),S(136),S(137),S(138),S(139),S(140),\
S(141),S(142),S(143),S(144),S(145),S(146),S(147),S(148),S(149),S(150),\
S(151),S(152),S(153),S(154),S(155),S(156),S(157),S(158),S(159),S(160),\
S(161),S(162),S(163),S(164),S(165),S(166),S(167),S(168),S(169),S(170),\
S(171),S(172),S(173),S(174),S(175),S(176),S(177),S(178),S(179),S(180),\
S(181),S(182),S(183),S(184),S(185),S(186),S(187),S(188),S(189),S(190),\
S(191),S(192),S(193),S(194),S(195),S(196),S(197),S(198),S(199),S(200)

// ５乗値
#define D5D(n) (double)((double)n*(double)n*(double)n*(double)n*(double)n)
const double DIM5[201] = { (double)0,SSS(D5D) };
// ５乗値の３２剰余
#define D5M32(n) ((n%32)*(n%32)*(n%32)*(n%32)*(n%32))%32
const int DIM5_MOD32[201] = { 0,SSS(D5M32) };
// 元値の３２剰余
#define D1M32(n) n%32
const int DIM1_MOD32[201] = { 0,SSS(D1M32) };
// 元値の１０剰余
#define D1M10(n) n%10
const int DIM1_MOD10[201] = { 0,SSS(D1M10) };
// ５乗値の１０剰余（元値と同じ）
#defineDIM5_MOD10 DIM1_MOD10

No.15 回答者： matyrcry 回答日時： 2007/10/26 12:38

３２の剰余を使えばもっと手数が少なくできそうです。

//０～３１の５乗を３２で割った剰余
const int DIM5_MOD32[32] = {
0,1,0,19,0,21,0,7,0,9,0,27,0,29,0,15,
0,17,0,3,0,5,0,23,0,25,0,11,0,13,0,31
};
ここから考えると、
１）５乗値の剰余が０以外の偶数になることはない。
２）５乗値の剰余が奇数なら元値の剰余は特定できる。
は適用できそうです。
５乗値の和や差の剰余値は除算しなくても元値の剰余が分かれば
上の配列を使って計算できます。
例）１＾５＋３＾５の剰余は２０になる
偶数なら剰余が０のときだけ検索すればよく、
奇数なら候補は３２飛ばしで多くても６～７個です。
前述の１０の剰余を使ってさらに候補を減らすこともできます。

No.14 回答者： matyrcry 回答日時： 2007/10/26 07:51

剰余から推測する方法は結構いけるようですね。

５乗値を１０で割った剰余は元数と同じになるようです。
最下層は１０飛ばしで検索できるので、
１，１１，２１，３１，．．．１９１の５乗、
２，１２，２２，３２，．．．１９２の５乗、
という１０刻みで２０個のテーブルを作っておけばいいかも。

No.13 回答者： matyrcry 回答日時： 2007/10/26 00:19

肝心なところを説明してなかったですが、整数でまかなえる部分は整数

演算で行うと考えれば、
ａ，ｂ，ｃ，ｄを決めてｅを探すよりも、
ａ，ｂ，ｃ，ｅを決めて差分からｃ＜ｄ＜ｅの範囲でｄを探すほうが
演算が若干整数範囲に入りやすいと思うのです。
浮動小数プロセッサを有効活用しないと演算時間は加減算でも数倍、
乗算だと１０倍以上かかるはずです。（駆使しても何倍かは重いはず）
まぁあまりいじるとこぼしそうなので正攻法でこなした方が無難かもし
れませんけど、やはり自分なら７３＾５を閾値にして幾分かでも整数演
算を導入したいかな。
全部浮動小数で計算するつもりなら、今まで書いた
５乗値を固定配置する（乗算をなくす）
ループの各階層で中間合計を記憶して加算演算を減らす
オーバーフローを判定（してループを抜ける）
５つ目の変数を中点検索する
くらいです。
あと些細な小技ですが、
５つ目の数は残りの４つが決まれば偶数か奇数か判別できますから、
最下層のループは逐次検索でも半分に減らせます。
５乗値の浮動小数だと判別しづらいので元数の偶奇から判別すると
いいでしょう。

No.12 回答者： matyrcry 回答日時： 2007/10/25 18:08

ごめんなさい。

読み違ってましたね。^^;
４個和＝残りの１つですか！！
２００＾５も一応３９ビットで基数部に入るようですね。
手持ち環境（マイコン）で試してできましたから、
(double)1*(double)1*(double)1*(double)1*(double)1,
で固定値配置はＰＣでも可能だと思います。
７３以下なら５乗しても２１億を切るので、７３までの５乗配列を
用意しておき、３個和からの差分が７３＾５より小さい場合は整数
で判定したほうがいいです。
ＣＰＵが専用演算を持ってたとしても整数演算のほうが数倍速いの
が普通なので、手間をかけたとしてもお釣りがたっぷり来るはず。

No.11 回答者： matyrcry 回答日時： 2007/10/25 17:04

ループの条件式を見ると、５つの数値はそれぞれ違う数値でなければ

ならないのでしょうか？
とすれば、５乗値の配列から連続５個の和を読めば組み合わせの
上限と下限は判断つきますよね。

毎回５個和をとるのでなく、各階層で１～４個の中間和を記憶して
おけば、合計値が対象を超えた時点でブレークして次候補の演算に
すぐ移行できるはずです。

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秒まで短縮できました。

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.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.7 回答者： matyrcry 回答日時： 2007/10/25 12:41

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

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