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().


SYNAPS DOCUMENTATION
logo