fft
Fast Discrete Fourier Transform (FFT)
Computes the Discrete Fourier Transform (DFT) of an array with a fast algorithm, the “Fast Fourier Transform” (FFT).
Usage
fft(z, inverse = FALSE)
mvfft(z, inverse = FALSE)
Arguments
 z
 a real or complex array containing the values to be transformed.
 inverse
 if
TRUE
, the unnormalized inverse transform is computed (the inverse has a+
in the exponent of $e$, but here, we do not divide by1/length(x)
).
Value

When
z
is a vector, the value computed and returned by
fft
is the unnormalized univariate discrete Fourier transform of the
sequence of values in z
. Specifically, y < fft(z)<="" code=""> returns
$$y[h] = \sum_{k=1}^n z[k] \exp(2\pi i (k1) (h1)/n)$$
for $h = 1, ..., n$ where n = length(y)
. If
inverse
is TRUE
, $exp(2*pi...)$
is replaced with $exp(2*pi...)$.When z
contains an array, fft
computes and returns the
multivariate (spatial) transform. If inverse
is TRUE
,
the (unnormalized) inverse Fourier transform is returned, i.e.,
if y < fft(z)<="" code="">, then z
is
fft(y, inverse = TRUE) / length(y)
.By contrast, mvfft
takes a real or complex matrix as argument,
and returns a similar shaped matrix, but with each column replaced by
its discrete Fourier transform. This is useful for analyzing
vectorvalued series.The FFT is fastest when the length of the series being transformed
is highly composite (i.e., has many factors). If this is not the
case, the transform may take a long time to compute and will use a
large amount of memory.
Source
Uses C translation of Fortran code in Singleton (1979).
References
Becker, R. A., Chambers, J. M. and Wilks, A. R. (1988) The New S Language. Wadsworth & Brooks/Cole. Singleton, R. C. (1979) Mixed Radix Fast Fourier Transforms, in Programs for Digital Signal Processing, IEEE Digital Signal Processing Committee eds. IEEE Press. Cooley, James W., and Tukey, John W. (1965) An algorithm for the machine calculation of complex Fourier series, Math. Comput. 19(90), 297301. https://dx.doi.org/10.1090/S00255718196501785861
See Also
Examples
x < 1:4
fft(x)
fft(fft(x), inverse = TRUE)/length(x)
## Slow Discrete Fourier Transform (DFT)  e.g., for checking the formula
fft0 < function(z, inverse=FALSE) {
n < length(z)
if(n == 0) return(z)
k < 0:(n1)
ff < (if(inverse) 1 else 1) * 2*pi * 1i * k/n
vapply(1:n, function(h) sum(z * exp(ff*(h1))), complex(1))
}
relD < function(x,y) 2* abs(x  y) / abs(x + y)
n < 2^8
z < complex(n, rnorm(n), rnorm(n))
## relative differences in the order of 4*10^{14} :
summary(relD(fft(z), fft0(z)))
summary(relD(fft(z, inverse=TRUE), fft0(z, inverse=TRUE)))
Community examples
Looks like there are no examples yet.