edu.princeton.cs.algs4

## Class FFT

• Object
• edu.princeton.cs.algs4.FFT

• ```public class FFT
extends Object```
The `FFT` class provides methods for computing the FFT (Fast-Fourier Transform), inverse FFT, linear convolution, and circular convolution of a complex array.

It is a bare-bones 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 represents complex numbers and it it re-allocates memory for the subarray, instead of doing in-place or reusing a single temporary array.

This computes correct results if all arithmetic performed is without floating-point rounding error or arithmetic overflow. In practice, there will be floating-point 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
Modifier and Type Method and 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 the `FFT` class.
• ### Methods inherited from class Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### 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 of `x` 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 of `x` 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 array
`y` - the other complex array
Returns:
the circular convolution of `x` and `y`
Throws:
`IllegalArgumentException` - if the length of `x` does not equal the length of `y` 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 array
`y` - the other complex array
Returns:
the linear convolution of `x` and `y`
Throws:
`IllegalArgumentException` - if the length of `x` does not equal the length of `y` or if the length is not a power of 2
• #### main

`public static void main(String[] args)`
Unit tests the `FFT` class.
Parameters:
`args` - the command-line arguments