FFT (Fast Fourier Transform) 是一种高效计算离散傅里叶变换的算法。在 C 语言中，实现 FFT 算法通常需要用到复数和递归。
下面是一个简单的 C 语言代码实现 FFT 算法：
- #include <math.h>
- #include <stdio.h>
- #include <stdlib.h>
- #define PI 3.14159265358979323846
- typedef struct {
- double real, imag;
- } Complex;
- Complex add(Complex a, Complex b) {
- Complex result = { a.real + b.real, a.imag + b.imag };
- return result;
- }
- Complex subtract(Complex a, Complex b) {
- Complex result = { a.real - b.real, a.imag - b.imag };
- return result;
- }
- Complex multiply(Complex a, Complex b) {
- Complex result = { a.real * b.real - a.imag * b.imag, a.real * b.imag + a.imag * b.real };
- return result;
- }
- void fft(Complex *x, int n) {
- if (n == 1) {
- return;
- }
- Complex *even = (Complex*) malloc(n / 2 * sizeof(Complex));
- Complex *odd = (Complex*) malloc(n / 2 * sizeof(Complex));
- for (int i = 0; i < n / 2; i++) {
- even[i] = x[2 * i];
- odd[i] = x[2 * i + 1];
- }
- fft(even, n / 2);
- fft(odd, n / 2);
- for (int i = 0; i < n / 2; i++) {
- Complex t = multiply(odd[i], (Complex) { cos(-2 * PI * i / n), sin(-2 * PI * i / n) });
- x[i] = add(even[i], t);
- x[i + n / 2] = subtract(even[i], t);
- }
- free(even);
- free(odd);
- }
- int main() {
- int n = 8;
- Complex x[] = { {1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {6, 0}, {7, 0}, {8, 0} };
- fft(x, n);
- printf("FFT:\n");
- for (int i = 0; i < n; i++) {
- printf("%f + %fi\n", x[i].real, x[i].imag);
- }
- return 0;
- }
| 
楼主
