FFT inputRe inputIm outputRe outputIm

The FFT command computes the Fast Fourier Transform of its inputs in rectangular coordinate form. The input vector lengths must be a power of 2. Both input vectors must be the same length.

inputRe contains the real parts of all the data points.

inputIm contains the imaginary parts of all the data points.

outputRe will contain the real parts of the transformed data.

outputIm will contain the imaginary parts of the transformed data.

The following related subroutines are included in the Statistics101 subroutine library (See the table below):

IFFT computes the Inverse FFT in rectangular coordinates.
COMPLEX_FFT computes the FFT using rectangular coordinate vectors (i.e., single vectors containing both real and imaginary parts).
COMPLEX_FFTZ computes the Inverse FFT using rectangular coordinate vectors (i.e., single vectors containing both real and imaginary parts).
COMPLEX_FFTZ computes the Fast Fourier Transform, but unlike the FFT command takes as its input a single vector containing polar coordinates and produces as its output a single vector containing polar coordinates.
COMPLEX_IFFTZ computes the Inverse Fast Fourier Transform, but unlike the IFFT subroutine takes as its input a single vector containing polar coordinates and produces as its output a single vector containing polar coordinates.

Also included are two related subroutines, CONVOLVE and CCONVOLVE, for performing linear and circular convolution.

Implementation note:

The implementation of the FFT command uses a non-recursive version of the Cooley-Tukey FFT. It runs in O(n log(n)) time, where n is the length of the input vectors.

Source for the algorithm is: https://introcs.cs.princeton.edu/java/97data/InplaceFFT.java

Copy the following program, paste it into the Statistics101 editor window and run it. It demonstrates the results of the forward and inverse FFT.

'Create a sine wave input:
nPoints = 1024 'Must be a power of 2
angle = 1,nPoints
angleRad = TORAD(angle)
y = sin(angleRad)
XYGRAPH angle y

'Take FFT of the sine wave:
zeroVec = nPoints#0
FFT y zeroVec outRe outIm
XYGRAPH angle outRe
XYGRAPH angle outIm

'Take the inverse FFT of the above output:
IFFT outRe outIm y2Re y2Im
XYGRAPH angle y2Re
XYGRAPH angle y2Im

The following program is the same as that above except that it uses COMPLEX rectangular coordinate vectors (i.e., a single vector containing both re and im parts) with the "convenience routines" (see table below) for those vectors. The "convenience" routines in this example program are really not convenient because we had to force the data into the proper format using other COMPLEX_* subroutines. But if you were manipulating most of your data in the complex rectangular coordinate form, they might save a few programming steps.

'Create a sine wave input:
nPoints = 1024 'Must be a power of 2
angle = 1,nPoints
angleRad = TORAD(angle)
y = sin(angleRad)
XYGRAPH angle y

'Take FFT of the sine wave:
zeroVec = nPoints#0
COMPLEX y zeroVec zRectIn
COMPLEX_FFT zRectIn zRectOut
COMPLEX_RE zRectOut outRe
COMPLEX_IM zRectOut outIm
XYGRAPH angle outRe
XYGRAPH angle outIm

'Take the inverse FFT of the above output:
COMPLEX_IFFT zRectOut zOut
COMPLEX_RE zOut outRe
COMPLEX_IM zOut outIm
XYGRAPH angle outRe
XYGRAPH angle outIm

The next table shows the existing subroutine variations in the Statistics101 library that are available to compute forward and inverse Fast Fourier Transformations. Only "FFT" is a built-in command. All the other names are subroutines. The "Z" entries represent the arguments that are in the form of single vectors containing both real and imaginary, or both magnitude and angle.

Arguments:	Re, Im	Rho, Theta	Z (Rectangular)	Z (Polar)
Forward Transform:	FFT	-	COMPLEX_FFT	COMPLEX_FFTZ
Inverse Transform:	IFFT	-	COMPLEX_IFFT	COMPLEX_IFFTZ