We show how to speed up the computation of fast Fourier transforms over complex numbers for “medium” precisions, typically in the range from until 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.

Occasion: ARITH 2015, Lyon, June 23, 2015

Coauthor: Grégoire Lecerf

Documents: slideshow, TeXmacs source