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

Go to the documentation of this file.

/******************************************************************************
* MODULE     : modular_integer.hpp
* DESCRIPTION: modulus for modular arithmetic over integers
* 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__MODULAR_INTEGER__HPP
#define __MMX__MODULAR_INTEGER__HPP
#include <numerix/integer.hpp>
#include <numerix/modular.hpp>
#include <numerix/modular_int.hpp>

namespace mmx {

#define TMPL template<typename C, typename M>

/******************************************************************************
* Naive implementation relying on direct division
******************************************************************************/
// The modulus 'p' is always taken to be positive
// The modulars are in the range [0, p-1]

struct modulus_normalization_integer_naive {

  template<typename C> static inline bool
  normalize (C& p) {
    if (p < 0) p = -p;
    return true;
  }
};

template<typename V>
struct modulus_add_integer_naive : public V {

  TMPL static inline void
  neg_mod (C& dest, const M& m) {
    if (dest != 0) dest = m.p - dest; }

  TMPL static inline void
  neg_mod (C& dest, const M& m, C& carry) {
    VERIFY (carry == 0 || carry == 1, "unexpected large carry");
    if (dest != 0 || carry != 0) { dest= m.p - dest - carry; carry= 1; } }

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

  TMPL static inline void
  neg_mod (C& dest, const C& s, const M& m, C& carry) {
    VERIFY (carry == 0 || carry == 1, "unexpected large carry");
    if (s != 0 || carry != 0) { dest= m.p - s - carry; carry= 1; }
    else dest= 0; }

  TMPL static inline void
  add_mod (C& dest, const C& s, const M& m) {
    dest += s;
    if (dest >= m.p) dest -= m.p; }

  TMPL static inline void
  add_mod (C& dest, const C& s, const M& m, C& carry) {
    VERIFY (carry == 0 || carry == 1, "unexpected large carry");
    dest += s + carry;
    if (dest >= m.p) { dest -= m.p; carry= 1; } else carry= 0; }

  TMPL static inline void
  add_mod (C& dest, const C& s1, const C& s2, const M& m) {
    dest = s1;
    add_mod (dest, s2, m); }
  
  TMPL static inline void
  add_mod (C& dest, const C& s1, const C& s2, const M& m, C& carry) {
    dest = s1;
    add_mod (dest, s2, m, carry); }
  
  template<typename C> static inline void
  sub_mod_core (C& dest, const C& s, const C& p) {
    if (dest < s) dest += p;
    dest -= s; }

  template<typename C> static inline void
  sub_mod_core (C& dest, const C& s, const C& p, C& carry) {
    VERIFY (carry == 0 || carry == 1, "unexpected large carry");
    C t = s + carry;
    if (t == p || dest < t) { dest += p; carry= 1; } else carry= 0;
    dest -= t; }

  TMPL static inline void
  sub_mod (C& dest, const C& s, const M& m) {
    sub_mod_core (dest, s, m.p); }

  TMPL static inline void
  sub_mod (C& dest, const C& s, const M& m, C& carry) {
    sub_mod_core (dest, s, m.p, carry); }

  TMPL static inline void
  sub_mod (C& dest, const C& s1, const C& s2, const M& m) {
    dest = s1;
    sub_mod (dest, s2, m); }

  TMPL static inline void
  sub_mod (C& dest, const C& s1, const C& s2, const M& m, C& carry) {
    dest = s1;
    sub_mod (dest, s2, m, carry); }
};

template<typename V>
struct modulus_inv_integer_naive : public V {

  TMPL static inline void
  inv_mod (C& a, const M& m) {
    if (m.p == 0) {
      if (a == 1 || a == -1)
        return;
      else
        ERROR ("inv_mod: argument is not invertible");  
    }
    a = invert_modulo (a, m.p);
    if (a == 0 && m.p != 1)
      ERROR ("inv_mod: argument is not invertible"); }

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

template<typename V>
struct modulus_encoding_integer_naive : public V {
  TMPL static inline void 
  encode_mod (C& dest, const C& s, const M& m) {
    if (s < 0 && m.p != 0) {
      dest = - s;
      V::reduce_mod (dest, m);
      dest = m.p - dest;
    }
    else
      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; }
};

struct modulus_integer_naive:
  public modulus_encoding_integer_naive<
         modulus_div_naive<
         modulus_inv_integer_naive<
         modulus_mul_naive<
         modulus_add_integer_naive<
         modulus_reduction_naive<
         modulus_normalization_integer_naive> > > > > > {};

/******************************************************************************
* Helpers specializations for hardware integers
******************************************************************************/

template<>
struct modulus_variant_helper<integer> {
  typedef modulus_integer_naive MV; };

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