My Project  UNKNOWN_GIT_VERSION
modulop.h
Go to the documentation of this file.
1 #ifndef MODULOP_H
2 #define MODULOP_H
3 /****************************************
4 * Computer Algebra System SINGULAR *
5 ****************************************/
6 /*
7 * ABSTRACT: numbers modulo p (<=32749)
8 */
9 #include "misc/auxiliary.h"
10 
11 
12 // define if a*b is with mod instead of tables
13 //#define HAVE_GENERIC_MULT
14 // define if 1/b is from tables
15 //#define HAVE_INVTABLE
16 // define if an if should be used
17 //#define HAVE_GENERIC_ADD
18 
19 //#undef HAVE_GENERIC_ADD
20 //#undef HAVE_GENERIC_MULT
21 //#undef HAVE_INVTABLE
22 
23 //#define HAVE_GENERIC_ADD 1
24 //#define HAVE_GENERIC_MULT 1
25 //#define HAVE_INVTABLE 1
26 
27 // enable large primes (32749 < p < 2^31-)
28 #define NV_OPS
29 #define NV_MAX_PRIME 32749
30 #define FACTORY_MAX_PRIME 536870909
31 
32 #ifdef USE_NTL_XGCD
33 //ifdef HAVE_NTL // in ntl.a
34 //extern void XGCD(long& d, long& s, long& t, long a, long b);
35 #include <NTL/ZZ.h>
36 #ifdef NTL_CLIENT
37 NTL_CLIENT
38 #endif
39 #endif
40 
41 struct n_Procs_s; typedef struct n_Procs_s *coeffs;
42 struct snumber; typedef struct snumber * number;
43 
44 BOOLEAN npInitChar(coeffs r, void* p);
45 
46 // inline number npMultM(number a, number b, int npPrimeM)
47 // // return (a*b)%n
48 // {
49 // double ab;
50 // long q, res;
51 //
52 // ab = ((double) ((int)a)) * ((double) ((int)b));
53 // q = (long) (ab/((double) npPrimeM)); // q could be off by (+/-) 1
54 // res = (long) (ab - ((double) q)*((double) npPrimeM));
55 // res += (res >> 31) & npPrimeM;
56 // res -= npPrimeM;
57 // res += (res >> 31) & npPrimeM;
58 // return (number)res;
59 // }
60 #ifdef HAVE_GENERIC_MULT
61 static inline number npMultM(number a, number b, const coeffs r)
62 {
63  return (number)
64  ((((unsigned long) a)*((unsigned long) b)) % ((unsigned long) r->ch));
65 }
66 static inline void npInpMultM(number &a, number b, const coeffs r)
67 {
68  a=(number)
69  ((((unsigned long) a)*((unsigned long) b)) % ((unsigned long) r->ch));
70 }
71 #else
72 static inline number npMultM(number a, number b, const coeffs r)
73 {
74  long x = (long)r->npLogTable[(long)a]+ r->npLogTable[(long)b];
75  #ifdef HAVE_GENERIC_ADD
76  if (x>=r->npPminus1M) x-=r->npPminus1M;
77  #else
78  x-=r->npPminus1M;
79  #if SIZEOF_LONG == 8
80  x += (x >> 63) & r->npPminus1M;
81  #else
82  x += (x >> 31) & r->npPminus1M;
83  #endif
84  #endif
85  return (number)(long)r->npExpTable[x];
86 }
87 static inline void npInpMultM(number &a, number b, const coeffs r)
88 {
89  long x = (long)r->npLogTable[(long)a]+ r->npLogTable[(long)b];
90  #ifdef HAVE_GENERIC_ADD
91  if (x>=r->npPminus1M) x-=r->npPminus1M;
92  #else
93  x-=r->npPminus1M;
94  #if SIZEOF_LONG == 8
95  x += (x >> 63) & r->npPminus1M;
96  #else
97  x += (x >> 31) & r->npPminus1M;
98  #endif
99  #endif
100  a=(number)(long)r->npExpTable[x];
101 }
102 #endif
103 
104 #if 0
105 inline number npAddAsm(number a, number b, int m)
106 {
107  number r;
108  asm ("addl %2, %1; cmpl %3, %1; jb 0f; subl %3, %1; 0:"
109  : "=&r" (r)
110  : "%0" (a), "g" (b), "g" (m)
111  : "cc");
112  return r;
113 }
114 inline number npSubAsm(number a, number b, int m)
115 {
116  number r;
117  asm ("subl %2, %1; jnc 0f; addl %3, %1; 0:"
118  : "=&r" (r)
119  : "%0" (a), "g" (b), "g" (m)
120  : "cc");
121  return r;
122 }
123 #endif
124 #ifdef HAVE_GENERIC_ADD
125 static inline number npAddM(number a, number b, const coeffs r)
126 {
127  unsigned long R = (unsigned long)a + (unsigned long)b;
128  return (number)(R >= r->ch ? R - r->ch : R);
129 }
130 static inline void npInpAddM(number &a, number b, const coeffs r)
131 {
132  unsigned long R = (unsigned long)a + (unsigned long)b;
133  a=(number)(R >= r->ch ? R - r->ch : R);
134 }
135 static inline number npSubM(number a, number b, const coeffs r)
136 {
137  return (number)((long)a<(long)b ?
138  r->ch-(long)b+(long)a : (long)a-(long)b);
139 }
140 #else
141 static inline number npAddM(number a, number b, const coeffs r)
142 {
143  unsigned long res = (long)((unsigned long)a + (unsigned long)b);
144  res -= r->ch;
145 #if SIZEOF_LONG == 8
146  res += ((long)res >> 63) & r->ch;
147 #else
148  res += ((long)res >> 31) & r->ch;
149 #endif
150  return (number)res;
151 }
152 static inline void npInpAddM(number &a, number b, const coeffs r)
153 {
154  unsigned long res = (long)((unsigned long)a + (unsigned long)b);
155  res -= r->ch;
156 #if SIZEOF_LONG == 8
157  res += ((long)res >> 63) & r->ch;
158 #else
159  res += ((long)res >> 31) & r->ch;
160 #endif
161  a=(number)res;
162 }
163 static inline number npSubM(number a, number b, const coeffs r)
164 {
165  long res = ((long)a - (long)b);
166 #if SIZEOF_LONG == 8
167  res += (res >> 63) & r->ch;
168 #else
169  res += (res >> 31) & r->ch;
170 #endif
171  return (number)res;
172 }
173 #endif
174 
175 static inline number npNegM(number a, const coeffs r)
176 {
177  return (number)((long)(r->ch)-(long)(a));
178 }
179 
180 static inline BOOLEAN npIsZeroM (number a, const coeffs)
181 {
182  return 0 == (long)a;
183 }
184 static inline BOOLEAN npIsOne (number a, const coeffs)
185 {
186  return 1 == (long)a;
187 }
188 
189 static inline long npInvMod(long a, const coeffs R)
190 {
191  long s, t;
192 
193 #ifdef USE_NTL_XGCD
194  long d;
195  XGCD(d, s, t, a, R->ch);
196  assume (d == 1);
197 #else
198  long u, v, u0, v0, u1, u2, q, r;
199 
200  assume(a>0);
201  u1=1; u2=0;
202  u = a; v = R->ch;
203 
204  while (v != 0)
205  {
206  q = u / v;
207  //r = u % v;
208  r = u - q*v;
209  u = v;
210  v = r;
211  u0 = u2;
212  u2 = u1 - q*u2;
213  u1 = u0;
214  }
215 
216  assume(u==1);
217  s = u1;
218 #endif
219 #ifdef HAVE_GENERIC_ADD
220  if (s < 0)
221  return s + R->ch;
222  else
223  return s;
224 #else
225  #if SIZEOF_LONG == 8
226  s += (s >> 63) & R->ch;
227  #else
228  s += (s >> 31) & R->ch;
229  #endif
230  return s;
231 #endif
232 }
233 
234 static inline number npInversM (number c, const coeffs r)
235 {
236  n_Test(c, r);
237 #ifndef HAVE_GENERIC_MULT
238  #ifndef HAVE_INVTABLE
239  number d = (number)(long)r->npExpTable[r->npPminus1M - r->npLogTable[(long)c]];
240  #else
241  long inv=(long)r->npInvTable[(long)c];
242  if (inv==0)
243  {
244  inv = (long)r->npExpTable[r->npPminus1M - r->npLogTable[(long)c]];
245  r->npInvTable[(long)c]=inv;
246  }
247  number d = (number)inv;
248  #endif
249 #else
250  #ifdef HAVE_INVTABLE
251  long inv=(long)r->npInvTable[(long)c];
252  if (inv==0)
253  {
254  inv=npInvMod((long)c,r);
255  r->npInvTable[(long)c]=inv;
256  }
257  #else
258  long inv=npInvMod((long)c,r);
259  #endif
260  number d = (number)inv;
261 #endif
262  n_Test(d, r);
263  return d;
264 }
265 
266 
267 // The folloing is reused inside gnumpc.cc, gnumpfl.cc and longrat.cc
268 long npInt (number &n, const coeffs r);
269 
270 // The folloing is reused inside tgb*.cc
271 number npMult (number a, number b, const coeffs r);
272 // The following is currently used in OPAE.cc, OPAEQ.cc and OPAEp.cc for setting their SetMap...
273 nMapFunc npSetMap(const coeffs src, const coeffs dst); // FIXME! BUG?
274 
275 #define npEqualM(A,B,r) ((A)==(B))
276 
277 
278 #endif
All the auxiliary stuff.
int BOOLEAN
Definition: auxiliary.h:85
int m
Definition: cfEzgcd.cc:121
Variable x
Definition: cfModGcd.cc:4023
int p
Definition: cfModGcd.cc:4019
CanonicalForm b
Definition: cfModGcd.cc:4044
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:738
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition: coeffs.h:73
const CanonicalForm int s
Definition: facAbsFact.cc:55
CanonicalForm res
Definition: facAbsFact.cc:64
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
mpz_t n
Definition: longrat.h:50
'SR_INT' is the type of those integers small enough to fit into 29 bits.
Definition: longrat.h:48
#define assume(x)
Definition: mod2.h:390
static BOOLEAN npIsOne(number a, const coeffs)
Definition: modulop.h:184
static number npAddM(number a, number b, const coeffs r)
Definition: modulop.h:125
static number npMultM(number a, number b, const coeffs r)
Definition: modulop.h:72
BOOLEAN npInitChar(coeffs r, void *p)
Definition: modulop.cc:378
static number npNegM(number a, const coeffs r)
Definition: modulop.h:175
static void npInpMultM(number &a, number b, const coeffs r)
Definition: modulop.h:87
nMapFunc npSetMap(const coeffs src, const coeffs dst)
Definition: modulop.cc:655
number npMult(number a, number b, const coeffs r)
Definition: modulop.cc:87
static long npInvMod(long a, const coeffs R)
Definition: modulop.h:189
static BOOLEAN npIsZeroM(number a, const coeffs)
Definition: modulop.h:180
static number npInversM(number c, const coeffs r)
Definition: modulop.h:234
long npInt(number &n, const coeffs r)
Definition: modulop.cc:128
static void npInpAddM(number &a, number b, const coeffs r)
Definition: modulop.h:130
static number npSubM(number a, number b, const coeffs r)
Definition: modulop.h:135
The main handler for Singular numbers which are suitable for Singular polynomials.
#define R
Definition: sirandom.c:26