FFT - faq
- From
- Evgeny Sharandin (2:5020/755.12)
- To
- Ilia Kantor
- Date
- 2002-12-18T01:35Z
- Area
- RU.ALGORITHMS
Reply-To: shar@nep.cplire.ru
Привет Ilia!
14 декабря 2002 года (а было тогда 02:47)
Ilia Kantor в своем письме к Nick Poroshin писал:
IK> А я чуток закомментарю его.. Конструктивной критикой, дабы стал лучше.
IK> Только самое необходимое.
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
IK> Такой точности пи хватит разве что для float.
IK> #define pi 3.141592653589793238462643383
Основная причина громадной погрешности зарыта именно здесь ;)
NP>> cos_ = cos(arg);
NP>> sin_ = sin(arg);
IK> Тормознутые функции..
В современных процесорах кеш-промах обходится дороже.
IK> Лучше брать значения из предварительно созданной
IK> таблицы.
Уже не факт, что лучше. Скорее фифти-фифти.
NP>> u3=u1*cos_-u2*sin_;
NP>> u2=u2*cos_+u1*sin_;
IK> Эта рекуррентная последовательность для тригонометрии приводит к
IK> быстрому росту ошибки. Лучше хранить не сам корень из -1 в виде (cos,
IK> sin), а пару (1-cos, sin). Соответственно, меняется формула.
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> домножать на него.
В данном случае не принципиально. Во-первых, доля затрачиваемого времени на
масштабирование мала. Во-вторых, нет необходимости делать масштабирование при
каждом преобразовании. В-третьих, умный компилятор сам разбертся.
С уважением, Evgeny 18 декабря 2002 года
---
* Origin: LID (2:5020/755.12)