リソースモニターでは、負荷はかかっていなかったのだが？
まぁいい、どうせウイルスバスターだろう。
気になったので実数と虚数を個別の配列にしたパターンを試してみた。
sin,cosテーブル不使用。
ソース
void *fft(int nx ,double ar[],double ai[])
{
int i, k, m, n;
double tmpr, tmpi, r, cosw, sinw;
n = 1<<nx;
r = -M_PI / (double)n;
for(m = n/2; m > 0 ; m /= 2 ) {
r *= 2;
for(k = 0 ; k < m; k++) {
cosw = cos(r*(double)k);
sinw = sin(r*(double)k);
for(i= k ; i < n; i += m*2) {
tmpr = ar[i] - ar[m+i];
tmpi = ai[i] - ai[m+i];
ar[i] = ar[i] + ar[m+i];
ai[i] = ai[i] + ai[m+i];
ar[m+i] = tmpr * cosw - tmpi * sinw;
ai[m+i] = tmpi * cosw + tmpr * sinw;
}
}
}
return;
}
/* ===== ifft ======== */
void *ifft(int nx,double ar[],double ai[])
{
int i, k, m,n;
double tmpr, tmpi, r, cosw, sinw;
n = 1<< nx ;
r = M_PI ;
for(m = 1; m < n ; m *= 2 ) {
for(k = 0; k < m; k++) {
cosw = cos(r*(double)k);
sinw = sin(r*(double)k);
for(i= k ; i < n; i += m*2) {
tmpr = cosw * ar[m+i] - sinw * ai[m+i];
tmpi = cosw * ai[m+i] + sinw * ar[m+i];
ar[m+i] = ar[i] - tmpr ;
ai[m+i] = ai[i] - tmpi;
ar[i] = ar[i] + tmpr ;
ai[i] = ai[i] + tmpi;
}
}
r *= 0.5;
}
return;
}
|
結果
No.0 n=67108864=1<<26 radix=1000 fft 64.316458 , r_mul -------- , ifft 65.452309 , error -------- No.1 n=67108864=1<<26 radix=1000 fft 39.964405 , r_mul 5.791993 , ifft 38.881574 , error 0.085938 No.2 n=67108864=1<<26 radix=1000 fft 38.348005 , r_mul 5.744716 , ifft 41.086747 , error 0.085938 No.3 n=67108864=1<<26 radix=1000 fft 3.771606 , r_mul 4.460116 , ifft 4.872133 , error 0.046875 No.4 n=67108864=1<<26 radix=1000 fft 3.780859 , r_mul 3.618985 , ifft 4.872954 , error 0.046875 No.5 n=67108864=1<<26 radix=1000 fft 3.802325 , r_mul 1.972648 , ifft 4.882619 , error 0.046875 No.6 n=67108864=1<<26 radix=1000 fft 3.779546 , r_mul 0.482001 , ifft 4.864007 , error 0.046875 No.7 n=67108864=1<<26 radix=1000 fft 2.680603 , r_mul 0.491500 , ifft 4.124678 ,error 0.046875 No.8 n=67108864=1<<26 radix=1000 fft 0.814415 , r_mul 0.132398 , ifft 1.112991 ,error 0.046875 |
fft,ifftの測定のみに特化しているため r_mul と error は、比較出来ない。
No.8 は、fft,ifft,r_mul の内部をスレッド化したもの。ソースが酷い事になっているので整理中。
No.1 の構造体と比べ倍遅い。
nを小さくした場合
No.0 n=65536=1<<16 radix=1000 fft 0.009721 , r_mul -------- , ifft 0.010200 , error -------- No.1 n=65536=1<<16 radix=1000 fft 0.006810 , r_mul 0.001947 , ifft 0.007225 , error 0.000053 No.3 n=65536=1<<16 radix=1000 fft 0.001549 , r_mul 0.001122 , ifft 0.001413 , error 0.000023 |
No.1 の構造体と比べ n が小さければ、差は少なくなる。
No.3 sin,cos のテーブル化は有効だが、n=1<<26 のように１０倍近く速くなる訳では無い。
No.3 の誤差(error)が小さいのは、sin,cos を求める範囲を０～π／４にしたため。
