FFT在一个单一的C文件的问题?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (28)

我正在C中寻找一个FFT实现。但是,我不是在寻找一个巨大的库(如FFTW),而是一个易于使用的单个C文件实现。

提问于
用户回答回答于

代码如下:

#include <iostream>
#include <complex>
#define MAX 200

using namespace std;

#define M_PI 3.1415926535897932384

int log2(int N)    /*function to calculate the log2(.) of int numbers*/
{
  int k = N, i = 0;
  while(k) {
    k >>= 1;
    i++;
  }
  return i - 1;
}

int check(int n)    //checking if the number of element is a power of 2
{
  return n > 0 && (n & (n - 1)) == 0;
}

int reverse(int N, int n)    //calculating revers number
{
  int j, p = 0;
  for(j = 1; j <= log2(N); j++) {
    if(n & (1 << (log2(N) - j)))
      p |= 1 << (j - 1);
  }
  return p;
}

void ordina(complex<double>* f1, int N) //using the reverse order in the array
{
  complex<double> f2[MAX];
  for(int i = 0; i < N; i++)
    f2[i] = f1[reverse(N, i)];
  for(int j = 0; j < N; j++)
    f1[j] = f2[j];
}

void transform(complex<double>* f, int N) //
{
  ordina(f, N);    //first: reverse order
  complex<double> *W;
  W = (complex<double> *)malloc(N / 2 * sizeof(complex<double>));
  W[1] = polar(1., -2. * M_PI / N);
  W[0] = 1;
  for(int i = 2; i < N / 2; i++)
    W[i] = pow(W[1], i);
  int n = 1;
  int a = N / 2;
  for(int j = 0; j < log2(N); j++) {
    for(int i = 0; i < N; i++) {
      if(!(i & n)) {
        complex<double> temp = f[i];
        complex<double> Temp = W[(i * a) % (n * a)] * f[i + n];
        f[i] = temp + Temp;
        f[i + n] = temp - Temp;
      }
    }
    n *= 2;
    a = a / 2;
  }
}

void FFT(complex<double>* f, int N, double d)
{
  transform(f, N);
  for(int i = 0; i < N; i++)
    f[i] *= d; //multiplying by step
}

int main()
{
  int n;
  do {
    cout << "specify array dimension (MUST be power of 2)" << endl;
    cin >> n;
  } while(!check(n));
  double d;
  cout << "specify sampling step" << endl; //just write 1 in order to have the same results of matlab fft(.)
  cin >> d;
  complex<double> vec[MAX];
  cout << "specify the array" << endl;
  for(int i = 0; i < n; i++) {
    cout << "specify element number: " << i << endl;
    cin >> vec[i];
  }
  FFT(vec, n, d);
  cout << "...printing the FFT of the array specified" << endl;
  for(int j = 0; j < n; j++)
    cout << vec[j] << endl;
  return 0;
}

热门问答

腾讯云广州一区DNS变更,需要怎么操作?

思潮澎湃轻描淡写的生活,但思潮澎湃
推荐
我也收到相关的通知了,这里分享下~ 2019年1月31日,腾讯云将对广州地区旧的基础网络DNS服务器(10.225.30.181、10.225.30.223)进行下线。在此期间,腾讯云提供最新的DNS服务器供您更新使用。 我们建议您尽快将DNS服务器配置进行更新,并且我们为您提供...... 展开详请

快照容量与费用的比例?如何关闭停用?

帅的惊动我国计算机大神
推荐已采纳
快照已于2019年1月22日0时启动正式商业化进程,商业化后所有存量快照和新产生的快照将根据快照使用的存储容量进行收费。 在快照商业化后,腾讯云仍旧会在国内主要地域为用户提供一定量的免费额度。免费额度策略如下: 免费额度覆盖范围为中国大陆地域,中国香港及海外地域暂无免费快照额...... 展开详请

云服务器购买后多久生效能使用?

Eli Qiao

腾讯 · 高级工程师 (已认证)

腾讯云CVM后台高级研发工程师
推荐

如果使用公有镜像,一般 10s 左右后台就可以创建完成。

欠费资源销毁怎么解决?

西风

renzha.net · 站长 (已认证)

www.renzha.net
推荐
当您的账户发生欠费时,对象存储 COS 会在24小时后停止服务,您的数据可以继续保留120天,如果在此期间未进行续费使账户余额大于等于0, 您的数据将会被销毁。 注意: 欠费停服后,数据占用的存储容量会持续计费,直到销毁数据。 销毁数据后,不可恢复。 用户续费使账户余额大于等于...... 展开详请

React项目的try_files机制,在COS上怎么配置?

galenye

腾讯 · 工程师 (已认证)

对象存储专业搬砖工
推荐
COS的静态网站可以设置默认索引,你这里应该是想实现react-router spa场景下刷新浏览器时,不希望报404的场景吧 可以在COS静态网站这设置一个错误文档的默认索引来实现类似try_files的功能 image.png ... 展开详请

用户主动向云服务器的号码发送短信(不是回复),该条消息能否回调给业务服务器?

推荐

您好,主动上行需配置专属上行码号,月发送量大于300万条可申请配置。未配置专属上行码号用户可先下发短信后用户回复。感谢您对腾讯云短信的支持。

所属标签

扫码关注云+社区