You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Remi Arntzen <re...@gmail.com> on 2006/07/02 23:15:20 UTC
[Commons-Math] FFT Support
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
Re: [Commons-Math] FFT Support
Posted by Phil Steitz <ph...@gmail.com>.
On 7/13/06, Remi Arntzen <re...@gmail.com> wrote:
> On 7/4/06, Phil Steitz <ph...@gmail.com> wrote:
> > Hi Remy,
> >
> > 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.
> >
>
> Well now that you mention it the current FastFourierTransformer class
> is not public for me to use. The transform method is public, but it
> is also non-static and thus requires an instantiation of the class.
> However the class is non-instantiable, because the constructor for the
> class only has package level access.
>
> I want to start work on a multi dimensional extension to this class,
> but it would be somewhat easier if the constructor was made public.
>
Fixed in svn. Sorry for the latency on this. In the future, to make
sure these things don't fall through the cracks, its best to open JIRA
tickets.
> Along the same lines, an extension to the API could use a utility
> class that contains only static versions of the corresponding methods
> in the FastFourierTransformer class. The original class could be
> remade with only static methods, but I believe it would be far quicker
> to make a FourierUtils ( :-) ) class or something.
>
+1 to the Utils class along the lines of StatUtils in the stat package.
Thanks for reporting the access problem.
Phil
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [Commons-Math] FFT Support
Posted by Remi Arntzen <re...@gmail.com>.
On 7/4/06, Phil Steitz <ph...@gmail.com> wrote:
> Hi Remy,
>
> 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.
>
Well now that you mention it the current FastFourierTransformer class
is not public for me to use. The transform method is public, but it
is also non-static and thus requires an instantiation of the class.
However the class is non-instantiable, because the constructor for the
class only has package level access.
I want to start work on a multi dimensional extension to this class,
but it would be somewhat easier if the constructor was made public.
Along the same lines, an extension to the API could use a utility
class that contains only static versions of the corresponding methods
in the FastFourierTransformer class. The original class could be
remade with only static methods, but I believe it would be far quicker
to make a FourierUtils ( :-) ) class or something.
I don't have any experience working with the junit api, but I believe
this error could be resolved by altering the programing pattern to
have the test classes in an alternate package, which would then be
able to detect this simple error at compile time.
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [Commons-Math] FFT Support
Posted by Remi Arntzen <re...@gmail.com>.
On 7/4/06, Phil Steitz <ph...@gmail.com> wrote:
> Hi Rem[i],
>
> On 7/2/06, Remi Arntzen <re...@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.
There it is!
> 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.
It's the same transform implemented via a different yet closely
related algorithm, therefore there is no need to add it to the
package. The current implementation is essentially the end product of
what I was hoping for.
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [Commons-Math] FFT Support
Posted by Phil Steitz <ph...@gmail.com>.
Hi Remy,
On 7/2/06, Remi Arntzen <re...@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