private void fft(double re[],double im[],int direction){
  int n=re.length;
  int bits=(int)Math.rint(Math.log(n) / Math.log(2));
  if (n != (1 << bits))   throw new IllegalArgumentException("fft data must be power of 2");
  int localN;
  int j=0;
  for (int i=0; i < n - 1; i++) {
    if (i < j) {
      double temp=re[j];
      re[j]=re[i];
      re[i]=temp;
      temp=im[j];
      im[j]=im[i];
      im[i]=temp;
    }
    int k=n / 2;
    while ((k >= 1) && (k - 1 < j)) {
      j=j - k;
      k=k / 2;
    }
    j=j + k;
  }
  for (int m=1; m <= bits; m++) {
    localN=1 << m;
    double Wjk_r=1;
    double Wjk_i=0;
    double theta=twoPI / localN;
    double Wj_r=Math.cos(theta);
    double Wj_i=direction * Math.sin(theta);
    int nby2=localN / 2;
    for (j=0; j < nby2; j++) {
      for (int k=j; k < n; k+=localN) {
        int id=k + nby2;
        double tempr=Wjk_r * re[id] - Wjk_i * im[id];
        double tempi=Wjk_r * im[id] + Wjk_i * re[id];
        re[id]=re[k] - tempr;
        im[id]=im[k] - tempi;
        re[k]+=tempr;
        im[k]+=tempi;
      }
      double wtemp=Wjk_r;
      Wjk_r=Wj_r * Wjk_r - Wj_i * Wjk_i;
      Wjk_i=Wj_r * Wjk_i + Wj_i * wtemp;
    }
  }
}

private void fft ( double re [ ] , double im [ ] , int direction ) { int n = re . length ; int bits = ( int ) Math . rint ( Math . log ( n ) / Math . log ( 2 ) ) ; if ( n != ( 1 << bits ) ) throw new IllegalArgumentException ( "fft data must be power of 2" ) ; int localN ; int j = 0 ; for ( int i = 0 ; i < n - 1 ; i ++ ) { if ( i < j ) { double temp = re [ j ] ; re [ j ] = re [ i ] ; re [ i ] = temp ; temp = im [ j ] ; im [ j ] = im [ i ] ; im [ i ] = temp ; } int k = n / 2 ; while ( ( k >= 1 ) && ( k - 1 < j ) ) { j = j - k ; k = k / 2 ; } j = j + k ; } for ( int m = 1 ; m <= bits ; m ++ ) { localN = 1 << m ; double Wjk_r = 1 ; double Wjk_i = 0 ; double theta = twoPI / localN ; double Wj_r = Math . cos ( theta ) ; double Wj_i = direction * Math . sin ( theta ) ; int nby2 = localN / 2 ; for ( j = 0 ; j < nby2 ; j ++ ) { for ( int k = j ; k < n ; k += localN ) { int id = k + nby2 ; double tempr = Wjk_r * re [ id ] - Wjk_i * im [ id ] ; double tempi = Wjk_r * im [ id ] + Wjk_i * re [ id ] ; re [ id ] = re [ k ] - tempr ; im [ id ] = im [ k ] - tempi ; re [ k ] += tempr ; im [ k ] += tempi ; } double wtemp = Wjk_r ; Wjk_r = Wj_r * Wjk_r - Wj_i * Wjk_i ; Wjk_i = Wj_r * Wjk_i + Wj_i * wtemp ; } } }
the fft method . calculation is inline , for complex data stored in 2 separate arrays . length of input data must be a power of two .
