レーダーのFFTアルゴリズム
畳み込み定理 により、FFTを用いて計算することができる。また、N−1 は合成数のため、より高速なクーリーターキー型のFFTアルゴリズムが適用できる。しかしながら、N−1 が大きな素数の素因数をもつ場合、レーダーのアルゴリズムを再帰的に使う必要がある。その代わりに、長さ N−1 のDFTをゼロ埋めによって2の冪乗にすることで、高速なクーリーターキーのアルゴリズムを用いることができる。ゼロ埋め後のデータサイズが最低 2(N−1)−1 以上あれば元のデータを完全に復元することができ、ゼロ埋めによる結果の変化は生じない。
畳み込み積分の計算にゼロ埋めを用いたFFTを用いることでのこのアルゴリズムは加算について O(N) の計算時間とそれに加えと畳み込み積分についてと O(N log N) の計算時間で実行できる。しかしながら、このアルゴリズムは付近の合成数のサイズのFFTに比べ、およそ3から10倍の時間がかかる。