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 99 of file fft_naive.hpp.

Member Typedef Documentation

typedef implementation<vector_linear,vector_naive> NVec

Definition at line 101 of file fft_naive.hpp.

typedef V::roots_type R

Definition at line 102 of file fft_naive.hpp.

typedef R::S S

Definition at line 104 of file fft_naive.hpp.

typedef R::U U

Definition at line 103 of file fft_naive.hpp.

Constructor & Destructor Documentation

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

Definition at line 112 of file fft_naive.hpp.

References fft_naive_transformer< C, V >::depth.

00112                                                             :
00113     fm (fm2),
00114     depth (log_2 (n)), len (n), roots (R::create_roots (n, fm)) {
00115     VERIFY (n == ((nat) 1 << depth), "power of two expected"); }

~fft_naive_transformer (  )  [inline]

Definition at line 117 of file fft_naive.hpp.

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

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

Member Function Documentation

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

Definition at line 183 of file fft_naive.hpp.

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

00183                                                 {
00184     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 121 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().

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

void direct_transform ( C *  c  )  [inline]

Definition at line 191 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().

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

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

Definition at line 187 of file fft_naive.hpp.

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

00187                                                 {
00188     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 152 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().

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

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

Definition at line 195 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().

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

Member Data Documentation

nat depth

Definition at line 107 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 106 of file fft_naive.hpp.

nat len

Definition at line 108 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 109 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 6 Dec 2012 for algebramix by  doxygen 1.6.1