About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of the ACM
Paper
Accumulation of Round-Off Error in Fast Fourier Transforms
Abstract
The fast Fourier transform (FFT) is an algorithm to compute the discrete Fourier coefficients with a substantial time saving over conventional methods. The finite word length used in the computer causes an error in computing the Fourier coefficients. This paper derives explicit expressions for the mean square error in the FFT when floating-point arithmetics are used. Upper and lower bounds for the total relative mean square error are given. The theoretical results are in good agreement with the actual error observed by taking the FFT of data sequences. © 1970, ACM. All rights reserved.