//
//??FFT.c
//??hello_c_mac
//
//??Created?by?callon?on?5/8/16.
//??Copyright???2016?callon.?All?rights?reserved.
//

#include?“math.h“
#include?“FFT.h“
///////////////////////////////////////
void?conjugate_complex（int?ncomplex?in[]complex?out[]）
{
????int?i?=?0;
????for（i=0;i????{
????????out[i].imag?=?-in[i].imag;
????????out[i].real?=?in[i].real;
????}
}
///////////////////////////////////////
void?c_abs（complex?f[]float?out[]int?n）
{
????int?i?=?0;
????float?t;
????for（i=0;i????{
????????t?=?f[i].real?*?f[i].real?+?f[i].imag?*?f[i].imag;
????????out[i]?=?sqrt（t）;
????}
}
///////////////////////////////////////
void?c_plus（complex?acomplex?bcomplex?*c）
{
????c->real?=?a.real?+?b.real;
????c->imag?=?a.imag?+?b.imag;
}
///////////////////////////////////////
void?c_sub（complex?acomplex?bcomplex?*c）
{
????c->real?=?a.real?-?b.real;
????c->imag?=?a.imag?-?b.imag;
}
////////////////////////////////////////
void?c_mul（complex?acomplex?bcomplex?*c）
{
????c->real?=?a.real?*?b.real?-?a.imag?*?b.imag;
????c->imag?=?a.real?*?b.imag?+?a.imag?*?b.real;
}
////////////////////////////////////////
void?c_div（complex?acomplex?bcomplex?*c）
{
????c->real?=?（a.real?*?b.real?+?a.imag?*?b.imag）/（b.real?*?b.real?+b.imag?*?b.imag）;
????c->imag?=?（a.imag?*?b.real?-?a.real?*?b.imag）/（b.real?*?b.real?+b.imag?*?b.imag）;
}
/////////////////////////////////////////
#define?SWAP（ab）??tempr=（a）;（a）=（b）;（b）=tempr

void?Wn_i（int?nint?icomplex?*Wn）
{
????Wn->real?=?cos（2*PI*i/n）;
????Wn->imag?=?-sin（2*PI*i/n）;
}

void?callon_fft（int?Ncomplex?x[]）
{
????complex?twn;
????int?ijkmnlrM;
????int?lalblc;
????
????for（i=NM=1;（i>>=1）!=1;M++）;
????
????for（i=1j=N>>1;i<=N-2;i++）
????{
????????if（i????????{
????????????t=x[j];
????????????x[j]=x[i];
????????????x[i]=t;
????????}
????????k=N>>1;
????????while（k<=j）
????????{
????????????j=j-k;
????????????k>>=1;
????????}
????????j=j+k;
????}
????
????for（m=1;m<=M;m++）
????{
????????la=1<????????lb=la>>1;
????????
????????for（l=1;l<=lb;l++）
????????{
????????????r=（l-1）*（1<<（M-m））;
????????????for（n=l-1;n????????????{
????????????????lc=n+lb;
????????????????Wn_i（Nr&wn）;
????????????????c_mul（x[lc]wn&t）;
????????????????c_sub（x[n]t&（x[lc]））;
????????????????c_plus（x[n]t&（x[n]））;
????????????}
????????????
????????}
????}
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2016-01-31?09:18??hello_c_mac\
?????文件????????6148??2016-05-08?19:57??hello_c_mac\.DS_Store
?????目錄???????????0??2016-05-09?22:34??__MACOSX\
?????目錄???????????0??2016-05-09?22:34??__MACOSX\hello_c_mac\
?????文件?????????120??2016-05-08?19:57??__MACOSX\hello_c_mac\._.DS_Store
?????目錄???????????0??2016-05-08?19:52??hello_c_mac\.git\
?????文件??????????15??2016-01-31?09:16??hello_c_mac\.git\COMMIT_EDITMSG
?????文件?????????137??2016-01-31?09:16??hello_c_mac\.git\config
?????文件??????????73??2016-01-31?09:16??hello_c_mac\.git\description
?????文件??????????23??2016-01-31?09:16??hello_c_mac\.git\HEAD
?????目錄???????????0??2016-01-31?09:16??hello_c_mac\.git\hooks\
?????文件?????????177??2016-01-31?09:16??hello_c_mac\.git\hooks\README.sample
?????文件????????1057??2016-05-08?19:05??hello_c_mac\.git\index
?????目錄???????????0??2016-01-31?09:16??hello_c_mac\.git\info\
?????文件??????????40??2016-01-31?09:16??hello_c_mac\.git\info\exclude
?????目錄???????????0??2016-05-09?22:34??__MACOSX\hello_c_mac\.git\
?????目錄???????????0??2016-05-09?22:34??__MACOSX\hello_c_mac\.git\info\
?????文件?????????171??2016-01-31?09:16??__MACOSX\hello_c_mac\.git\info\._exclude
?????目錄???????????0??2016-01-31?09:16??hello_c_mac\.git\logs\
?????文件?????????174??2016-01-31?09:16??hello_c_mac\.git\logs\HEAD
?????目錄???????????0??2016-01-31?09:16??hello_c_mac\.git\logs\refs\
?????目錄???????????0??2016-01-31?09:16??hello_c_mac\.git\logs\refs\heads\
?????文件?????????174??2016-01-31?09:16??hello_c_mac\.git\logs\refs\heads\master
?????目錄???????????0??2016-05-08?19:04??hello_c_mac\.git\objects\
?????目錄???????????0??2016-01-31?09:16??hello_c_mac\.git\objects\14\
?????文件?????????131??2016-01-31?09:16??hello_c_mac\.git\objects\14\e0b7cb4e6711a66d992c7a710bc108c777047c
?????目錄???????????0??2016-01-31?09:16??hello_c_mac\.git\objects\1a\
?????文件?????????137??2016-01-31?09:16??hello_c_mac\.git\objects\1a\c0f8ada4fe87f1fd955fe31a927b876d544b09
?????目錄???????????0??2016-01-31?09:16??hello_c_mac\.git\objects\1c\
?????文件??????????69??2016-01-31?09:16??hello_c_mac\.git\objects\1c\3ea215bf0ffd498e7731977b3ca88e47f3c15e
?????目錄???????????0??2016-01-31?09:16??hello_c_mac\.git\objects\36\
............此處省略54個文件信息