Class FFT
 Object

 edu.princeton.cs.algs4.FFT

public class FFT extends Object
TheFFT
class provides methods for computing the FFT (FastFourier Transform), inverse FFT, linear convolution, and circular convolution of a complex array.It is a barebones implementation that runs in n log n time, where n is the length of the complex array. For simplicity, n must be a power of 2. Our goal is to optimize the clarity of the code, rather than performance. It is not the most memory efficient implementation because it uses objects to represent complex numbers and it reallocates memory for the subarray, instead of doing inplace or reusing a single temporary array.
This computes correct results if all arithmetic performed is without floatingpoint rounding error or arithmetic overflow. In practice, there will be floatingpoint rounding error.
For additional documentation, see Section 9.9 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 Author:
 Robert Sedgewick, Kevin Wayne


Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static Complex[]
cconvolve(Complex[] x, Complex[] y)
Returns the circular convolution of the two specified complex arrays.static Complex[]
convolve(Complex[] x, Complex[] y)
Returns the linear convolution of the two specified complex arrays.static Complex[]
fft(Complex[] x)
Returns the FFT of the specified complex array.static Complex[]
ifft(Complex[] x)
Returns the inverse FFT of the specified complex array.static void
main(String[] args)
Unit tests theFFT
class.



Method Detail

fft
public static Complex[] fft(Complex[] x)
Returns the FFT of the specified complex array. Parameters:
x
 the complex array Returns:
 the FFT of the complex array
x
 Throws:
IllegalArgumentException
 if the length ofx
is not a power of 2

ifft
public static Complex[] ifft(Complex[] x)
Returns the inverse FFT of the specified complex array. Parameters:
x
 the complex array Returns:
 the inverse FFT of the complex array
x
 Throws:
IllegalArgumentException
 if the length ofx
is not a power of 2

cconvolve
public static Complex[] cconvolve(Complex[] x, Complex[] y)
Returns the circular convolution of the two specified complex arrays. Parameters:
x
 one complex arrayy
 the other complex array Returns:
 the circular convolution of
x
andy
 Throws:
IllegalArgumentException
 if the length ofx
does not equal the length ofy
or if the length is not a power of 2

convolve
public static Complex[] convolve(Complex[] x, Complex[] y)
Returns the linear convolution of the two specified complex arrays. Parameters:
x
 one complex arrayy
 the other complex array Returns:
 the linear convolution of
x
andy
 Throws:
IllegalArgumentException
 if the length ofx
does not equal the length ofy
or if the length is not a power of 2

main
public static void main(String[] args)
Unit tests theFFT
class. Parameters:
args
 the commandline arguments

