FFTの基底の選び方について教えてください。

FFTの基底の選び方について教えてください。
NETLIB-NAPACKから任意個数のFFTをダウンロードし、個数が素数の計算をしたところ計算時間がものすごくかかります。例えば、N=16411で複素数の場合、そのままだと約15秒、後にゼロをつけて2のべき乗(N=32768)にすると0.02秒、N=17496(=2^3*3^7、試行で求めた)にすると0.03秒となります。そこで後につけるゼロの個数をできるだけ減らし、かつ元個数に最も近いような個数（例えば今回の17496)を、2,3,5,7のべき乗で表す個数（今回の17496)を求めるアルゴリズム、もしくはプログラムは無いものでしょうか。

No.1 ベストアンサー 回答者： Tacosan 回答日時： 2010/06/17 14:01

2, 3, 5, 7 のべきだけで与えられた N 以上の最も小さい数を作ればいいわけだから, O((log N)^4) のアルゴリズムは一瞬で考えられる. もちろん,

2^p 3^q 5^r 7^s
の p, q, r, s を全部調べるだけ.

この回答へのお礼

ありがとうございます。
言われてみれば目からうろこが落ちたような感じです。
今、実際にFFTの前段にプログラミング（Fortrannです）してますが、
てこずっています。

お礼日時：2010/06/17 19:43

No.4 回答者： Tacosan 回答日時： 2010/06/18 01:11

4乗時間でよければ, 単純に 4重ループを組むだけです.

3乗時間にするなら, そのうち内側の 2重ループを工夫すればいい.

この回答へのお礼

何度もご親切な回答、ありがとうございます。ご教示の方法でうまくいきました。もう一つ、素因数分解で2,3,5,7以外の数値が出る場合は元の個数を1ずつ増やし繰り返す方法も試しましたが、こちらもOKでした。

お礼日時：2010/06/18 15:07

No.3 回答者： Tacosan 回答日時： 2010/06/17 16:31

O((log N)^3) まではちょっとがんばれば落ちる.

もっと落ちるかなぁ?

No.2 回答者： f272 回答日時： 2010/06/17 14:25

#1の言うように作ってみると，やっぱり一瞬で

2^4 * 3^1 * 5^0 * 7^3 = 16464
が見つかる。

2^4 * 3^1 * 5^0 * 7^3 = 16464
2^5 * 3^1 * 5^2 * 7^1 = 16800
2^0 * 3^0 * 5^0 * 7^5 = 16807
2^1 * 3^5 * 5^1 * 7^1 = 17010
2^1 * 3^0 * 5^2 * 7^3 = 17150
2^7 * 3^3 * 5^1 * 7^0 = 17280
2^3 * 3^7 * 5^0 * 7^0 = 17496

この回答への補足

ありがとうございます。
今、実際にFFTの前段にプログラミング（FortranとVBAです）してますが、
てこずっています。最速時間となるNでなくても、ご教示のN=16464でも良いので、総当たり戦であたっているのですが、うまくいかず、四苦八苦してます。

補足日時：2010/06/17 19:48