In essence, I'm trying to get a better feel for when there is a use for FFT with small coefficients, compared to the length, assuming that we get a better runtime.
I've been toying with an idea for a Fourier transform with elements of small size compared to the length of the transform. It seems that the running time is $O(n^m \log_2{(n^m)})$ total bit operations of size $n$, but it doesn't require any multiplications. I'm wondering if this could be useful, or if this can be totally circumvented with smaller transforms. In the case that it does seem useful, or comparable to other situations, what are the uses for it?
Also, if we suppose that it requires $O(f(m) \cdot n^m)$ multiplications, could it still be useful?
As an example, it seems to me that this would decrease the depth of a multiplication algorithm, since we can decrease the size of the coefficients that we use recursion on.
