synaps/linalg/FFT.h File Reference

---

Detailed Description

Generic Fast Fourier Transform.

Definition in file FFT.h.

Go to the source code of this file.

Functions
template<class T>
void	Root_Unity (std::complex< T > &c, int n)
	Root of Unity. Replace c by the primitive root of order n.
unsigned int	BitReverse (int k, int n)
template<class T>
void	Permut (T *Tab, int N)
	Shuflle on N entries.
template<class C, class U>
void	FFT (int n, const std::complex< U > &w, std::complex< C > *W, int inverse)

---

Function Documentation

unsigned int BitReverse	(	int	k,
		int	n
	)

Functions which permute an array by Bit Reversal method.

Definition at line 28 of file FFT.h.

Referenced by Permut().

template<class C, class U>

void FFT	(	int	n,
		const std::complex< U > &	w,
		std::complex< C > *	W,
		int	inverse
	)

Implementation of { FFT } computation of a complex array. It is an "in-place" transformation, based on the Butterfly algorithm. A complex array W, of size n (a power of 2), is replaced by the FFT of its values. The complex number w is a primitive root of unity of order $n$.

Definition at line 62 of file FFT.h.

Referenced by UPOL::mul_fft().

template<class T>

void Permut	(	T *	Tab,
		int	N
	)

Shuflle on N entries.

Definition at line 43 of file FFT.h.

References BitReverse().

Referenced by UPOL::mul_fft().

template<class T>

void Root_Unity	(	std::complex< T > &	c,
		int	n
	)

Root of Unity. Replace c by the primitive root of order n.

Definition at line 20 of file FFT.h.

Referenced by UPOL::mul_fft().