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 · ベストアンサー

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

お礼

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

回答No.4

Tacosan

4乗時間でよければ, 単純に 4重ループを組むだけです.
3乗時間にするなら, そのうち内側の 2重ループを工夫すればいい.

お礼

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

回答No.3

Tacosan

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

回答No.2

f272

#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でも良いので、総当たり戦であたっているのですが、うまくいかず、四苦八苦してます。