algebramix_doc 0.3
|
#include <fkt_transform.hpp>
Definition at line 21 of file fkt_transform.hpp.
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.
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); }