fft {stats} | R Documentation |

## Fast Discrete Fourier Transform (FFT)

### Description

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. Long vectors are not supported. |

`inverse` |
if |

### 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)`

returns

`y[h] = \sum_{k=1}^n z[k] \exp(-2\pi i (k-1) (h-1)/n)`

for `h = 1,\ldots,n`

where n = `length(y)`

. If
`inverse`

is `TRUE`

, `\exp(-2\pi\ldots)`

is replaced with `\exp(2\pi\ldots)`

.

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)`

, 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
vector-valued 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,
*Mathematics of Computation*, **19**(90), 297–301.
doi:10.2307/2003354.

### 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:(n-1)
ff <- (if(inverse) 1 else -1) * 2*pi * 1i * k/n
vapply(1:n, function(h) sum(z * exp(ff*(h-1))), 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)))
```

*stats*version 4.4.0 Index]