Skip to content
The Chat Archive
Human-written demonstration (OpenAssistant volunteers)· OpenAssistant (human-written) OpenAssistant Conversations (oasst2)

帮我写一个C语言FFT函数

In OpenAssistant data, “assistant” turns were written by human volunteers as demonstrations. They are not model outputs.
  1. User

    帮我写一个C语言FFT函数

  2. Assistant

    以下是一个简单的C语言FFT函数:

    #include <math.h> #include <stdlib.h> #include <stdio.h>

    /* 定义复数结构体 */ typedef struct { double real; double imaginary; } Complex;

    /* 复数加法 */ Complex add(Complex a, Complex b) { Complex c; c.real = a.real + b.real; c.imaginary = a.imaginary + b.imaginary; return c; }

    /* 复数减法 */ Complex subtract(Complex a, Complex b) { Complex c; c.real = a.real - b.real; c.imaginary = a.imaginary - b.imaginary; return c; }

    /* 复数乘法 */ Complex multiply(Complex a, Complex b) { Complex c; c.real = a.real * b.real - a.imaginary * b.imaginary; c.imaginary = a.real * b.imaginary + a.imaginary * b.real; return c; }

    /* 计算旋转因子 */ Complex w(int n, int k) { Complex c; c.real = cos(2 * M_PI * k / n); c.imaginary = -sin(2 * M_PI * k / n); return c; }

    /* FFT函数 */ 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 k = 0; k < n / 2; k++) { Complex t = multiply(odd[k], w(n, k)); x[k] = add(even[k], t); x[k + n / 2] = subtract(even[k], t); } free(even); free(odd); } 这个FFT函数使用递归的方式实现快速傅里叶变换,其中包含了复数结构体的定义以及复数的基本计算函数。在使用时,只需要传入一个复数数组和数组的长度,即可计算出该数组的FFT结果。 或者这眼的C语言FFT函数:

    #include <stdio.h> #include <stdlib.h>

    // Define the size of the arrays to be used for input and output values #define N 1024

    void fft(complex *x) { int i, j; complex c[N];

    // Transform x[] into c[]. The real parts are in even elements, the imaginary part in odd ones
    for (i = 0; i < N/2; i++)
        c[i] = x[2*i];   // Real part
    for (j = 1; j <= N/2; ++j)
        c[j] = x[2*j-1]+x[2*j];  // Imaginary part
    
    // Perform the actual transformation using divide-and-conquer approach
    fftRecur(x, &c[1], N);
    

    }

    void fftRecur(complex *x, complex *c, long n) { if (n == 1) return;

    // Divide the Fourier matrix into four submatrices
    complex X[4][4];
    
    // First perform forward transform on each row separately
    for (int k = 0; k < n/2; ++k)
      xtranspose(&X[0][k], x[4*k], n);
        
    // Then do the same thing with conjugate transposes
    for (int l = n/2; l < n; ++l)
      xtranspose(&X[3][l], x[4*(n/2)+l], n);
    
    // Combine these partial results by reversing rows
    for (int i=0; i<n/2; i++)
        memcpy(&x[i+n/4], &X[(i%2)*2][n/4], sizeof(*x));
        
    // Next, call recursive routine on all four subproblems
    fftRecur(c, x, (long)(n/2));
    

    }

    void xtranspose(complex *A, complex *B, long m) { long i, j;

    for (i = 0; i < m; i++)
      for (j = i+1; j < m; j++)
        swap(&A[i][j], &A[j][i]);
    

    }

    int main() { complex x[N]; complex y[N];

    /* Initialize array */
    init_array();
    
    /* Compute FFT and store result in y[] */
    fft(x);
    
    /* Print out the first few coefficients of the transformed signal */
    printf("Transformed signal:\n");
    print_array(y, N);
    
    return 0;
    

    }``` 请注意,此代码使用了一些辅助函数(init_array,`print_array'),此处未显示这些函数。根据应用程序将如何使用FFT函数,应根据需要实现这些函数。

    还要注意,可能有更有效的实现可用,但这一个只是简单的介绍

  3. User

    非常好,太感谢了!

  4. Assistant

    不客气,如果你还有其他需要我帮忙的地方,欢迎随时找我

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.