package fast_fourier_transform;
import java.io.IOException;
import java.math.BigDecimal;
public class Main {
int[] a;
int[] b;
int n;
String[] as;
int m;
Complex_number[] V;
Complex_number w;
Complex_number[] V2;
BigDecimal fi;
public Main() throws IOException {
StringBuffer sb = new StringBuffer();
String s;
Fileoutput out = new Fileoutput();
Filereader file = new Filereader("input4.dat");
n = file.getn();
as = new String[n * 2 + 3];
as = file.getlist();
m = getm(n);
V = new Complex_number[m];
V2 = new Complex_number[m];
for (int i = 0; i < V.length; i++) {
V[i] = new Complex_number();
V2[i] = new Complex_number();
}
w = new Complex_number();
w.real = Math.cos(Math.PI * 2 / m);
w.imagi = Math.sin(Math.PI * 2 / m);
a = new int[m];
b = new int[m];
for (int i = 0; i < a.length; i++) {
if (i < n + 1) {
a[i] = Integer.parseInt(as[n + 1 - i]);
} else {
a[i] = 0;
}
}
for (int i = 0; i < b.length; i++) {
if (i < n + 1) {
b[i] = Integer.parseInt(as[n * 2 + 2 - i]);
} else {
b[i] = 0;
}
}
for (int i = 0; i < V.length; i++) {
V[i].real = a[i];
V[i].imagi = 0;
}
V = Fast_Fourier_Transform(m, V, w);
for (int i = 0; i < V2.length; i++) {
V2[i].real = b[i];
V2[i].imagi = 0;
}
V2 = Fast_Fourier_Transform(m, V2, w);
for (int i = 0; i < m; i++) {
V2[i] = V2[i].mult(V[i]);
}
w.imagi = -w.imagi;
w.real = w.real;
V2 = Fast_Fourier_Transform(m, V2, w);
double p = 1;
double q = m;
Complex_number t = new Complex_number(p / q, 0);
for (int i = 0; i < V2.length; i++) {
V2[i] = V2[i].mult(t);
}
for (int i = 2*n; i >=0; i--) {
fi=new BigDecimal(V2[i].real);
fi=fi.setScale(0,BigDecimal.ROUND_HALF_UP);
System.out.println("A[" + i + "]=" + fi);
sb.append(fi+" ");
}
s=sb.toString().trim();
out.output(s, "result4.dat");
}
public int getm(int n) {
int i = 1;
while (i < 2 * n + 1) {
i = i * 2;
}
return i;
}
public Complex_number[] Fast_Fourier_Transform(int n, Complex_number[] a,
Complex_number w) {
if (n == 1) {
return a;
} else {
Complex_number[] U = new Complex_number[n / 2];
Complex_number[] W = new Complex_number[n / 2];
Complex_number[] a1 = new Complex_number[n / 2];
Complex_number[] a2 = new Complex_number[n / 2];
for (int i = 0; i < a1.length; i++) {
a1[i] = new Complex_number(a[i * 2].real, a[i * 2].imagi);
a2[i] = new Complex_number(a[i * 2 + 1].real,
a[i * 2 + 1].imagi);
}
for (int i = 0; i < U.length; i++) {
U[i] = new Complex_number();
}
for (int i = 0; i < W.length; i++) {
W[i] = new Complex_number();
}
Complex_number v = new Complex_number();// v=w*w
v = w.mult(w);
U = Fast_Fourier_Transform(n / 2, a1, v);
W = Fast_Fourier_Transform(n / 2, a2, v);
double angle;
if (w.real < 0) {
angle = Math.atan(w.imagi / w.real) + Math.PI;
} else {
angle = Math.atan(w.imagi / w.real);
}
for (int i = 0; i <= n / 2 - 1; i++) {
double p = i;
v.real = Math.cos(angle * p);
v.imagi = Math.sin(angle * p);
Complex_number temp1 = new Complex_number();
Complex_number temp2 = new Complex_number(-1, 0);
temp1 = v.mult(W[i]);
a[i] = U[i].add(temp1);
temp2 = temp1.mult(temp2);
a[i + n / 2] = U[i].add(temp2);
}
return a;
}
}
public static void main(String[] argvs) throws IOException {
new Main();
}
}
fft.rar （12个子文件） 
fft 
input4.dat 35B bin fast_fourier_transform Main.class 5KB Filereader.class 2KB Complex_number.class 886B Fileoutput.class 777B ex4_fast_fourier_transform result4.dat 29B src fast_fourier_transform Complex_number.java 613B Fileoutput.java 273B Filereader.java 649B Main.java 4KB ex4_fast_fourier_transform .project 379B .classpath 232B资源评论
