Minimal number of operations of a discrete Fourier transform

Question

Is there somewhere a table of the smallest known number $F(n)$ of (infinite precision) operations on complex numbers needed to compute a discrete Fourier transform on vectors of a given length $n$, for $n$ up to some reasonable limit like 100?

Answer 1

Considering a "flop" as a real arithmetic operation and ignoring precision, and apropos of @skbmoore's reference, the paper [Johnson, S. G. and Frigo, M. "A Modified Split-Radix FFT With Fewer Arithmetic Operations." IEEE Trans. Sig. Proc. 55, 111 (2007) (doi)] by the authors of FFTW achieves a flop count of $$\frac{43}{9} N \log_2 N - \frac{124}{27} N - 2 \log_2 N - \frac{2}{9}(-1)^{\log_2 N} \log_2 N + \frac{16}{27}(-1)^{\log_2 N} + 8.$$ Here $N$ is assumed a power of two. (See DSPSE answer along these lines here.) In particular, $N = 1,2,4,8,16,32,64,128$ respectively gives flop counts of $4,4,16,56,168,456,1152,2792$. This paper also points out that "no tight lower bound on the flop count is known" in general.

In [Haynal, S. A. and Haynal, H. B. "Generating and searching families of FFT algorithms." J. Satisfiability, Boolean Modeling Comp. 7, 145 (2011) (doi)] the authors show that certain types of FFT algorithm cannot improve on this bound (or indeed in many cases a weaker one) for small $N$.

Finally, Barseghyan and Sarukhanyan - New approach to FFT algorithms claims improved flop counts for $N$.