Faster FFTs in Medium Precision
Joris van der Hoeven, Grégoire Lecerf · 2015
In this paper, we show how to speed up the computation of fast Fourier transforms over complex numbers for "medium" precisions, typically in the range from 100 until 400 bits. On the one hand, such precisions are usually not supported by hardware. On the other hand, asymptotically fast algorithms for multiple precision arithmetic do not pay off yet. The main idea behind our algorithms is to develop efficient vectorial multiple precision fixed point arithmetic, capable of exploiting SIMD instructions in modern processors.