/Users/mourrain/Devel/mmx/numerix/include/numerix/modulus_naive.hpp

Go to the documentation of this file.

/******************************************************************************
* MODULE     : modulus_naive.hpp
* DESCRIPTION: modulus for modular arithmetic
* COPYRIGHT  : (C) 2008  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__MODULUS_NAIVE__HPP
#define __MMX__MODULUS_NAIVE__HPP
#include "basix/port.hpp"

namespace mmx {
#define TMPL template<typename C, typename M>

/******************************************************************************
* Naive reduction through remaindering
******************************************************************************/

struct modulus_normalization_naive {
  template<typename C> static inline bool
  normalize (C& p) { return true; }
};

template<typename V>
struct modulus_reduction_naive : public V {
  TMPL static inline void 
  reduce_mod (C& dest, const M& m) {
    if (m.p != 0) dest = rem (dest, m.p); }

  TMPL static inline void 
  reduce_mod (C& dest, const M& m, C& carry) {
    if (m.p != 0) {
      carry= quo (dest, m.p);
      dest = rem (dest, m.p);
    }
    else
      carry= 0; }

  TMPL static inline void 
  reduce_mod (C& dest, const C& s, const M& m) {
    if (m.p != 0) dest = rem (s, m.p); else dest = s; }

  TMPL static inline void 
  reduce_mod (C& dest, const C& s, const M& m, C& carry) {
    if (m.p != 0) {
      carry= quo (s, m.p);
      dest = rem (s, m.p);
    }
    else {
      carry= 0;
      dest= s;
    } }
};

/******************************************************************************
* In place operations
******************************************************************************/

template<typename V>
struct modulus_add_naive : public V {

  TMPL static inline void 
  neg_mod (C& dest, const M& m) {
    dest = - dest;
    V::reduce_mod (dest, m);}

  TMPL static inline void 
  neg_mod (C& dest, const M& m, C& carry) {
    dest= carry - dest;
    V::reduce_mod (dest, m, carry); }

  TMPL static inline void 
  neg_mod (C& dest, const C& s, const M& m) {
    V::reduce_mod (dest, -s, m);}

  TMPL static inline void 
  neg_mod (C& dest, const C& s, const M& m, C& carry) {
    V::reduce_mod (dest, carry - s, m, carry); }

  TMPL static inline void 
  add_mod (C& dest, const C& s, const M& m) {
    dest += s;
    V::reduce_mod (dest, m); }

  TMPL static inline void 
  add_mod (C& dest, const C& s, const M& m, C& carry) {
    dest += s + carry;
    V::reduce_mod (dest, m, carry); }

  TMPL static inline void 
  add_mod (C& dest, const C& s1, const C& s2, const M& m) {
    V::reduce_mod (dest, s1 + s2, m); }

  TMPL static inline void 
  add_mod (C& dest, const C& s1, const C& s2, const M& m, C& carry) {
    V::reduce_mod (dest, s1 + s2 + carry, m, carry); }

  TMPL static inline void 
  sub_mod (C& dest, const C& s, const M& m) {
    dest -= s;
    V::reduce_mod (dest, m); }

  TMPL static inline void 
  sub_mod (C& dest, const C& s, const M& m, C& carry) {
    dest -= s + carry;
    V::reduce_mod (dest, m, carry); }

  TMPL static inline void 
  sub_mod (C& dest, const C& s1, const C& s2, const M& m) {
    V::reduce_mod (dest, s1 - s2, m); }

  TMPL static inline void 
  sub_mod (C& dest, const C& s1, const C& s2, const M& m, C& carry) {
    V::reduce_mod (dest, s1 - s2 + carry, m, carry); }

};
  
template<typename V>
struct modulus_mul_naive : public V {

  TMPL static inline void 
  mul_mod (C& dest, const C& s, const M& m) {
    dest *= s;
    V::reduce_mod (dest, m); }

  TMPL static inline void 
  mul_mod (C& dest, const C& s, const M& m, C& carry) {
    dest *= s;
    dest += carry;
    V::reduce_mod (dest, m, carry); }

  TMPL static inline void 
  mul_mod (C& dest, const C& s1, const C& s2, const M& m) {
    V::reduce_mod (dest, s1 * s2, m); }

  TMPL static inline void 
  mul_mod (C& dest, const C& s1, const C& s2, const M& m, C& carry) {
    V::reduce_mod (dest, s1 * s2 + carry, m, carry); }
};

template<typename V>
struct modulus_inv_naive : public V {

  TMPL static inline void 
  inv_mod (C& dest, const M& m) {
    (void) m;
    if ((dest == (C) 1) || (dest == (C) -1)) return;
    ERROR ("inv_mod: argument is not invertible"); }

  TMPL static inline void 
  inv_mod (C& dest, const C& s, const M& m) {
    (void) m;
    if ((s == (C) 1) || (s == (C) -1)) { dest = s; return; }
    ERROR ("inv_mod: argument is not invertible"); }
};

template<typename V>
struct modulus_div_naive : public V {

  TMPL static inline void 
  div_mod (C& dest, const C& s, const M& m) {
    C t = s;
    V::inv_mod (t, m);
    V::mul_mod (dest, t, m); }

  TMPL static inline void 
  div_mod (C& dest, const C& s1, const C& s2, const M& m) {
    C t;
    V::inv_mod (t, s2, m);
    V::mul_mod (dest, s1, t, m); }
};

/******************************************************************************
* Naive encoding is identity
******************************************************************************/

template<typename V>
struct modulus_encoding_naive : public V {

  TMPL static inline void 
  encode_mod (C& dest, const C& s, const M& m) {
    dest = s;
    V::reduce_mod (dest, m); }

  TMPL static inline void 
  decode_mod (C& dest, const C& s, const M& m) {
    (void) m;
    dest = s; }
};

/******************************************************************************
* Naive modulus
******************************************************************************/

struct modulus_naive:
  public modulus_encoding_naive<
         modulus_div_naive<
         modulus_inv_naive<
         modulus_mul_naive<
         modulus_add_naive<
         modulus_reduction_naive<
         modulus_normalization_naive> > > > > > {};

/******************************************************************************
* Default variant helper
******************************************************************************/

template<typename C>
struct modulus_variant_helper { typedef modulus_naive MV; };

#undef TMPL
} // namespace mmx
#endif //__MMX__MODULUS_NAIVE__HPP