#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;
}
free(W);
}
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;
}
This file works properly as it is: just copy and paste in your computer. Surfing on the web I have found this easy implementation on wikipedia page here. The page is in italian, so I re-wrote the code with some translations. Here there are almost the same informations but in english. ENJOY!
#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;
}
free(W);
}
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;
}
Your best bet is KissFFT - as its name implies it's simple, but it's still quite respectably fast, and a lot more lightweight than FFTW. It's also free, whereas FFTW requires a hefty licence fee if you want to include it in a commercial product.
You could start converting this java snippet to C the author states he has converted it from C based on the book numerical recipies which you find online! here
发布评论
评论（4）
该文件可以正常工作：只需复制并粘贴到您的计算机中即可。
在网上冲浪时，我在维基百科页面此处找到了这个简单的实现。该页面是意大利语，所以我用一些翻译重新编写了代码。 这里有几乎相同的信息，但是是英文的。享受！
This file works properly as it is: just copy and paste in your computer.
Surfing on the web I have found this easy implementation on wikipedia page here. The page is in italian, so I re-wrote the code with some translations. Here there are almost the same informations but in english. ENJOY!
你最好的选择是 KissFFT - 顾名思义，它是 简单，但它仍然相当快，并且比 FFTW 轻得多。它也是免费的，但如果您想将 FFTW 包含在商业产品中，则需要支付高额许可费。
Your best bet is KissFFT - as its name implies it's simple, but it's still quite respectably fast, and a lot more lightweight than FFTW. It's also free, whereas FFTW requires a hefty licence fee if you want to include it in a commercial product.
这里是一个许可许可的 C 库各种不同的 FFT 实现，每个实现都位于其自己的独立 C 文件中。
Here is a permissively-licensed C library with a variety of different FFT implementations, each of which is in its own self-contained C-file.
您可以开始将 这个 java 片段 转换为 C，作者表示他已将其从 C 转换为基于您可以在网上找到的数字食谱这本书！ 此处
You could start converting this java snippet to C the author states he has converted it from C based on the book numerical recipies which you find online! here