commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Remi Arntzen" <remi.arnt...@gmail.com>
Subject [Commons-Math] FFT Support
Date Sun, 02 Jul 2006 21:15:20 GMT
I was just wondering if there are other people with an interest in
developing an FFT class.

I have a simple Cooley-Tukey FFT implementation to start on, and
perhaps we could work on implementing other variations.

Now obviously this implementation is very crude, and needs many
improvements, but I believe that an FFT library could be a valuable
addition to the commons.  Please let me know what your opinions on
this are.

import org.apache.commons.math.complex.ComplexUtils;
import org.apache.commons.math.complex.Complex;

public class FFT {
    public static Complex[] fft(Complex[] input) {
        Complex[] output = new Complex[input.length];
        if (input.length == 1) {
            output[0] = input[0];
        } else {
            Complex[] even = new Complex[input.length/2];
            Complex[] odd = new Complex[input.length/2];
            for (int i = 0; i < input.length/2; i++) {
                even[i] = input[i*2];
                odd[i] = input[i*2 + 1];
            }
            Complex[] E = fft(even);
            Complex[] O = fft(odd);
            for (int i = 0; i < input.length; i++) {
                if (i < input.length/2) {
                    output[i] = E[i].add(ComplexUtils.exp(new Complex(0,
                            -2*Math.PI/input.length*i)).multiply(O[i]));
                } else {
                    output[i] = E[i - input.length/2].subtract(ComplexUtils.exp(
                            new Complex(0, -2*Math.PI/input.length*(i
                            - input.length/2))).multiply(O[i - input.length/2])
                            );
                }
            }
        }
        return output;
    }

    public static Complex[] ifft(Complex[] input) {
        Complex[] postInput = new Complex[input.length];
        for (int i = 0; i < input.length; i++) {
            postInput[i] = input[i].conjugate();
        }
        Complex[] output = fft(postInput);
        for (int i = 0; i < input.length; i++) {
            output[i] = output[i].conjugate().divide(new Complex(input.length,
                                                                 0));
        }
        return output;
    }
}

---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message