ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Ilia Kantor                          2:5020/175.2   16 Dec 2002  21:31:15
 To : Nick Poroshin
 Subject : FFT - faq
 -------------------------------------------------------------------------------- 
 

 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едко бывает нужным,
 
 В примере реализаци из другого моего письма его тоже нет.. Hенормализованное
 БПФ всяко лучше ;)
 
  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)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    FFT - faq   Nick Poroshin   10 Dec 2002 21:40:08   FFT - faq   Evgeny Sharandin   13 Dec 2002 03:06:00   FFT - faq   Ilia Kantor   14 Dec 2002 03:37:16   FFT - faq   Evgeny Sharandin   18 Dec 2002 02:27:00   FFT - faq   Nick Poroshin   16 Dec 2002 11:10:21   FFT - faq   Ilia Kantor   16 Dec 2002 21:27:27   FFT - faq   Nick Poroshin   18 Dec 2002 01:23:21   FFT - faq   Ilia Kantor   18 Dec 2002 00:59:27   FFT - faq   Nick Poroshin   18 Dec 2002 05:04:07   Re: FFT - faq   Dmitry Shuklin   18 Dec 2002 13:43:02   FFT - faq   Nick Poroshin   18 Dec 2002 23:56:18   FFT - faq   Ilia Kantor   14 Dec 2002 03:47:33   FFT - faq   Vladimir Vassilevsky   14 Dec 2002 06:55:03   FFT - faq   Ilia Kantor   14 Dec 2002 19:01:03   FFT - faq   Denis Artuhov   14 Dec 2002 17:09:55   Re: FFT - faq   Michael Ryazanov   17 Dec 2002 00:09:00   FFT - faq   Nick Poroshin   16 Dec 2002 11:23:51   FFT - faq   Ilia Kantor   16 Dec 2002 21:31:15   Re: FFT - faq   Michael Ryazanov   17 Dec 2002 00:16:00   FFT - faq   Evgeny Sharandin   18 Dec 2002 02:35:00