commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Phil Steitz" <phil.ste...@gmail.com>
Subject Re: [Commons-Math] FFT Support
Date Tue, 04 Jul 2006 21:23:31 GMT
Hi Remy,

On 7/2/06, Remi Arntzen <remi.arntzen@gmail.com> wrote:
> I was just wondering if there are other people with an interest in
> developing an FFT class.

Yes!  This has been on the roadmap for commons math for quite a while.
I just committed an FFT package that was submitted some time ago.  It
is in a new "transform" package, org.apache.commons.math.transform.
The test coverage is still not where we would like to have it and we
may want to refine/revise the API.  Please have a look and if you have
suggestions for improvement or are willing to work on adding more test
cases / validation with other packages, thanks in advance.

Your code below implements a different transform, which could be added
to the transform package as well, providing that you (or someone else)
are willing to document the algorithm and provide test cases.  Have a
look at the code just checked in for an example of the kind of javadoc
references and test cases we like to have.  The "Developers Guide"
link on the left nav of the commons math web site provides info on
this and how to submit patches, etc.  Thanks!

Phil
>
> 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
>
>

---------------------------------------------------------------------
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