レーダーのFFTアルゴリズム
畳み込み積分の計算をゼロ埋めなしのFFTで行う場合、計算時間は N の性質に強く依存する。最悪の場合、N−1 が素数 N2 により N−1= 2N2 と表され、また N2−1 が素数 N3 により N2−1 = 2N3 と表され、以下同様に続いていく場合である。このような場合、レーダーのアルゴリズムの再帰が連続することになり、O(N) の計算時間がかかる可能性がある。このような性質をもつ N は ソフィー・ジェルマン素数と呼ばれ、上記の数列は一次の Cunningham(ビル-カニンガム)チェーンと呼ばれる。しかしながら、これまでの研究ではカニンガムチェーンの成長は log2(N) よりも遅いことが分かっているため、レーダーのアルゴリズムの再帰によりかかる計算時間は O(N) よりかは速いと思われる。幸いにも、畳み込み計算にゼロ埋めを用いたFFTを使えば計算時間は O(N log N) のオーダーになることが保証されている。