fkt_package< V > Struct Template Reference

#include <fkt_transform.hpp>

List of all members.

Public Types

• typedef implementation
  < polynomial_multiply, V > Pol
• typedef Pol::Vec Vec

Static Public Member Functions

• template<class C > static void direct_fkt_step (C *dest, nat n)
• template<class C > static void direct_fkt (C *dest, nat n2, nat n3)
• template<class C > static void inverse_fkt_step (C *dest, nat n, nat l)
• template<class C > static void inverse_fkt (C *dest, nat n3, nat n2)

---

Detailed Description

template<typename V>
struct mmx::fkt_package< V >

Definition at line 21 of file fkt_transform.hpp.

---

Member Typedef Documentation

typedef implementation<polynomial_multiply,V> Pol

Definition at line 22 of file fkt_transform.hpp.

typedef Pol::Vec Vec

Definition at line 23 of file fkt_transform.hpp.

---

Member Function Documentation

static void direct_fkt	(	C *	dest,
		nat	n2,
		nat	n3
	)			[inline, static]

Definition at line 35 of file fkt_transform.hpp.

References mmx::C, and fkt_package< V >::direct_fkt_step().

                                     {
  // dest of length n2 = 2^p on entry and n3 = 3^p on exit
  if (n2 == 2) {
    dest[2]= dest[1];
    dest[1] += dest[0];
  }
  else if (n2 == 4) {
    C p= dest[0] + dest[1];
    C q= dest[2] + dest[3];
    dest[6]= dest[2];
    dest[2]= dest[1];
    dest[8]= dest[3];
    dest[1]= p;
    dest[3]= dest[0] + dest[6];
    dest[4]= p+q;
    dest[5]= dest[2] + dest[8];
    dest[7]= q;
  }
  else while (n2 != n3) {
    direct_fkt_step (dest, n2);
    n2= n2 + (n2 >> 1);
  }
}

static void direct_fkt_step	(	C *	dest,
		nat	n
	)			[inline, static]

Definition at line 26 of file fkt_transform.hpp.

Referenced by fkt_package< V >::direct_fkt().

                                 {
  // dest of length n on entry and 3n/2 on exit
  nat h= n >> 1;
  Vec::half_copy (dest + n, dest + 1, h);
  Vec::half_copy (dest + 1, dest + 2, h - 1);
  Pol::add (dest + h, dest, dest + n, h);
}

static void inverse_fkt	(	C *	dest,
		nat	n3,
		nat	n2
	)			[inline, static]

Definition at line 86 of file fkt_transform.hpp.

References mmx::C, and fkt_package< V >::inverse_fkt_step().

                                      {
  // dest of length n3 = 3^p on entry and 2 n2 - 1 on exit with n2 = 2 ^ p
  if (n2 == 2)
    dest[1] -= (dest[0] + dest[2]);
  else if (n2 == 4) {
    dest[3] -= (dest[0] + dest[6]);
    dest[4] -= (dest[1] + dest[7]);
    dest[5] -= (dest[2] + dest[8]);
    C aux= dest[1]; dest[1]= dest[3]; dest[3]= aux;
    aux= dest[2]; dest[2]= dest[6]; dest[6]= aux;
    aux= dest[5]; dest[5]= dest[7]; dest[7]= aux;
    dest[3] -= (dest[0] + dest[6]);
    dest[4] -= (dest[1] + dest[7]);
    dest[5] -= (dest[2] + dest[8]);
    aux= dest[1];
    dest[1]= dest[3];
    dest[3]= dest[4];
    dest[4]= dest[2] + dest[7];
    dest[2]= aux + dest[6];
    dest[6]= dest[8];
  }
  else {
    nat n= n3, l= 1;
    while (n != l) {
      inverse_fkt_step (dest, n, l);
      nat k= n / ((l << 1) + l);
      l= (l << 1) + 1;
      n= k * l;
    }
  }
}

static void inverse_fkt_step	(	C *	dest,
		nat	n,
		nat	l
	)			[inline, static]

Definition at line 60 of file fkt_transform.hpp.

References mmx::C, and mmx::copy().

Referenced by fkt_package< V >::inverse_fkt().

                                         {
  // dest of length n = 3 k l on entry for some integer k
  // dest of length (2 l + 1) k on exit
  nat t= n/3, k= t/l, ll= (l << 1) + 1;
  Pol::sub (dest + t, dest, t);
  Pol::sub (dest + t, dest + (t << 1), t);
  nat buf_size= aligned_size<C,V> (n);
  C* buf= mmx_new<C> (buf_size);
  Pol::copy (buf, dest, n);
  C* src= buf;
  if (l == 1) {
    Vec::triple_copy (dest, buf, t);
    Vec::triple_copy (dest + 1, buf + t, t);
    Vec::triple_copy (dest + 2, buf + (t << 1), t);
  }
  else while (k != 0) {
    Vec::double_copy (dest, src, l);
    Vec::double_copy (dest + 1, src + t, l);
    Vec::double_add (dest + 2, src + (t << 1), l-1);
    dest[l<<1]= src[(t<<1) + (l-1)];
    dest += ll; src += l; k--;
  }
  mmx_delete<C> (buf, buf_size);
}

---

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

• include/algebramix/fkt_transform.hpp