FFT - faq

From

Ilia Kantor (2:5020/175.2)

To

Nick Poroshin

Date

2002-12-14T02:47:33Z

Area

RU.ALGORITHMS

From: "Ilia Kantor" <ilia@manual.ru>

Tue Dec 10 2002 20:40, Nick Poroshin wrote to All:

 NP> Пpедлагаю подпpавленный ваpиант-ляпы подпpавлены и сделано, чтобы массивы
 NP> начинались с 0(а не 1)-так имо удобнее.

А я чуток закомментарю его.. Конструктивной критикой, дабы стал лучше.
Только самое необходимое.

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

 NP> void fft(double *x1,double *y1,int n,int m,int dir)
 NP> {
 NP>  #define pi  3.14159265
Такой точности пи хватит разве что для float. 
 #define pi 3.141592653589793238462643383

 NP> cos_ = cos(arg);
 NP> sin_ = sin(arg);
Тормознутые функции.. Лучше брать значения из предварительно созданной
таблицы.

 NP>     u3=u1*cos_-u2*sin_;
 NP>     u2=u2*cos_+u1*sin_;
Эта рекуррентная последовательность для тригонометрии приводит к быстрому
росту ошибки. Лучше хранить не сам корень из -1 в виде (cos, sin), а пару
(1-cos, sin). Соответственно, меняется формула.

 NP>  for(i=0;i<n;i++) {
 NP>     x1[i]=x1[i]/n;
 NP>     y1[i]=y1[i]/n;
 NP>  }

Косметическое исправление: лучше сначала вычислить inv=1/n, а потом домножать
на него.

Конечно, ничего этого не нужно, если точек 256, а потеря точности типа 1e-5 не
волнует.

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)