include/algebramix/polynomial_modular.hpp

Go to the documentation of this file.

/******************************************************************************
* MODULE     : polynomial_modular.hpp
* DESCRIPTION: Multiplying modular polynomials by lifting and reduction
* COPYRIGHT  : (C) 2009  Joris van der Hoeven and Gregoire Lecerf
*******************************************************************************
* This software falls under the GNU general public license and comes WITHOUT
* ANY WARRANTY WHATSOEVER. See the file $TEXMACS_PATH/LICENSE for more details.
* If you don't have this file, write to the Free Software Foundation, Inc.,
* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
******************************************************************************/

#ifndef __MMX_POLYNOMIAL_MODULAR_HPP
#define __MMX_POLYNOMIAL_MODULAR_HPP
#include <algebramix/polynomial_dicho.hpp>

namespace mmx {
#define TMPL template<typename I, typename MoV, typename MaV>
#define M modular<modulus<I, MoV>, MaV>
#define C Lift_type(M)

/******************************************************************************
* Variant for modular polynomials
******************************************************************************/

template<typename V>
struct polynomial_modular: public V {
  typedef typename V::Vec Vec;
  typedef typename V::Naive Naive;
  typedef typename V::Positive Positive;
  typedef polynomial_modular<typename V::No_simd> No_simd;
  typedef polynomial_modular<typename V::No_thread> No_thread;
  typedef polynomial_modular<typename V::No_scaled> No_scaled;
};

template<typename F, typename V, typename W>
struct implementation<F,V,polynomial_modular<W> >:
  public implementation<F,V,W> {};

template<typename F, typename V, typename W>
struct polynomial_variant_helper<modular<modulus<F,V>, W> > {
  typedef polynomial_modular<polynomial_dicho<polynomial_naive> > PV;
};

/******************************************************************************
* Multiplication of modular polynomials
******************************************************************************/

template<typename V, typename W>
struct implementation<polynomial_multiply,V,polynomial_modular<W> >:
  public implementation<polynomial_linear,V>
{
  typedef implementation<polynomial_multiply,W> Fallback;

template<typename K> static inline void
mul (K* dest, const K* s1, const K* s2, nat n1, nat n2) {
  Fallback::mul (dest, s1, s2, n1, n2);
}
  
template<typename K> static inline void
square (K* dest, const K* s1, nat n1) {
  Fallback::square (dest, s1, n1);
}
  
TMPL static inline void
mul (M* dest, const M* s1, const M* s2, nat n1, nat n2) {
  typedef typename Polynomial_variant (C) CV;
  typedef implementation<vector_linear,CV> Vec_C;
  typedef implementation<polynomial_multiply,CV> Pol_C;

  nat nd  = n1 + n2 - 1;
  nat spc1= aligned_size<C,CV> (n1);
  nat spc2= aligned_size<C,CV> (n2);
  nat spcd= aligned_size<C,CV> (nd);
  nat spc = spc1 + spc2 + spcd;
  C* x1= mmx_new<C> (spc);
  C* x2= x1 + spc1;
  C* xd= x2 + spc2;
  Vec_C::template vec_unary<lift_op> (x1, s1, n1);
  Vec_C::template vec_unary<lift_op> (x2, s2, n2);
  Pol_C::mul (xd, x1, x2, n1, n2);
  Vec_C::template vec_unary<project_op> (dest, xd, nd);
  mmx_delete<C> (x1, spc);
}

TMPL static inline void
square (M* dest, const M* s1, nat n1) {
  typedef typename Polynomial_variant (C) CV;
  typedef implementation<vector_linear,CV> Vec_C;
  typedef implementation<polynomial_multiply,CV> Pol_C;

  nat nd  = n1 + n1 - 1;
  nat spc1= aligned_size<C,CV> (n1);
  nat spcd= aligned_size<C,CV> (nd);
  nat spc = spc1 + spcd;
  C* x1= mmx_new<C> (spc);
  C* xd= x1 + spc1;
  Vec_C::template vec_unary<lift_op> (x1, s1, n1);
  Pol_C::square (xd, x1, n1);
  Vec_C::template vec_unary<project_op> (dest, xd, nd);
  mmx_delete<C> (x1, spc);
}

}; // implementation<polynomial_multiply,V,polynomial_modular<CV> >

#undef TMPL
#undef M
#undef C

} // namespace mmx
#endif // __MMX_POLYNOMIAL_MODULAR_HPP

---