# 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