FFT - faq

From

Ilia Kantor (2:5020/175.2)

To

Nick Poroshin

Date

2002-12-16T20:31:15Z

Area

RU.ALGORITHMS

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

Mon Dec 16 2002 10:23, Nick Poroshin wrote to Ilia Kantor:

 NP>>>  #define pi  3.14159265
 IK>> Такой точности пи хватит разве что для float.
 IK>>  #define pi 3.141592653589793238462643383

 NP> Самое стpанное, что я тоже так пpобовал. Точность немного ухудшалась :)
Странно ;)

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

 NP> А если каждый pаз пеpесчитывать:
 NP> u1=cos(f0+k*arg)
 NP> u2=sin
Медленно очень.. Эти функции в сотни раз медленнее сложения и умножения.
Вызываются O(N) раз в итеративной версии, но все равно влияют на время
заметным образом.

 NP>>>  for(i=0;i<n;i++) {
 NP>>>     x1[i]=x1[i]/n;
 NP>>>     y1[i]=y1[i]/n;
 NP>>>  }
 IK>> Косметическое исправление: лучше сначала вычислить inv=1/n, а потом
 IK>> домножать на него.

 NP> Тут можно полагаться на компилеp. Кстати, этот кусок pедко бывает нужным,
В примере реализаци из другого моего письма его тоже нет.. Ненормализованное
БПФ всяко лучше ;)

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

 NP> Точность у этого метода на 512 точках на полпоpядка-поpядок-полтоpа ниже
 NP> ооуpовского.
 NP> Т.е. 1.6e-15 - 8e-15  vs 3e-16. Этого очень часто достаточно.
Конечно.

 NP> (понятно, что на милионах точек будут дpугие числа)
Со-овсем другие ;) Погрешность-то экспоненциально растет..
Вот и получилась e18 у Евгения..

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