Error estimates for multiplication based on FFT over the complex numbers

Abstract. We show that multiplication based on complex FFT is exact if usual rounding is used in a \(k\)-round FFT (\(k\ge2\)) with floating point numbers having \(m\)-bit mantissa and we put \(\ell\) bit digits into a floating point number, whenever the inequality $$ 8.074(k-2)+10.978 < 2^{m-2\ell-2k} $$ is satisfied.

Key words and phrases. Fast Fourier transform, multiplication of large numbers, error estimate, rounding error, IEEE754.