1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Struct to hold two primary type
public static class Complex2 {
public double real;
public double imag;
Complex2() {
this.real = 0;
this.imag = 0;
}
Complex2(double real, double imag) {
this.real = real;
this.imag = imag;
}
Complex2 add(Complex2 another) {
return new Complex2(this.real + another.real, this.imag + another.imag);
}
Complex2 scalarMultiply(Complex2 another) {
double x1 = this.real;
double x2 = another.real;
double y1 = this.imag;
double y2 = another.imag;
return new Complex2(x1*x2-y1*y2, x1*y2+x2*y1);
}
}

1
2
3
4
5
6
7
8
9
10
11
public static Complex2[] fft(List<Double> dataList) {
// Get the size of dataList
final int N = dataList.size();
Complex2[] fftResult = new Complex2[N];
// Traverse dataList by index k from 0 to size of dataList
for(int k=0 ; k<N ; k++) {
fftResult[k] = fftRecursion(dataList, N, k);
}
return fftResult;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* Realize FFT by divide-and-conquer algorithm
*
* @param ALineUnit This is List of fragemnt of ALine Points. The termination of recursion
*
is sometime when size of ALineUnit is 2
*/
private static Complex2 fftRecursion(List<Double> ALineUnit, int unitLength, int k) {
if(unitLength == 2) {
Complex2 unit2 = new Complex2();
// Apply FFT to data list (size:2)
double xn;
// Get real value
for(int k1=0 ; k1<2 ; k1++) {
for(int n=0 ; n<2 ; n++) {
xn = ALineUnit.get(n);
unit2.real += xn * cos(2*PI*k1*n/2);
unit2.imag -= xn * sin(2*PI*k1*n/2);
}
}
return unit2;
}
else {
// Cut odd and even component of the current unit
List<Double> oddList = new ArrayList<>();
List<Double> evenList = new ArrayList<>();
for(int i=0 ; i<unitLength/2 ; i++) {
oddList.add(ALineUnit.get(2*i + 1));
evenList.add(ALineUnit.get(2*i));
}
return fftRecursion(evenList, unitLength/2, k).add(new Complex2(cos(2*PI*k/unitLength), -sin(2*PI*k/unitLength)).scalarMultiply(fftRecursion(oddList, unitLength/2, k)));
}
}