Rosetta Code

Fast Fourier transform: Difference between revisions

Page Discussion

Fast Fourier transform (view source)

Revision as of 05:00, 28 June 2011

376 bytes removed ,  13 years ago
m
→‎{{header|C}}: Since we are using c99 anyway...
m (→‎{{header|C}}: Since we are using c99 anyway...)
Line 93:
#include <math.h>
#include <complex.h>
#include <stdlib.h>
#include <string.h>
 
double PI;
typedef double complex cplx;
 
void _fft(cplx * buf[], cplx *out[], int n, int step)
{
if (step < n) {▼
int i;
_fft(out, buf, n, step * 2);
cplx t;
_fft(out + step, buf + step, n, step * 2);
 
▲ if (step < n) {
for (int i = 0; i < n; i += 2 _fft(out, buf, n,* step) * 2);{
cplx t = cexp(-I * PI * i / n) * _fft(out[i + step, buf + step, n, step * 2)];
buf[i / 2] = out[i] + t;▼
 
buf[(i + n)/2] = out[i] - t;▼
for (i = 0; i < n; i += 2 * step) {
}
t = cexp(-I * PI * i / n) * out[i + step];
}
▲ buf[i / 2] = out[i] + t;
▲ buf[(i + n)/2] = out[i] - t;
}
}
}
void fft(cplx buf[], int n)
{▼
cplx out[n];
for (int i = 0; i < 8n; i++) out[i] = buf[i];▼
 
void fft _fft(cplx *buf, intout, n, 1);
▲{
cplx *out = malloc(sizeof(cplx) * n);
memcpy(out, buf, sizeof(cplx) * n);
_fft(buf, out, n, 1);
free(out);
}
 
int main()
{
PI = atan2(1, 1) * int i4;
cplx buf[] = {1, 1, 1, 1, 0, 0, 0, 0};▼
 
PI = atan2(1., 1.) * 4;
▲ cplx buf[] = {1, 1, 1, 1, 0, 0, 0, 0};
 
▲ for (i = 0; i < 8; i++)
printf("%g + %g i\n", creal(buf[i]), cimag(buf[i]));▼
 
fft(buf, 8);▼
printf("\nAfter FFT:\n");
for (i = 0; i < 8; i++)▼
printf("%g + %g i\n", creal(buf[i]), cimag(buf[i]));▼
 
void show(char * s) {
return 0;▼
printf(s);
}</lang>Output:<lang>1 + 0 i▼
▲ for (int i = 0; i < 8; i++)
1 + 0 i
if (!cimag(buf[i]))
1 + 0 i
▲ printf("%g + %g i\n", creal(buf[i]), cimag(buf[i]));
1 + 0 i
else
0 + 0 i
▲ printf("(%g +, %g) i\n", creal(buf[i]), cimag(buf[i]));
0 + 0 i
}
0 + 0 i
0 + 0 i
show("Data: ");
▲ fft(buf, 8);
show("\nFFT : ");
 
▲ return 0;
After FFT:
▲}</lang>Output:<lang>Data: 1 +1 1 1 0 0 0 0 i
4 + 0 i
FFT : 4 (1, -2.41421) 0 (1, -0.414214) 0 (1, 0.414214) 0 (1, 2.41421)</lang>
1 + -2.41421 i
0 + 0 i
1 + -0.414214 i
0 + 0 i
1 + 0.414214 i
0 + 0 i
1 + 2.41421 i</lang>
 
=={{header|C++}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/171438"