Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-09T17:20:20.818Z Has data issue: false hasContentIssue false

The whole can be very much less than the sum of its parts

Published online by Cambridge University Press:  14 February 2019

Peter Shiu*
Affiliation:
353 Fulwood Road, Sheffield S10 3BQ e-mail: [email protected]

Extract

This Article is on the discrete Fourier transform (DFT) and the fast Fourier transform (FFT). As we shall see, FFT is a slight misnomer, causing confusion to beginners. The idiosyncratic title will be clarified in §4.

Computing machines are highly efficient nowadays, and much of the efficiency is based on the use of the FFT to speed up calculations in ultrahigh precision arithmetic. The algorithm is now an indispensable tool for solving problems that involve a large amount of computation, resulting in many useful and important applications: for example, in signal processing, data compression and photo-images in general, and WiFi, mobile phones, CT scanners and MR imaging in particular.

Type
Articles
Copyright
Copyright © Mathematical Association 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. Cooley, J. M. and Turkey, J. W., An algorithm for the machine calculation of complex Fourier series, Mathematics of Computation 19 (1965) pp. 297301.Google Scholar
2. Schönhage, A. and Strassen, V., Schnelle Multiplikation grosser Zahen, Computing (Arch. Electron. Rechnen) 7 (1971) pp. 281292.Google Scholar
3. Karatsuba, A. A. and Ofman, Y., Multiplication of multi-digit numbers on automata, Soviet Physics Doklady 7 (1963) pp. 595596.Google Scholar