#include <fft_naive.hpp>

Public Types

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

Public Member Functions

fft_naive_transformer (nat n)
~fft_naive_transformer ()
void dfft (C *c, nat stride, nat shift, nat steps, nat step1, nat step2)
void ifft (C *c, nat stride, nat shift, nat steps, nat step1, nat step2)
void dfft (C *c, nat stride, nat shift, nat steps)
void ifft (C *c, nat stride, nat shift, nat steps)
void direct_transform (C *c)
void inverse_transform (C *c, bool divide=true)

Public Attributes

nat depth
nat len
U * roots

Detailed Description

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

Examples:: fft_test.cpp, and tft_test.cpp.

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 ) [inline]

Definition at line 111 of file fft_naive.hpp.

References fft_naive_transformer< C, V >::depth.

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

~fft_naive_transformer ( ) [inline]

Definition at line 115 of file fft_naive.hpp.

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

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

Member Function Documentation

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

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

                                                                      {
    // In place direct fft of c[0], c[stride], ..., c[(2^steps-1) stride]
    // Only perform steps from step1 until step2-1
    // If shift != 0, then roots start at roots + (shift<<1)
    for (nat step= step1; step < step2; step++) {
      //mmout << "step " << step << ": " << flush_now;
      if (step == 0 && shift == 0) {
        nat todo= steps - 1;
        C* cc= c;
        for (nat k= 0; k < ((nat) 1<<todo); k++) {
          R::fft_cross (cc, cc + (stride<<todo));
          cc += stride;
        }
      }
      else {
        nat todo= steps - 1 - step;
        C* cc= c;
        U * uu= roots + ((shift >> todo) << 1);
        for (nat j= 0; j < ((nat) 1<<step); j++) {
          for (nat k= 0; k < ((nat) 1<<todo); k++) {
            R::dfft_cross (cc, cc + (stride<<todo), uu);
            cc += stride;
          }
          cc += (stride<<todo);
          uu += 2;
        }
      }
    }
  }

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

Definition at line 181 of file fft_naive.hpp.

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

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

void direct_transform ( C * c ) [inline]

Definition at line 189 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 implementation< series_multiply, U, series_fast >::nrelax_mul_series_rep< C, V >::direct_transform().

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

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

Definition at line 185 of file fft_naive.hpp.

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

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

                                                                      {
    // In place inverse fft of c[0], c[stride], ..., c[(2^steps-1) stride]
    // Only perform steps from step2-1 until step1
    // If shift != 0, then roots start at roots + (shift<<1)
    for (int step= step2-1; (int) step >= ((int) step1); step--) {
      //mmout << "step " << step << ": " << flush_now;
      if (step == 0 && shift == 0) {
        nat todo= steps - 1;
        C* cc= c;
        for (nat k= 0; k < ((nat) 1<<todo); k++) {
          R::fft_cross (cc, cc + (stride<<todo));
          cc += stride;
        }
      }
      else {
        nat todo= steps - 1 - step;
        C* cc= c;
        U * uu= roots + 1 + ((shift >> todo) << 1);
        for (nat j= 0; j < ((nat) 1<<step); j++) {
          for (nat k= 0; k < ((nat) 1<<todo); k++) {
            R::ifft_cross (cc, cc + (stride<<todo), uu);
            cc += stride;
          }
          cc += (stride<<todo);
          uu += 2;
        }
      }
    }
  }

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

Definition at line 193 of file fft_naive.hpp.

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

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

                                             {
    ifft (c, 1, 0, depth);
    if (divide) {
      S x= binpow (S (2), depth);
      x= invert (x);
      NVec::template vec_unary_scalar<typename R::fft_mul_sc_op> (c, x, len);
    }
  }