0xdeadbeef hat gesagt.:Ich bin mir zwar nicht ganz sicher, was Du mit einem springenden Ball meinst
public class FFT {
/**
* This is a Java implementation of the fast Fourier transform
* written by Jef Poskanzer. The copyright appears above.
*/
private static final double TWOPI = 2.0 * Math.PI;
// Limits on the number of bits this algorithm can utilize
private static final int LOG2_MAXFFTSIZE = 15;
private static final int MAXFFTSIZE = 1 << LOG2_MAXFFTSIZE;
/**
* FFT class constructor
* Initializes code for doing a fast Fourier transform
*
* @param int bits is a power of two such that 2^b is the number
* of samples.
*/
public FFT(int bits) {
this.bits = bits;
if (bits > LOG2_MAXFFTSIZE) {
System.out.println("" + bits + " is too big");
System.exit(1);
}
for (int i = (1 << bits) - 1; i >= 0; --i) {
int k = 0;
for (int j = 0; j < bits; ++j) {
k *= 2;
if ((i & (1 << j)) != 0)
k++;
}
bitreverse = k; //<--- hier meckert eclipse >> Prob. A
}
}
/**
* A fast Fourier transform routine
*
* @param double [] xr is the real part of the data to be transformed
* @param double [] xi is the imaginary part of the data to be transformed
* (normally zero unless inverse transofrm is effect).
* @param boolean invFlag which is true if inverse transform is being
* applied. false for a forward transform.
*/
public void doFFT(double [] xr, double [] xi, boolean invFlag) {
int n, n2, i, k, kn2, l, p;
double ang, s, c, tr, ti;
n2 = (n = (1 << bits)) / 2;
for (l = 0; l < bits; ++l) {
for (k = 0; k < n; k += n2) {
for (i = 0; i < n2; ++i, ++k) {
p = bitreverse[k / n2];
ang = TWOPI * p / n;
c = Math.cos(ang);
s = Math.sin(ang);
kn2 = k + n2;
if (invFlag)
s = -s;
tr = xr[kn2] * c + xi[kn2] * s;
ti = xi[kn2] * c - xr[kn2] * s;
xr[kn2] = xr[k] - tr;
xi[kn2] = xi[k] - ti;
xr[k] += tr;
xi[k] += ti;
}
}
n2 /= 2;
}
for (k = 0; k < n; k++) {
if ((i = bitreverse[k]) <= k)
continue;
tr = xr[k];
ti = xi[k];
xr[k] = xr; //<-- hier meckert eclipse >>>
xi[k] = xi; //<-- hier meckert eclipse >>> Prob. B
xr = tr; //<-- hier meckert eclipse >>>
xi = ti; //<-- hier meckert eclipse >>>
}
// Finally, multiply each value by 1/n, if this is the forward
// transform.
if (!invFlag) {
double f = 1.0 / n;
for (i = 0; i < n ; i++) {
xr *= f; //<-- hier meckert eclipse >>>
xi *= f; //<-- hier meckert eclipse >>> Prob. C
}
}
}
// Private class data
private int bits;
private int [] bitreverse = new int[MAXFFTSIZE];
}
// Declare your arrays
double[] realData;
double[] imaginaryData;
/*
Init and fill your data from where you want...
*/
// Obtain an FFT instance
FFT fft = new FFT(/* int bits*/);
// Call the method
fft.doFFT(realData, imaginaryData, true);
/*
Do whatever you need with your array, knowing that their content has been modified...
*/
public class FFT {
int n;
int[] bitrev;
double[] sintbl;
public FFT(int n) {
this.n = n;
sintbl = new double[n + n / 4];
bitrev = new int[n];
// ŽOŠpŠÖ?”•\‚ð?ì‚é.
double t = Math.sin(Math.PI / n);
double dc = 2 * t * t;
double ds = Math.sqrt(dc * (2 - dc));
t = 2 * dc;
double c = sintbl[n / 4] = 1;
double s = sintbl[0] = 0;
for (int i = 1; i < n / 8; i++) {
c -= dc; dc += t * c;
s += ds; ds -= t * s;
sintbl[i] = s; sintbl[n / 4 - i] = c;
}
if (n / 8 != 0) sintbl[n / 8] = Math.sqrt(0.5);
for (int i = 0; i < n / 4; i++)
sintbl[n / 2 - i] = sintbl[i];
for (int i = 0; i < n / 2 + n / 4; i++)
sintbl[i + n / 2] = - sintbl[i];
// ƒrƒbƒg”½“]•\‚ð?ì‚é.
int i = 0;
int j = 0;
bitrev[0] = 0;
while (++i < n) {
int k = n / 2;
while (k <= j) { j -= k; k /= 2; }
j += k;
bitrev[i] = j;
}
}
void fftsub(double[] x, double[] y, int sign) {
for (int i = 0; i < n; i++) { // ƒrƒbƒg”½“]
int j = bitrev[i];
if (i < j) {
double t = x[i]; x[i] = x[j]; x[j] = t;
t = y[i]; y[i] = y[j]; y[j] = t;
}
}
for (int k = 1; k < n; k *= 2) { // •ÏŠ·
int h = 0;
int d = n / (k * 2);
for (int j = 0; j < k; j++) {
double c = sintbl[h + n / 4];
double s = sign * sintbl[h];
for (int i = j; i < n; i += k * 2) {
int ik = i + k;
double dx = s * y[ik] + c * x[ik];
double dy = c * y[ik] - s * x[ik];
x[ik] = x[i] - dx; x[i] += dx;
y[ik] = y[i] - dy; y[i] += dy;
}
h += d;
}
}
}
public void fft(double[] x, double[] y) {
fftsub(x, y, 1);
}
public void ifft(double[] x, double[] y) {
fftsub(x, y, -1);
for (int i = 0; i < n; i++) {
x[i] /= n; y[i] /= n;
}
}
// ƒeƒXƒg—p
public static void main(String[] args) {
final int N = 64;
double x1[] = new double[N];
double y1[] = new double[N];
double x2[] = new double[N];
double y2[] = new double[N];
double x3[] = new double[N];
double y3[] = new double[N];
for (int i = 0; i < N; i++) {
x1[i] = x2[i] = 6 * Math.cos( 6 * Math.PI * i / N)
+ 4 * Math.sin(18 * Math.PI * i / N);
y1[i] = y2[i] = 0;
}
FFT fftN = new FFT(N);
fftN.fft(x2, y2);
for (int i = 0; i < N; i++) {
x3[i] = x2[i]; y3[i] = y2[i];
}
fftN.ifft(x3, y3);
System.out.println("(Œ³ƒf?[ƒ^) (ƒt?[ƒŠƒG•ÏŠ·) (‹t•ÏŠ·)");
for (int i = 0; i < N; i++)
System.out.println(i + " (" +
(float)x1[i] + "," +
(float)y1[i] + ") (" +
(float)x2[i] + ", " +
(float)y2[i] + ") (" +
(float)x3[i] + ", " +
(float)y3[i] + ")");
}
}
lin hat gesagt.:Aber für Equalizer kannste auch winamp nehmen ;-)
huch, klingt kompliziert, weil die Frequenz des Gesangs variiert ja ständig? *interessier*es geht darum zB auch lästigen gesang aus wertvoller musik zu verbannen...