БПФ vs БПХ оценки

From

Илья Кантор (2:5020/175.2)

To

All

Date

2002-11-04T14:48:43Z

Area

RU.ALGORITHMS

From: "Илья Кантор" <ilia@manual.ru>

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)