ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : €«мп Љ ­в®а                          2:5020/175.2   04 Nov 2002  15:48:43
 To : All
 Subject : БПФ vs БПХ оценки
 -------------------------------------------------------------------------------- 
 

 Hi All,
 
 Разобрался я поконкретнее с оценочками... Что-то странное выходит ;)
 
 В БПФ на каждом уровне рекурсии делается N/2 бабочек, каждая из 4 умножений и
 6 сложений, всего 2N* и 3N+ на уровень.
 
 В БПХ на каждом уровне делается N/4 спаренных бабочки (иначе не "на месте"
 выходит). Каждая спаренная бабочка - это 4 умножения и 6 сложений.
 #define FHT_T2Butterfly(N1,N2,C,S) {\  
   double Rx,Ri;       \
   int i1=N1,i2=N2;     \
   Rx=Right[i1];Ri=Right[i2];    \ 
   {           \  
    double cas1,Lx;    \
    cas1=Rx*(C)+Ri*(S); \ 
    Lx=Left[i1];            \
    Left[i1]  = Lx+cas1;   \  
    Right[i1] = Lx-cas1;    \
   }                             \
   {           \
    double cas2,Li;         \  
    cas2=Rx*(S)-Ri*(C);     \  
    Li=Left[i2];            \
    Left[i2]  = Li+cas2;    \
    Right[i2] = Li-cas2;    \
   }                             \
 }
 Так что всего N умножений и 3N/2 сложений.
 
 Комплексный вектор в 2 раза короче действительного, поэтому БПФ
 действительного вектора состоит также из N умножений и 3N/2 сложений.
 
 Если не учитывать затраты O(N) с малой константой на FFT Real wrapper, то
 получается одинаково...
 
 Или где я неправ ??
 
 --- ifmail v.2.15dev5
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
 
 

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