fft_naive_transformer< C, V > Class Template Reference

#include <fft_naive.hpp>

List of all members.

Public Types

Public Member Functions

Public Attributes

Detailed Description

template<typename C, typename V = std_roots<C>>
class mmx::fft_naive_transformer< C, V >

Definition at line 98 of file fft_naive.hpp.

Member Typedef Documentation

typedef implementation<vector_linear,vector_naive> NVec

Definition at line 100 of file fft_naive.hpp.

typedef V::roots_type R

Definition at line 101 of file fft_naive.hpp.

typedef R::S S

Definition at line 103 of file fft_naive.hpp.

typedef R::U U

Definition at line 102 of file fft_naive.hpp.

Constructor & Destructor Documentation

fft_naive_transformer ( nat  n,
const format< C > &  fm2 
) [inline]

Definition at line 111 of file fft_naive.hpp.

References fft_naive_transformer< C, V >::depth.

00111                                                             :
00112     fm (fm2), depth (log_2 (n)), len (n),
00113     roots (R::create_roots (n, format<U> (no_format ()))) { // FIXME
00114     VERIFY (n == ((nat) 1 << depth), "power of two expected"); }

~fft_naive_transformer (  )  [inline]

Definition at line 116 of file fft_naive.hpp.

References fft_naive_transformer< C, V >::len, and fft_naive_transformer< C, V >::roots.

00116                                    {
00117     R::destroy_roots (roots, len); }

Member Function Documentation

void dfft ( C *  c,
nat  stride,
nat  shift,
nat  steps 
) [inline]

Definition at line 182 of file fft_naive.hpp.

References fft_naive_transformer< C, V >::dfft().

00182                                                 {
00183     dfft (c, stride, shift, steps, 0, steps); }

void dfft ( C *  c,
nat  stride,
nat  shift,
nat  steps,
nat  step1,
nat  step2 
) [inline]

Definition at line 120 of file fft_naive.hpp.

References mmx::C, and fft_naive_transformer< C, V >::roots.

Referenced by fft_naive_transformer< C, V >::dfft(), and fft_naive_transformer< C, V >::direct_transform().

00120                                                                       {
00121     // In place direct fft of c[0], c[stride], ..., c[(2^steps-1) stride]
00122     // Only perform steps from step1 until step2-1
00123     // If shift != 0, then roots start at roots + (shift<<1)
00124     for (nat step= step1; step < step2; step++) {
00125       //mmout << "step " << step << ": " << flush_now;
00126       if (step == 0 && shift == 0) {
00127         nat todo= steps - 1;
00128         C* cc= c;
00129         for (nat k= 0; k < ((nat) 1<<todo); k++) {
00130           R::fft_cross (cc, cc + (stride<<todo));
00131           cc += stride;
00132         }
00133       }
00134       else {
00135         nat todo= steps - 1 - step;
00136         C* cc= c;
00137         U * uu= roots + ((shift >> todo) << 1);
00138         for (nat j= 0; j < ((nat) 1<<step); j++) {
00139           for (nat k= 0; k < ((nat) 1<<todo); k++) {
00140             R::dfft_cross (cc, cc + (stride<<todo), uu);
00141             cc += stride;
00142           }
00143           cc += (stride<<todo);
00144           uu += 2;
00145         }
00146       }
00147     }
00148   }

void direct_transform ( C *  c  )  [inline]

Definition at line 190 of file fft_naive.hpp.

References fft_naive_transformer< C, V >::depth, and fft_naive_transformer< C, V >::dfft().

Referenced by mmx::direct_fft(), and nrelax_mul_series_rep< C, V >::direct_transform().

00190                           {
00191     dfft (c, 1, 0, depth); }

void ifft ( C *  c,
nat  stride,
nat  shift,
nat  steps 
) [inline]

Definition at line 186 of file fft_naive.hpp.

References fft_naive_transformer< C, V >::ifft().

00186                                                 {
00187     ifft (c, stride, shift, steps, 0, steps); }

void ifft ( C *  c,
nat  stride,
nat  shift,
nat  steps,
nat  step1,
nat  step2 
) [inline]

Definition at line 151 of file fft_naive.hpp.

References mmx::C, and fft_naive_transformer< C, V >::roots.

Referenced by fft_naive_transformer< C, V >::ifft(), and fft_naive_transformer< C, V >::inverse_transform().

00151                                                                       {
00152     // In place inverse fft of c[0], c[stride], ..., c[(2^steps-1) stride]
00153     // Only perform steps from step2-1 until step1
00154     // If shift != 0, then roots start at roots + (shift<<1)
00155     for (int step= step2-1; (int) step >= ((int) step1); step--) {
00156       //mmout << "step " << step << ": " << flush_now;
00157       if (step == 0 && shift == 0) {
00158         nat todo= steps - 1;
00159         C* cc= c;
00160         for (nat k= 0; k < ((nat) 1<<todo); k++) {
00161           R::fft_cross (cc, cc + (stride<<todo));
00162           cc += stride;
00163         }
00164       }
00165       else {
00166         nat todo= steps - 1 - step;
00167         C* cc= c;
00168         U * uu= roots + 1 + ((shift >> todo) << 1);
00169         for (nat j= 0; j < ((nat) 1<<step); j++) {
00170           for (nat k= 0; k < ((nat) 1<<todo); k++) {
00171             R::ifft_cross (cc, cc + (stride<<todo), uu);
00172             cc += stride;
00173           }
00174           cc += (stride<<todo);
00175           uu += 2;
00176         }
00177       }
00178     }
00179   }

void inverse_transform ( C *  c,
bool  divide = true 
) [inline]

Definition at line 194 of file fft_naive.hpp.

References binpow(), fft_naive_transformer< C, V >::depth, fft_naive_transformer< C, V >::ifft(), mmx::invert(), fft_naive_transformer< C, V >::len, and mmx::x.

Referenced by mmx::inverse_fft(), and nrelax_mul_series_rep< C, V >::inverse_transform().

00194                                              {
00195     ifft (c, 1, 0, depth);
00196     if (divide) {
00197       S x= binpow (S (2), depth);
00198       x= invert (x);
00199       NVec::template vec_unary_scalar<typename R::fft_mul_sc_op> (c, x, len);
00200     }
00201   }

Member Data Documentation

nat depth

Definition at line 106 of file fft_naive.hpp.

Referenced by fft_naive_transformer< C, V >::direct_transform(), fft_naive_transformer< C, V >::fft_naive_transformer(), and fft_naive_transformer< C, V >::inverse_transform().

format<C> fm

Definition at line 105 of file fft_naive.hpp.

nat len

Definition at line 107 of file fft_naive.hpp.

Referenced by fft_naive_transformer< C, V >::inverse_transform(), and fft_naive_transformer< C, V >::~fft_naive_transformer().

U* roots

Definition at line 108 of file fft_naive.hpp.

Referenced by fft_naive_transformer< C, V >::dfft(), fft_naive_transformer< C, V >::ifft(), and fft_naive_transformer< C, V >::~fft_naive_transformer().

The documentation for this class was generated from the following file:
Generated on 20 Mar 2013 for algebramix by  doxygen 1.6.1