synaps/arithm/ModP.h

/*********************************************************************
*      This file is part of the source code of SYNAPS kernel.        *
*   Author(s): B. Mourrain, GALAAD, INRIA                            *
**********************************************************************
History: 
$Id: ModP.h,v 1.1 2005/07/11 10:39:47 mourrain Exp $
**********************************************************************/
#ifndef SYNAPS_ARITHM_MODP_H
#define SYNAPS_ARITHM_MODP_H
//----------------------------------------------------------------------
#include <iostream>
#include <cstdlib>
#include <cassert>
#include <synaps/init.h>
//----------------------------------------------------------------------
__BEGIN_NAMESPACE_SYNAPS

template <class T=int>
struct ModP
{
private:
  T p;

public:
  ModP(): p(0) {}
  ModP(int n): p(n){ assert(n>0); };
  ModP(const ModP<T> & z): p(z.p) {}


  bool equal (T   a, T  b)      {return (a-b)%p==0;} 
  void assign(T & r, T  a)      {r =a %p;} 
  void add   (T & r, T  a)      {r+=a %p;}
  void add   (T & r, T  a, T b) {r=(a+b) %p;}
  void sub   (T & r, T  a)      {r-=a %p;}
  void sub   (T & r, T  a, T b) {r=(a-b) %p;}
  void neg   (T & r, T  a)      {r=-a;}
  void mul   (T & r, T  a)      {r*=a; r%=p;}
  void mul   (T & r, T  a, T b) {r=(a*b) %p;}
  void div   (T & res, T  z)      
    {
      assert(z!=0 && p!=0);
      T a=p, b=z;
      b %=p; b +=p; b%=p;
      T r=b, u1=1,u2=0, q, inv=0;
      while(r!=0) 
        {
          q = a/b; 
          r = (a-q*b)%p; a=b; b=r;
          u2= (inv-q*u1)%p; inv=u1; u1=u2;
        }
      inv+=p; inv%=p;
      mul(res,inv);
    }
  void div   (T & r, T  a, T b) {r=a; div(r,b);}

  void print (std::ostream & os, const T & a) {os<<a;}
  void read  (std::istream & is, T& a) {is>>a;}
};
//----------------------------------------------------------------------

__END_NAMESPACE_SYNAPS

#endif // SYNAPS_ARITHM_MODP_H