Reliable and fast FFT in Java

Question

since I don t want to do it on my own  I am searching for a good FFT implementation for java  First I used this one here FFT Princeton but it uses objects and my profiler told me  that its not really fast due to this fact  So I googled again and found this one  FFT Columbia which is faster  Maybe one of you guys know another FFT implementation  I d like to have the  best  one because my app has to process a huge amount of sound data  and users don t like waiting     -   Regards

User · Answer

Late to the party - here as a pure java solution for those when JNI is not an option JTransforms

User · Answer

FFTW is the  fastest fourier transform in the west   and has some Java wrappers      http   www fftw org download html   Hope that helps

User · Answer

I m looking into using SSTJ for FFTs in Java   It can redirect via JNI to FFTW if the library is available or will use a pure Java implementation if not

User · Answer

I wrote a function for the FFT in Java  http   www wikijava org wiki The Fast Fourier Transform in Java  28part 1 29  It s in the Public Domain so you can use those functions everywhere  personal or business projects too   Just cite me in the credits and send me just a link of your work  and you re ok   It is completely reliable  I ve checked its output against the Mathematica s FFT and they were always correct until the 15th decimal digit  I think it s a very good FFT implementation for Java  I wrote it on the J2SE 1 6 version  and tested it on the J2SE 1 5-1 6 version   If you count the number of instruction  it s a lot much simpler than a perfect computational complexity function estimation  you can clearly see that this version is great even if it s not optimized at all  I m planning to publish the optimized version if there are enough requests   Let me know if it was useful  and tell me any comment you like   I share the same code right here          author Orlando Selenu      public class FFTbase          The Fast Fourier Transform  generic version  with NO optimizations          param inputReal               an array of length n  the real part     param inputImag               an array of length n  the imaginary part     param DIRECT               TRUE   direct transform  FALSE   inverse transform     return a new array of length 2n     public static double   fft final double   inputReal  double   inputImag                             boolean DIRECT           - n is the dimension of the problem        - nu is its logarithm in base e     int n   inputReal length          If n is a power of 2  then ld is an integer   without  decimals      double ld   Math log n    Math log 2 0           Here I check if n is a power of 2  If exist decimals in ld  I quit        from the function returning null      if    int  ld  - ld    0            System out println  The number of elements is not a power of 2             return null                Declaration and initialization of the variables        ld should be an integer  actually  so I don t lose any information in        the cast     int nu    int  ld      int n2   n   2      int nu1   nu - 1      double   xReal   new double n       double   xImag   new double n       double tReal  tImag  p  arg  c  s          Here I check if I m going to do the direct transform or the inverse        transform      double constant      if  DIRECT          constant   -2   Math PI      else         constant   2   Math PI          I don t want to overwrite the input arrays  so here I copy them  This        choice adds  Theta 2n  to the complexity      for  int i   0  i  lt  n  i              xReal i    inputReal i           xImag i    inputImag i                 First phase - calculation     int k   0      for  int l   1  l  lt   nu  l              while  k  lt  n                for  int i   1  i  lt   n2  i                      p   bitreverseReference k  gt  gt  nu1  nu                      direct FFT or inverse FFT                 arg   constant   p   n                  c   Math cos arg                   s   Math sin arg                   tReal   xReal k   n2    c   xImag k   n2    s                  tImag   xImag k   n2    c - xReal k   n2    s                  xReal k   n2    xReal k  - tReal                  xImag k   n2    xImag k  - tImag                  xReal k     tReal                  xImag k     tImag                  k                              k    n2                    k   0          nu1--          n2    2                Second phase - recombination     k   0      int r      while  k  lt  n            r   bitreverseReference k  nu           if  r  gt  k                tReal   xReal k               tImag   xImag k               xReal k    xReal r               xImag k    xImag r               xReal r    tReal              xImag r    tImag                    k                  Here I have to mix xReal and xImag to have an array  yes  it should        be possible to do this stuff in the earlier parts of the code  but        it s here to readibility       double   newArray   new double xReal length   2       double radice   1   Math sqrt n       for  int i   0  i  lt  newArray length  i    2            int i2   i   2             I used Stephen Wolfram s Mathematica as a reference so I m going            to normalize the output while I m copying the elements          newArray i    xReal i2    radice          newArray i   1    xImag i2    radice            return newArray            The reference bitreverse function      private static int bitreverseReference int j  int nu        int j2      int j1   j      int k   0      for  int i   1  i  lt   nu  i              j2   j1   2          k   2   k   j1 - 2   j2          j1   j2            return k

User · Answer

I guess it depends on what you are processing  If you are calculating the FFT over a large duration you might find that it does take a while depending on how many frequency points you are wanting  However  in most cases for audio it is considered non-stationary  that is the signals mean and variance changes to much over time   so taking one large FFT  Periodogram PSD estimate  is not an accurate representation  Alternatively you could use Short-time Fourier transform  whereby you break the signal up into smaller frames and calculate the FFT  The frame size varies depending on how quickly the statistics change  for speech it is usually 20-40ms  for music I assume it is slightly higher   This method is good if you are sampling from the microphone  because it allows you to buffer each frame at a time  calculate the fft and give what the user feels is  real time  interaction  Because 20ms is quick  because we can t really perceive a time difference that small   I developed a small bench mark to test the difference between FFTW and KissFFT c-libraries on a speech signal  Yes FFTW is highly optimised  but when you are taking only short-frames  updating the data for the user  and using only a small fft size  they are both very similar  Here is an example on how to implement the KissFFT libraries in Android using LibGdx by badlogic games  I implemented this library using overlapping frames in an Android App I developed a few months ago called Speech Enhancement for Android

[java] Reliable and fast FFT in Java

Examples related to java

Examples related to fft