fft_truncated_transformer< C, Ffter > Class Template Reference

#include <fft_truncated.hpp>

List of all members.

Public Types

typedef implementation
< vector_linear, vector_naive > NVec
typedef Ffter::R R
typedef Ffter::U U
typedef Ffter::S S

Public Member Functions

fft_truncated_transformer (nat s, const format< C > &fm)
~fft_truncated_transformer ()
void fft_cross_range (C *lp, C *rp, nat stride, nat shift, nat nr)
void dtft (C *c, nat stride, nat s, nat shift, nat steps)
void itft_flip_range (C *lp, C *rp, nat stride, nat shift, nat nr)
void tft_cross_range (C *lp, C *rp, nat stride, nat shift, nat nr)
void ifft_cross_range (C *lp, C *rp, nat stride, nat shift, nat nr)
void itft (C *c, nat stride, nat s, nat shift, nat steps)
void dtft (C *c, nat stride, nat s, nat shift)
void itft (C *c, nat stride, nat s, nat shift)
void direct_transform (C *c)
void inverse_transform (C *c)

Public Attributes

nat len
Ffter * ffter

Detailed Description

template<typename C, typename Ffter = fft_naive_transformer<C>>
class mmx::fft_truncated_transformer< C, Ffter >

Definition at line 27 of file fft_truncated.hpp.

Member Typedef Documentation

typedef implementation<vector_linear,vector_naive> NVec

Definition at line 29 of file fft_truncated.hpp.

typedef Ffter::R R

Definition at line 30 of file fft_truncated.hpp.

typedef Ffter::S S

Definition at line 32 of file fft_truncated.hpp.

typedef Ffter::U U

Definition at line 31 of file fft_truncated.hpp.

Constructor & Destructor Documentation

fft_truncated_transformer	(	nat	s,
		const format< C > &	fm
	)			`[inline]`

Definition at line 37 of file fft_truncated.hpp.

References fft_truncated_transformer< C, Ffter >::ffter.

00037                                                                : len (s) {
00038     nat n= next_power_of_two (s);
00039     VERIFY(s <= n, "maximum size exceeded");
00040     ffter= new Ffter (n, fm); }

~fft_truncated_transformer ( ) [inline]

Definition at line 42 of file fft_truncated.hpp.

References fft_truncated_transformer< C, Ffter >::ffter.

00042 { delete ffter; }

Member Function Documentation

void direct_transform ( C * c ) [inline]

Definition at line 155 of file fft_truncated.hpp.

References fft_truncated_transformer< C, Ffter >::dtft(), fft_truncated_transformer< C, Ffter >::ffter, and fft_truncated_transformer< C, Ffter >::len.

00155                           {
00156     nat n= ((nat) 1) << ffter->depth;
00157     if (len == n)
00158       ffter->direct_transform (c);
00159     else {
00160       NVec::clear (c + len, n - len);
00161       dtft (c, 1, len, 0);
00162       NVec::clear (c + len, n - len);
00163     }
00164   }

void dtft	(	C *	c,
		nat	stride,
		nat	s,
		nat	shift
	)			`[inline]`

Definition at line 147 of file fft_truncated.hpp.

References fft_truncated_transformer< C, Ffter >::dtft(), and fft_truncated_transformer< C, Ffter >::ffter.

00147                                             {
00148     dtft (c, stride, s, shift, ffter->depth); }

void dtft	(	C *	c,
		nat	stride,
		nat	s,
		nat	shift,
		nat	steps
	)			`[inline]`

Definition at line 61 of file fft_truncated.hpp.

References fft_truncated_transformer< C, Ffter >::fft_cross_range(), and fft_truncated_transformer< C, Ffter >::ffter.

Referenced by fft_truncated_transformer< C, Ffter >::direct_transform(), and fft_truncated_transformer< C, Ffter >::dtft().

00061                                                        {
00062     // In place direct tft of c[0], c[stride], ..., c[(s-1) stride]
00063     // Roots start at roots + (shift<<1)
00064     if (s == 0 || steps == 0) return;
00065     nat todo= steps - 1;
00066     nat w   = (nat) 1 << todo;
00067     fft_cross_range (c, c + (stride<<todo), stride, shift>>todo, w);
00068     steps--;
00069     if (s >= w) {
00070       ffter->dfft (c, stride, shift, steps);
00071       s -= w;  shift += w >> 1;  c += stride<<todo;
00072     }
00073     dtft (c, stride, s, shift, steps);
00074   }

void fft_cross_range	(	C *	lp,
		C *	rp,
		nat	stride,
		nat	shift,
		nat	nr
	)			`[inline]`

Definition at line 46 of file fft_truncated.hpp.

References fft_truncated_transformer< C, Ffter >::ffter.

Referenced by fft_truncated_transformer< C, Ffter >::dtft().

00046                                                                 {
00047     U* a= ffter->roots + (shift << 1);
00048     if (shift == 0)
00049       for (nat i=nr; i!=0; i--) {
00050         R::fft_cross (lp, rp);
00051         lp += stride; rp +=stride;
00052       }
00053     else
00054       for (nat i=nr; i!=0; i--) {
00055         R::dfft_cross (lp, rp, a);
00056         lp += stride; rp += stride;
00057       }
00058   }

void ifft_cross_range	(	C *	lp,
		C *	rp,
		nat	stride,
		nat	shift,
		nat	nr
	)			`[inline]`

Definition at line 108 of file fft_truncated.hpp.

References fft_truncated_transformer< C, Ffter >::ffter.

Referenced by fft_truncated_transformer< C, Ffter >::itft().

00108                                                                  {
00109     U* a= ffter->roots + (shift << 1);
00110     if (shift == 0)
00111       for (nat i=nr; i!=0; i--) {
00112         R::fft_cross (lp, rp);
00113         lp += stride; rp += stride;
00114       }
00115     else
00116       for (nat i=nr; i!=0; i--) {
00117         R::ifft_cross (lp, rp, a+1);
00118         lp += stride; rp += stride;
00119       }
00120   }

void inverse_transform ( C * c ) [inline]

Definition at line 167 of file fft_truncated.hpp.

References binpow(), fft_truncated_transformer< C, Ffter >::ffter, mmx::invert(), fft_truncated_transformer< C, Ffter >::itft(), fft_truncated_transformer< C, Ffter >::len, and mmx::x.

00167                            {
00168     nat n= ((nat) 1) << ffter->depth;
00169     if (len == n)
00170       ffter->inverse_transform (c);
00171     else {
00172       NVec::clear (c + len, n - len);
00173       itft (c, 1, len, 0);
00174       S x= invert (binpow (S (2), ffter->depth));
00175       NVec::template vec_unary_scalar<typename R::fft_mul_sc_op> (c, x, len);
00176       NVec::clear (c + len, n - len);
00177     }
00178   }

void itft	(	C *	c,
		nat	stride,
		nat	s,
		nat	shift
	)			`[inline]`

Definition at line 151 of file fft_truncated.hpp.

References fft_truncated_transformer< C, Ffter >::ffter, and fft_truncated_transformer< C, Ffter >::itft().

00151                                             {
00152     itft (c, stride, s, shift, ffter->depth); }

void itft	(	C *	c,
		nat	stride,
		nat	s,
		nat	shift,
		nat	steps
	)			`[inline]`

Definition at line 123 of file fft_truncated.hpp.

References fft_truncated_transformer< C, Ffter >::ffter, fft_truncated_transformer< C, Ffter >::ifft_cross_range(), fft_truncated_transformer< C, Ffter >::itft_flip_range(), and fft_truncated_transformer< C, Ffter >::tft_cross_range().

Referenced by fft_truncated_transformer< C, Ffter >::inverse_transform(), and fft_truncated_transformer< C, Ffter >::itft().

00123                                                        {
00124     // In place inverse tft of c[0], c[stride], ..., c[(s-1) stride]
00125     // Roots start at roots + (shift<<1)
00126     if (s == 0 || steps == 0) return;
00127     nat todo= steps - 1;
00128     nat l   = (nat) 1 << steps;
00129     nat w   = (nat) 1 << todo;
00130     if (s < w) {
00131       tft_cross_range (c + stride*s, c + stride*(s+w),
00132                        stride, shift>>todo, w-s);
00133       itft (c, stride, s, shift, steps-1);
00134       itft_flip_range (c, c + (stride<<todo), stride, shift>>todo, s);
00135     }
00136     else {
00137       ffter->ifft (c, stride, shift, steps-1);
00138       itft_flip_range (c + stride*(s-w), c + stride*s,
00139                        stride, shift>>todo, l-s);
00140       if (s == w) return;
00141       itft (c + (stride<<todo), stride, s-w, shift + (w>>1), steps-1);
00142       ifft_cross_range (c, c + (stride<<todo), stride, shift>>todo, s-w);
00143     }
00144   }

void itft_flip_range	(	C *	lp,
		C *	rp,
		nat	stride,
		nat	shift,
		nat	nr
	)			`[inline]`

Definition at line 78 of file fft_truncated.hpp.

References fft_truncated_transformer< C, Ffter >::ffter.

Referenced by fft_truncated_transformer< C, Ffter >::itft().

00078                                                                 {
00079     U* a= ffter->roots + (shift << 1);
00080     if (shift == 0)
00081       for (nat i=nr; i!=0; i--) {
00082         R::itft_flip (lp, rp);
00083         lp += stride; rp += stride;
00084       }
00085     else
00086       for (nat i=nr; i!=0; i--) {
00087         R::itft_flip (lp, rp, a);
00088         lp += stride; rp += stride;
00089       }
00090   }

void tft_cross_range	(	C *	lp,
		C *	rp,
		nat	stride,
		nat	shift,
		nat	nr
	)			`[inline]`

Definition at line 93 of file fft_truncated.hpp.

References fft_truncated_transformer< C, Ffter >::ffter.

Referenced by fft_truncated_transformer< C, Ffter >::itft().

00093                                                                 {
00094     U* a= ffter->roots + (shift << 1);
00095     if (shift == 0)
00096       for (nat i=nr; i!=0; i--) {
00097         R::dtft_cross (lp, rp);
00098         lp += stride; rp += stride;
00099       }
00100     else
00101       for (nat i=nr; i!=0; i--) {
00102         R::dtft_cross (lp, rp, a);
00103         lp += stride; rp += stride;
00104       }
00105   }

Member Data Documentation

Ffter* ffter

Definition at line 34 of file fft_truncated.hpp.

nat len

Definition at line 33 of file fft_truncated.hpp.

Referenced by fft_truncated_transformer< C, Ffter >::direct_transform(), and fft_truncated_transformer< C, Ffter >::inverse_transform().

The documentation for this class was generated from the following file:

include/algebramix/fft_truncated.hpp

fft_truncated_transformer< C, Ffter > Class Template Reference

Public Types

Public Member Functions

Public Attributes

Detailed Description

template<typename C, typename Ffter = fft_naive_transformer<C>> class mmx::fft_truncated_transformer< C, Ffter >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename C, typename Ffter = fft_naive_transformer<C>>
class mmx::fft_truncated_transformer< C, Ffter >