What is the complexity (on the standard integer RAM) of computing the standard discrete Fourier transform of a vector of $n$ integers?
The classical algorithm for fast Fourier transforms, inappropriately attributed to Cooley and Tukey, is usually described as running in $O(n \log n)$ time. But most of the arithmetic operations executed in this algorithm start with complex $n$th roots of unity, which are (for most $n$) irrational, so exact evaluation in constant time is not reasonable. The same issue arises with the naive $O(n^2)$-time algorithm (multiplying by a Vandermonde matrix of complex roots of unity).
It's not even clear how to represent the output of the DFT exactly (in any useful form). In other words, it's not clear that computing DFTs is actually possible!
So suppose we only need $b$ bits of precision in each output value. What's the complexity of computing the discrete Fourier transform, as a function of $n$ and $b$? (For concreteness, feel free to assume $n$ is a power of $2$.)
Or does every instance of "FFT" in the literature actually mean "fast number-theoretic transform"?
 It should really be called (some prefix of) the Gauss-Runge-König-Yates-Stumpf-Danielson-Lánczos-Cooley-Tukey algorithm.
 And if so, why do most textbooks describe only the complex-number algorithm?