programming-examples/java/Basics/FastFourierTransform.java

package com.jwetherell.algorithms.mathematics;

import com.jwetherell.algorithms.numbers.Complex;

/**
 * A fast Fourier transform (FFT) algorithm computes the discrete Fourier transform (DFT) of a sequence, or its inverse. 
 * Fourier analysis converts a signal from its original domain (often time or space) to a representation in the frequency 
 * domain and vice versa. An FFT rapidly computes such transformations by factorizing the DFT matrix into a product of 
 * sparse (mostly zero) factors.
 * <p>
 * http://en.wikipedia.org/wiki/Fast_Fourier_transform
 * <br>
 * @author Mateusz Cianciara <e.cianciara@gmail.com>
 * @author Justin Wetherell <phishman3579@gmail.com>
 */
public class FastFourierTransform {

    private FastFourierTransform() { }

    /** 
     * The Cooley–Tukey algorithm, named after J.W. Cooley and John Tukey, is the most common fast Fourier transform 
     * (FFT) algorithm. It re-expresses the discrete Fourier transform (DFT) of an arbitrary composite size N = N1N2 
     * in terms of N1 smaller DFTs of sizes N2, recursively, to reduce the computation time to O(N log N) for highly 
     * composite N (smooth numbers).
     * <p>
     * http://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm
     * <br>
     * @param coefficients size must be power of 2
     */
    public static void cooleyTukeyFFT(Complex[] coefficients) {
        final int size = coefficients.length;
        if (size <= 1) 
            return;

        final Complex[] even = new Complex[size / 2];
        final Complex[] odd = new Complex[size / 2];
        for (int i = 0; i < size; i++) {
            if (i % 2 == 0) {
                even[i / 2] = coefficients[i];
            } else {
                odd[(i - 1) / 2] = coefficients[i];
            }
        }
        cooleyTukeyFFT(even);
        cooleyTukeyFFT(odd);
        for (int k = 0; k < size / 2; k++) {
            Complex t = Complex.polar(1.0, -2 * Math.PI * k / size).multiply(odd[k]);
            coefficients[k] = even[k].add(t);
            coefficients[k + size / 2] = even[k].sub(t);
        }
    }
}