![]() |
![]() |
![]() |
![]() | Waves and Fourier sums | ![]() |
![]() |
Flexibility may be lost because the basic fast program works with complex-valued signals, so we ordinarily convert our real signals to complex ones (by adding a zero imaginary part). More flexibility is lost because typical fast FT programs require the data length to be an integral power of 2. Thus geophysical datasets often have zeros appended (a process called ``zero padding") until the data length is a power of 2. From time to time I notice clumsy computer code written to deduce a number that is a power of 2 and is larger than the length of a dataset. An answer is found by rounding up the logarithm to base 2.
How fast is the fast Fourier transform method?
The answer depends on the size of the data.
The matrix times vector operation in (8)
requires multiplications and additions.
That determines the speed of the slow transform.
For the fast method the number of adds and multiplies
is proportional to
.
Since
, the speed ratio is typically 1024/10 or about 100.
In reality, the fast method is not quite that fast,
depending on certain details of overhead and implementation.
A reference given at the end of this chapter
contains many versions of the FFT program.
One version transforms real-valued signals to complex-valued
frequency functions in the interval
.
Others that do not transform data on top of itself
may be faster with specialized computer architectures.
![]() |
![]() |
![]() |
![]() | Waves and Fourier sums | ![]() |
![]() |