prime length FFT

Hello, I have to program a general purpose FFT program an my question is
about prime lengths. 
For radices 2,3,5,and 7 I have coded small DFT modules WFTA.
For large lengths I have employed Chirp z-Transform (Bluestein).
For medium length prime (11,13,...) Bluestein don't work really good, so
what's your opinion about Rader's or Agarwal-Cooley for this lengths?
Do you know other methods?

Thanks a lot for your answers. 

ima_zoncolan schrieb:
> Hello, I have to program a general purpose FFT program an my question is
> about prime lengths. 

There is nothing like "FFT" with prime lengths, because the FFT relies 
on the factorisation of the length. So I don't understand the question.


Marcel

On Feb 19, 6:32 am, "ima_zoncolan" <imar...@gmail.com> wrote:
> Hello, I have to program a general purpose FFT program an my question is
> about prime lengths.
> For radices 2,3,5,and 7 I have coded small DFT modules WFTA.
> For large lengths I have employed Chirp z-Transform (Bluestein).
> For medium length prime (11,13,...) Bluestein don't work really good, so
> what's your opinion about Rader's or Agarwal-Cooley for this lengths?
> Do you know other methods?
>
> Thanks a lot for your answers.

Do you have a requirement to write the implementations yourself? If
not, there are a number of good FFT libraries out there (like FFTW),
that are extremely optimized, even for sizes with small prime factors.

Jason

On Feb 19, 6:52 pm, Marcel M&#4294967295;ller <news.5.ma...@spamgourmet.com>
wrote:
> > Hello, I have to program a general purpose FFT program an my question is
> > about prime lengths.
>
> There is nothing like "FFT" with prime lengths, because the FFT relies
> on the factorisation of the length. So I don't understand the question.

This is a common misconception.  There are, in fact, a couple of FFT
algorithms that achieve O(N log N) complexity for prime N.  Google
"Bluestein's FFT algorithm" and "Rader's FFT algorithm".

The root of your error is your term "the FFT."  There is more than one
distinct FFT algorithm, although the most common algorithms in
practice are variations on Cooley-Tukey (often erroneously called
"the" FFT).

Regards,
Steven G. Johnson

On Feb 19, 6:32 am, "ima_zoncolan" <imar...@gmail.com> wrote:
> Hello, I have to program a general purpose FFT program an my question is
> about prime lengths.
> For radices 2,3,5,and 7 I have coded small DFT modules WFTA.
> For large lengths I have employed Chirp z-Transform (Bluestein).
> For medium length prime (11,13,...) Bluestein don't work really good, so
> what's your opinion about Rader's or Agarwal-Cooley for this lengths?
> Do you know other methods?

In FFTW, we found Rader's algorithm to be more effective than
Bluestein for small prime lengths where you can hard-code the
transform; if N-1 is highly composite, it requires less arithmetic
than Bluestein, and the overhead of Rader's interesting little
permutation is irrelevant for hard-coded transforms.

Note also that you don't necessarily want to break things into prime
radices.  For example, just because your size is a power of 2 doesn't
mean you want to use radix-2!  Quite apart from arithmetic
considerations, using larger radices allows one to better exploit e.g.
larger register sets, and is easier on the cache(s), at least on
general purpose CPUs.  In FFTW we have hard-coded radices up to
radix-64.

Note also that WFTA is not necessarily the best choice for sizes 3 and
5 and 7; we actually found the O(N^2) algorithm to be faster than
either WFTA or Rader for size 3 and 7, probably because of register-
pressure issues; again, this is on general-purpose CPUs.  YMMV.

Regards,
Steven G. Johnson