Borderbasix

Zp.hpp
Go to the documentation of this file.
1 /*********************************************************************
2 * This file is part of the source code of BORDERBASIX software. *
3 * (C) B. Mourrain, INRIA *
4 **********************************************************************
5 History:
6 $Id: Zp.hpp,v 1.1.1.1 2006/10/06 08:01:40 trebuche Exp $
7 **********************************************************************/
8 #ifndef _Zp_H_
9 #define _Zp_H_
10 
11 #include <iostream>
12 #include <stdlib.h>
13 //----------------------------------------------------------------------
18 template <int p, class T=int>
19 class Z
20 {
21 private:
22  // T rep;
23  // using namespace std;
24 public:
25  T rep;
26  inline Z(): rep(0) {}
27  // Z(int n): rep(((n%p)+p)%p){}
28  template<typename TT>
29  Z(TT n){ rep=(long int)n%p;
30  if(rep < 0)
31  rep+=p;}
32  Z(double n): rep((((unsigned)n%p)+p)%p){}
33  Z(char * s):rep(((atoll(s)%p)+p)%p){}
34  inline Z(const Z<p,T> & z): rep(z.rep) {}
35  inline
36  Z<p,T>& operator= (const Z<p,T> &z) {rep=z.rep; return *this;}
37  inline
38  Z<p,T>& operator+=(const Z<p,T> z)
39  {
40  rep+=z.rep;
41  if(rep>=p) rep-=p;
42  // if(rep<0) {cout<<"+="<<endl;exit(1);};
43  return *this;
44  }
45  inline
46  Z<p,T>& operator-=(const Z<p,T> z)
47  {
48  (rep -=z.rep);
49  if(rep<0) rep+=p;
50  //if(rep<0) {cout<<"-="<<endl;exit(1);};
51  return *this;
52  }
53  Z<p,T>& operator*=(const Z<p,T> z)
54  {
55  int tmp=rep;
56  tmp *= z.rep; tmp %= p; rep=tmp;
57  //if(rep<0) {cout<<"*="<<endl;exit(1);};
58  return *this;}
59  Z<p,T>& operator/=(const Z<p,T> z);
60  bool operator==(const Z<p,T> &z) const {return (rep==z.rep);}
61  bool operator!=(const Z<p,T> &z) const {return !(*this==z);}
62  inline
63  Z<p,T> operator+(const Z<p,T> &b) const
64  {
65  Z<p,T> res; res.rep=(rep+b.rep); if (res.rep>p) res.rep-=((T)p);
66  // if(res.rep<0) {cout<<"+"<<endl;exit(1);};
67  return res;}
68  //{return (Z<p,T>(rep+b.rep));}
69 
70  inline
71  Z<p,T> operator-(const Z<p,T> &b) const
72  {
73  Z<p,T> res;
74  res.rep=(rep-b.rep);
75  if (res.rep<0) res.rep+=(T)p;
76  //if(res.rep<0) {cout<<"-"<<endl;exit(1);};
77  return res;}
78  template<typename Typ>
79  inline bool operator>( const Typ &b) const
80  {
81  return this->rep>b;
82  }
83  inline
84  Z<p,T> operator*( const Z<p,T> &b) const
85  // { T accu=rep,accub=b.rep;
86 // Z<p,T> res;
87 // res.rep=0;
88 // for(;accub>0;accub/=2,accu*=2)//accub>>1)
89 // {
90 
91 // if (accu>p)
92 // accu-=p;
93 // if (accub & 1)
94 // {
95 // res.rep+=accu;
96 // if(res.rep>p)
97 // res.rep-=p;
98 // }
99 // }
100 // return res;
101 // }
102  {Z<p,T> res; res.rep=(rep*b.rep)%p; return res;}
103 
104  Z<p,T> operator*( const int b) const
105  {Z<p,T> res; res.rep=(rep*b)%p; return res;}
106 
107  inline
108  Z<p,T> operator/(const Z<p,T> &b) const
109  {return (Z<p,T>(rep)/=b);}
110 };
111 
112 
113 template<int p, typename T>
114 // friend
115 std::ostream & operator<<(std::ostream& os, const Z<p,T> & z)
116 {return (os << z.rep);}
117 
118 //ostream & operator<<(ostream& os, const Z<32051,int> & z)
119 //{return (os << z.rep);}
120 
121 
122 template<int p, typename T>
123 // friend
124 std::istream & operator>>(std::istream& is, Z<p,T> & z)
125 {return (is >> z.rep);}
126 
127 //};
128 
129 // void convert(Z<3,int> &toto,char * chaine)
130 // {
131 // toto=Z<3,int>(chaine);
132 // }
133 // void convert(Z<32051,int> &toto,char * chaine)
134 // {
135 // toto=Z<32051,int>(chaine);
136 // }
137 template <int p, typename T>
138 Z<p,T> & Z<p,T>::operator/=(const Z<p,T> z)
139 {
140  static int flag=1;
141  static T *inverse=NULL;
142 #ifdef PETITFERMAT
143  static T expon[p];
144 #endif //
145  // int r=z.rep, a=z.rep, b=p,u1=0,u2=0, q;
146  if (flag)
147  {
148  inverse=(T*)malloc(p*sizeof(T));
149  for(int i=0;i<p;i++)
150  inverse[i]=-1;
151  // {
152 // int inversez;
153 // for(inversez=0;((inversez*i % p)!=1);inversez++);
154 // inverse[i]=inversez;
155 // }
156  flag=0;
157  }
158 
159  if(z==0){std::cout<<"division by zero"<<std::endl;exit(-10);}
160  if(inverse[(int)z.rep]==-1)
161  {
162  T inversez;
163 #ifndef PETITFERMAT
164  for(inversez=0;((inversez*z.rep) % p)!=1;inversez++);
165 #else
166  int comp=1;
167  expon[1]=z.rep;
168  for(;comp*2<p,comp*=2)
169  expon[2*comp]=(expon[comp]*expon[comp]) %p;
170  inversez=expon[comp];
171  for(int total=comp;total<p-2;total+=comp)
172  {
173  for(;comp+total>p-2;comp/=2);
174  inversez=(inversez * expon[comp]) %p;
175  }
176 #endif //
177  inverse[(int)z.rep]=inversez;
178  }
179  rep *=inverse[(int)z.rep];
180  rep =((long int) rep) % p;
181  return *this;
182 }
183 #if 0
184 Z<32051,short int>&
185 Z<32051,short int>::operator+=(const Z<32051,short int> z)
186  {
187  int tmp=rep;
188  (tmp += z.rep);
189  if(tmp>=32051) tmp-=32051;
190  rep=tmp;
191  //if(rep<0) {cout<<"+="<<endl;exit(1);};
192  return *this;
193  }
194 
195 Z<32051,short int >
196 Z<32051,short int >::operator+(const Z<32051,short int> &b) const
197  {
198  Z<32051,short int> res; int tmp=rep;
199  tmp=(tmp+b.rep); if (tmp>32051) tmp-=32051;
200  res.rep=tmp;
201  //if(res.rep<0) {cout<<"+"<<endl;exit(1);};
202 return res;}
203 
204 template<>
205 Z<32051,short int>& Z<32051,short int>::operator*=(const Z<32051,short int> z)
206 {int tmp=rep; rep=(short int)((tmp * z.rep)% 32051); return *this;}
207 
208 template<>
209 inline
210 Z<32051,short int> Z<32051,short int>::operator*( const Z<32051,short int> &b) const
211 {
212 int tmp=rep;
213 Z<32051,short int> res; res.rep=(tmp*b.rep)%32051; return res;}
214 
215 
216 template<>
217 Z<32051,short int>& Z<32051,short int>::operator/=(const Z<32051,short int> z)
218 {
219  static int flag=1;
220  static int *inverse=NULL;
221 #ifdef PETITFERMAT
222  static int expon[p];
223 #endif //
224  // int r=z.rep, a=z.rep, b=p,u1=0,u2=0, q;
225  if (flag)
226  {
227  inverse=(int*)malloc(32051*sizeof(int));
228 
229  cout<<"je malloc tout ca"<<endl;
230  for(int i=0;i<32051;i++)
231  inverse[i]=-1;
232  // {
233 // int inversez;
234 // for(inversez=0;((inversez*i % p)!=1);inversez++);
235 // inverse[i]=inversez;
236 // }
237  flag=0;
238  }
239  //cout<<"z.rep "<<z.rep<<endl;
240  if(z==0){std::cout<<"division by zero"<<endl;exit(-10);}
241  if(inverse[(int)z.rep]==-1)
242  {
243  int inversez;
244 #ifndef PETITFERMAT
245  for(inversez=0;((inversez*z.rep % 32051)!=1);inversez++);
246 #else
247  int comp=1;
248  expon[1]=z.rep;
249  for(;comp*2<32051,comp*=2)
250  expon[2*comp]=(expon[comp]*expon[comp]) %32051;
251  inversez=expon[comp];
252  for(int total=comp;total<32051-2;total+=comp)
253  {
254  for(;comp+total>32051-2;comp/=2);
255  inversez=(inversez * expon[comp]) %32051;
256  }
257 #endif //
258  inverse[z.rep]=inversez;
259  }
260  flag=rep *inverse[z.rep];
261  rep =flag % 32051;
262  flag=0;
263  return *this;
264 }
265 #endif
266 //----------------------------------------------------------------------
268 //----------------------------------------------------------------------
269 template <int p, class T>
270 Z<p,T> operator^(const Z<p,T> a, const int n)
271 {
272  int m;
273  Z<p,T> r=1, e;
274  if(n <0){e=1/a;m=-n;}else {e=a;m=n;}
275  while(m !=0) {
276  if(m%2){
277  m -=1; m/=2; r*=e; e*=e;
278  }else{
279  m/=2; e*=e;
280  }
281  }
282  return r;
283 }
284 //#include "Zp.C"
285 #endif // //_Zp_H_
286 
287 
288 
289 
operator>>
std::istream & operator>>(std::istream &is, Z< p, T > &z)
Definition: Zp.hpp:124
Z::operator=
Z< p, T > & operator=(const Z< p, T > &z)
Definition: Zp.hpp:36
Z::operator-=
Z< p, T > & operator-=(const Z< p, T > z)
Definition: Zp.hpp:46
flag
long flag
Definition: alp_f2c.H:52
inverse
void inverse(int *&, int)
Z::Z
Z(const Z< p, T > &z)
Definition: Zp.hpp:34
malloc
void * malloc(YYSIZE_T)
Z::operator/
Z< p, T > operator/(const Z< p, T > &b) const
Definition: Zp.hpp:108
Z::Z
Z()
Definition: Zp.hpp:26
Z::operator!=
bool operator!=(const Z< p, T > &z) const
Definition: Zp.hpp:61
Z::operator>
bool operator>(const Typ &b) const
Definition: Zp.hpp:79
Z::operator-
Z< p, T > operator-(const Z< p, T > &b) const
Definition: Zp.hpp:71
Z::operator+=
Z< p, T > & operator+=(const Z< p, T > z)
Definition: Zp.hpp:38
Z
Definition: Zp.hpp:19
Z::operator==
bool operator==(const Z< p, T > &z) const
Definition: Zp.hpp:60
Z::operator/=
Z< p, T > & operator/=(const Z< p, T > z)
Definition: Zp.C:19
Z::operator*=
Z< p, T > & operator*=(const Z< p, T > z)
Definition: Zp.hpp:53
i
MSKint32t MSKint32t MSKint32t i
Definition: mosek.h:2278
Z::Z
Z(char *s)
Definition: Zp.hpp:33
operator^
Z< p, T > operator^(const Z< p, T > a, const int n)
Fast binary exponentiation.
Definition: Zp.hpp:270
Z::operator*
Z< p, T > operator*(const int b) const
Definition: Zp.hpp:104
r
MSKrescodee r
Definition: mosek.h:2321
Z::operator+
Z< p, T > operator+(const Z< p, T > &b) const
Definition: Zp.hpp:63
a
MSKstreamtypee MSKint32t MSKint32t MSKint32t MSKint32t MSKint32t MSKint32t MSKint32t MSKint32t MSKint32t a
Definition: mosek.h:3833
Z::rep
T rep
Definition: Zp.hpp:25
Z::operator*
Z< p, T > operator*(const Z< p, T > &b) const
Definition: Zp.hpp:84
Z::Z
Z(double n)
Definition: Zp.hpp:32
Z::Z
Z(TT n)
Definition: Zp.hpp:29
Home  |  Download & Install |  Contributions
Generated on Tue Sep 29 2015 11:43:19 for Borderbasix by 1.8.9.1