rmodulo2m.cc
Go to the documentation of this file.
1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 /*
5 * ABSTRACT: numbers modulo 2^m
6 */
7 #include <misc/auxiliary.h>
8 
9 #include <omalloc/omalloc.h>
10 
11 #include <misc/mylimits.h>
12 #include <reporter/reporter.h>
13 
14 #include "si_gmp.h"
15 #include "coeffs.h"
16 #include "numbers.h"
17 #include "longrat.h"
18 #include "mpr_complex.h"
19 
20 #include "rmodulo2m.h"
21 #include "rmodulon.h"
22 
23 #include <string.h>
24 
25 #ifdef HAVE_RINGS
26 
27 static inline number nr2mMultM(number a, number b, const coeffs r)
28 {
29  return (number)
30  ((((unsigned long) a) * ((unsigned long) b)) & ((unsigned long)r->mod2mMask));
31 }
32 
33 static inline number nr2mAddM(number a, number b, const coeffs r)
34 {
35  return (number)
36  ((((unsigned long) a) + ((unsigned long) b)) & ((unsigned long)r->mod2mMask));
37 }
38 
39 static inline number nr2mSubM(number a, number b, const coeffs r)
40 {
41  return (number)((unsigned long)a < (unsigned long)b ?
42  r->mod2mMask - (unsigned long)b + (unsigned long)a + 1:
43  (unsigned long)a - (unsigned long)b);
44 }
45 
46 #define nr2mNegM(A,r) (number)((r->mod2mMask - (unsigned long)(A) + 1) & r->mod2mMask)
47 #define nr2mEqualM(A,B) ((A)==(B))
48 
49 extern omBin gmp_nrz_bin; /* init in rintegers*/
50 
51 static char* nr2mCoeffName(const coeffs cf)
52 {
53  static char n2mCoeffName_buf[22];
54  snprintf(n2mCoeffName_buf,21,"ZZ/(2^%lu)",cf->modExponent);
55  return n2mCoeffName_buf;
56 }
57 
58 static void nr2mCoeffWrite (const coeffs r, BOOLEAN /*details*/)
59 {
60  PrintS("// coeff. ring is : ");
61  Print("Z/2^%lu\n", r->modExponent);
62 }
63 
64 static BOOLEAN nr2mCoeffIsEqual(const coeffs r, n_coeffType n, void * p)
65 {
66  if (n==n_Z2m)
67  {
68  int m=(int)(long)(p);
69  unsigned long mm=r->mod2mMask;
70  if (((mm+1)>>m)==1L) return TRUE;
71  }
72  return FALSE;
73 }
74 
75 static char* nr2mCoeffString(const coeffs r)
76 {
77  // r->modExponent <=bitsize(long)
78  char* s = (char*) omAlloc(11+11);
79  sprintf(s,"ZZ/(2^%lu)",r->modExponent);
80  return s;
81 }
82 
83 static coeffs nr2mQuot1(number c, const coeffs r)
84 {
85  coeffs rr;
86  long ch = r->cfInt(c, r);
87  mpz_t a,b;
88  mpz_init_set(a, r->modNumber);
89  mpz_init_set_ui(b, ch);
90  mpz_ptr gcd;
91  gcd = (mpz_ptr) omAlloc(sizeof(mpz_t));
92  mpz_init(gcd);
93  mpz_gcd(gcd, a,b);
94  if(mpz_cmp_ui(gcd, 1) == 0)
95  {
96  WerrorS("constant in q-ideal is coprime to modulus in ground ring");
97  WerrorS("Unable to create qring!");
98  return NULL;
99  }
100  if(mpz_cmp_ui(gcd, 2) == 0)
101  {
102  rr = nInitChar(n_Zp, (void*)2);
103  }
104  else
105  {
106  int kNew = 1;
107  mpz_t baseTokNew;
108  mpz_init(baseTokNew);
109  mpz_set(baseTokNew, r->modBase);
110  while(mpz_cmp(gcd, baseTokNew) > 0)
111  {
112  kNew++;
113  mpz_mul(baseTokNew, baseTokNew, r->modBase);
114  }
115  mpz_clear(baseTokNew);
116  rr = nInitChar(n_Z2m, (void*)(long)kNew);
117  }
118  return(rr);
119 }
120 
121 /* TRUE iff 0 < k <= 2^m / 2 */
122 static BOOLEAN nr2mGreaterZero(number k, const coeffs r)
123 {
124  if ((unsigned long)k == 0) return FALSE;
125  if ((unsigned long)k > ((r->mod2mMask >> 1) + 1)) return FALSE;
126  return TRUE;
127 }
128 
129 /*
130  * Multiply two numbers
131  */
132 static number nr2mMult(number a, number b, const coeffs r)
133 {
134  if (((unsigned long)a == 0) || ((unsigned long)b == 0))
135  return (number)0;
136  else
137  return nr2mMultM(a, b, r);
138 }
139 
140 static number nr2mAnn(number b, const coeffs r);
141 /*
142  * Give the smallest k, such that a * x = k = b * y has a solution
143  */
144 static number nr2mLcm(number a, number b, const coeffs)
145 {
146  unsigned long res = 0;
147  if ((unsigned long)a == 0) a = (number) 1;
148  if ((unsigned long)b == 0) b = (number) 1;
149  while ((unsigned long)a % 2 == 0)
150  {
151  a = (number)((unsigned long)a / 2);
152  if ((unsigned long)b % 2 == 0) b = (number)((unsigned long)b / 2);
153  res++;
154  }
155  while ((unsigned long)b % 2 == 0)
156  {
157  b = (number)((unsigned long)b / 2);
158  res++;
159  }
160  return (number)(1L << res); // (2**res)
161 }
162 
163 /*
164  * Give the largest k, such that a = x * k, b = y * k has
165  * a solution.
166  */
167 static number nr2mGcd(number a, number b, const coeffs)
168 {
169  unsigned long res = 0;
170  if ((unsigned long)a == 0 && (unsigned long)b == 0) return (number)1;
171  while ((unsigned long)a % 2 == 0 && (unsigned long)b % 2 == 0)
172  {
173  a = (number)((unsigned long)a / 2);
174  b = (number)((unsigned long)b / 2);
175  res++;
176  }
177 // if ((unsigned long)b % 2 == 0)
178 // {
179 // return (number)((1L << res)); // * (unsigned long) a); // (2**res)*a a is a unit
180 // }
181 // else
182 // {
183  return (number)((1L << res)); // * (unsigned long) b); // (2**res)*b b is a unit
184 // }
185 }
186 
187 /* assumes that 'a' is odd, i.e., a unit in Z/2^m, and computes
188  the extended gcd of 'a' and 2^m, in order to find some 's'
189  and 't' such that a * s + 2^m * t = gcd(a, 2^m) = 1;
190  this code will always find a positive 's' */
191 static void specialXGCD(unsigned long& s, unsigned long a, const coeffs r)
192 {
193  mpz_ptr u = (mpz_ptr)omAlloc(sizeof(mpz_t));
194  mpz_init_set_ui(u, a);
195  mpz_ptr u0 = (mpz_ptr)omAlloc(sizeof(mpz_t));
196  mpz_init(u0);
197  mpz_ptr u1 = (mpz_ptr)omAlloc(sizeof(mpz_t));
198  mpz_init_set_ui(u1, 1);
199  mpz_ptr u2 = (mpz_ptr)omAlloc(sizeof(mpz_t));
200  mpz_init(u2);
201  mpz_ptr v = (mpz_ptr)omAlloc(sizeof(mpz_t));
202  mpz_init_set_ui(v, r->mod2mMask);
203  mpz_add_ui(v, v, 1); /* now: v = 2^m */
204  mpz_ptr v0 = (mpz_ptr)omAlloc(sizeof(mpz_t));
205  mpz_init(v0);
206  mpz_ptr v1 = (mpz_ptr)omAlloc(sizeof(mpz_t));
207  mpz_init(v1);
208  mpz_ptr v2 = (mpz_ptr)omAlloc(sizeof(mpz_t));
209  mpz_init_set_ui(v2, 1);
210  mpz_ptr q = (mpz_ptr)omAlloc(sizeof(mpz_t));
211  mpz_init(q);
212  mpz_ptr rr = (mpz_ptr)omAlloc(sizeof(mpz_t));
213  mpz_init(rr);
214 
215  while (mpz_cmp_ui(v, 0) != 0) /* i.e., while v != 0 */
216  {
217  mpz_div(q, u, v);
218  mpz_mod(rr, u, v);
219  mpz_set(u, v);
220  mpz_set(v, rr);
221  mpz_set(u0, u2);
222  mpz_set(v0, v2);
223  mpz_mul(u2, u2, q); mpz_sub(u2, u1, u2); /* u2 = u1 - q * u2 */
224  mpz_mul(v2, v2, q); mpz_sub(v2, v1, v2); /* v2 = v1 - q * v2 */
225  mpz_set(u1, u0);
226  mpz_set(v1, v0);
227  }
228 
229  while (mpz_cmp_ui(u1, 0) < 0) /* i.e., while u1 < 0 */
230  {
231  /* we add 2^m = (2^m - 1) + 1 to u1: */
232  mpz_add_ui(u1, u1, r->mod2mMask);
233  mpz_add_ui(u1, u1, 1);
234  }
235  s = mpz_get_ui(u1); /* now: 0 <= s <= 2^m - 1 */
236 
237  mpz_clear(u); omFree((ADDRESS)u);
238  mpz_clear(u0); omFree((ADDRESS)u0);
239  mpz_clear(u1); omFree((ADDRESS)u1);
240  mpz_clear(u2); omFree((ADDRESS)u2);
241  mpz_clear(v); omFree((ADDRESS)v);
242  mpz_clear(v0); omFree((ADDRESS)v0);
243  mpz_clear(v1); omFree((ADDRESS)v1);
244  mpz_clear(v2); omFree((ADDRESS)v2);
245  mpz_clear(q); omFree((ADDRESS)q);
246  mpz_clear(rr); omFree((ADDRESS)rr);
247 }
248 
249 static unsigned long InvMod(unsigned long a, const coeffs r)
250 {
251  assume((unsigned long)a % 2 != 0);
252  unsigned long s;
253  specialXGCD(s, a, r);
254  return s;
255 }
256 
257 static inline number nr2mInversM(number c, const coeffs r)
258 {
259  assume((unsigned long)c % 2 != 0);
260  // Table !!!
261  unsigned long inv;
262  inv = InvMod((unsigned long)c,r);
263  return (number)inv;
264 }
265 
266 static number nr2mInvers(number c, const coeffs r)
267 {
268  if ((unsigned long)c % 2 == 0)
269  {
270  WerrorS("division by zero divisor");
271  return (number)0;
272  }
273  return nr2mInversM(c, r);
274 }
275 
276 /*
277  * Give the largest k, such that a = x * k, b = y * k has
278  * a solution.
279  */
280 static number nr2mExtGcd(number a, number b, number *s, number *t, const coeffs r)
281 {
282  unsigned long res = 0;
283  if ((unsigned long)a == 0 && (unsigned long)b == 0) return (number)1;
284  while ((unsigned long)a % 2 == 0 && (unsigned long)b % 2 == 0)
285  {
286  a = (number)((unsigned long)a / 2);
287  b = (number)((unsigned long)b / 2);
288  res++;
289  }
290  if ((unsigned long)b % 2 == 0)
291  {
292  *t = NULL;
293  *s = nr2mInvers(a,r);
294  return (number)((1L << res)); // * (unsigned long) a); // (2**res)*a a is a unit
295  }
296  else
297  {
298  *s = NULL;
299  *t = nr2mInvers(b,r);
300  return (number)((1L << res)); // * (unsigned long) b); // (2**res)*b b is a unit
301  }
302 }
303 
304 static void nr2mPower(number a, int i, number * result, const coeffs r)
305 {
306  if (i == 0)
307  {
308  *(unsigned long *)result = 1;
309  }
310  else if (i == 1)
311  {
312  *result = a;
313  }
314  else
315  {
316  nr2mPower(a, i-1, result, r);
317  *result = nr2mMultM(a, *result, r);
318  }
319 }
320 
321 /*
322  * create a number from int
323  */
324 static number nr2mInit(long i, const coeffs r)
325 {
326  if (i == 0) return (number)(unsigned long)i;
327 
328  long ii = i;
329  unsigned long j = (unsigned long)1;
330  if (ii < 0) { j = r->mod2mMask; ii = -ii; }
331  unsigned long k = (unsigned long)ii;
332  k = k & r->mod2mMask;
333  /* now we have: i = j * k mod 2^m */
334  return (number)nr2mMult((number)j, (number)k, r);
335 }
336 
337 /*
338  * convert a number to an int in ]-k/2 .. k/2],
339  * where k = 2^m; i.e., an int in ]-2^(m-1) .. 2^(m-1)];
340  */
341 static long nr2mInt(number &n, const coeffs r)
342 {
343  unsigned long nn = (unsigned long)(unsigned long)n & r->mod2mMask;
344  unsigned long l = r->mod2mMask >> 1; l++; /* now: l = 2^(m-1) */
345  if ((unsigned long)nn > l)
346  return (long)((unsigned long)nn - r->mod2mMask - 1);
347  else
348  return (long)((unsigned long)nn);
349 }
350 
351 static number nr2mAdd(number a, number b, const coeffs r)
352 {
353  return nr2mAddM(a, b, r);
354 }
355 
356 static number nr2mSub(number a, number b, const coeffs r)
357 {
358  return nr2mSubM(a, b, r);
359 }
360 
361 static BOOLEAN nr2mIsUnit(number a, const coeffs)
362 {
363  return ((unsigned long)a % 2 == 1);
364 }
365 
366 static number nr2mGetUnit(number k, const coeffs)
367 {
368  if (k == NULL) return (number)1;
369  unsigned long erg = (unsigned long)k;
370  while (erg % 2 == 0) erg = erg / 2;
371  return (number)erg;
372 }
373 
374 static BOOLEAN nr2mIsZero(number a, const coeffs)
375 {
376  return 0 == (unsigned long)a;
377 }
378 
379 static BOOLEAN nr2mIsOne(number a, const coeffs)
380 {
381  return 1 == (unsigned long)a;
382 }
383 
384 static BOOLEAN nr2mIsMOne(number a, const coeffs r)
385 {
386  return ((r->mod2mMask == (unsigned long)a) &&(1L!=(long)a))/*for char 2^1*/;
387 }
388 
389 static BOOLEAN nr2mEqual(number a, number b, const coeffs)
390 {
391  return (a == b);
392 }
393 
394 static number nr2mDiv(number a, number b, const coeffs r)
395 {
396  if ((unsigned long)a == 0) return (number)0;
397  else if ((unsigned long)b % 2 == 0)
398  {
399  if ((unsigned long)b != 0)
400  {
401  while (((unsigned long)b % 2 == 0) && ((unsigned long)a % 2 == 0))
402  {
403  a = (number)((unsigned long)a / 2);
404  b = (number)((unsigned long)b / 2);
405  }
406  }
407  if ((unsigned long)b % 2 == 0)
408  {
409  WerrorS("Division not possible, even by cancelling zero divisors.");
410  WerrorS("Result is integer division without remainder.");
411  return (number) ((unsigned long) a / (unsigned long) b);
412  }
413  }
414  return (number)nr2mMult(a, nr2mInversM(b,r),r);
415 }
416 
417 /* Is 'a' divisible by 'b'? There are two cases:
418  1) a = 0 mod 2^m; then TRUE iff b = 0 or b is a power of 2
419  2) a, b <> 0; then TRUE iff b/gcd(a, b) is a unit mod 2^m */
420 static BOOLEAN nr2mDivBy (number a, number b, const coeffs r)
421 {
422  if (a == NULL)
423  {
424  unsigned long c = r->mod2mMask + 1;
425  if (c != 0) /* i.e., if no overflow */
426  return (c % (unsigned long)b) == 0;
427  else
428  {
429  /* overflow: we need to check whether b
430  is zero or a power of 2: */
431  c = (unsigned long)b;
432  while (c != 0)
433  {
434  if ((c % 2) != 0) return FALSE;
435  c = c >> 1;
436  }
437  return TRUE;
438  }
439  }
440  else
441  {
442  number n = nr2mGcd(a, b, r);
443  n = nr2mDiv(b, n, r);
444  return nr2mIsUnit(n, r);
445  }
446 }
447 
448 static BOOLEAN nr2mGreater(number a, number b, const coeffs r)
449 {
450  return nr2mDivBy(a, b,r);
451 }
452 
453 static int nr2mDivComp(number as, number bs, const coeffs)
454 {
455  unsigned long a = (unsigned long)as;
456  unsigned long b = (unsigned long)bs;
457  assume(a != 0 && b != 0);
458  while (a % 2 == 0 && b % 2 == 0)
459  {
460  a = a / 2;
461  b = b / 2;
462  }
463  if (a % 2 == 0)
464  {
465  return -1;
466  }
467  else
468  {
469  if (b % 2 == 1)
470  {
471  return 2;
472  }
473  else
474  {
475  return 1;
476  }
477  }
478 }
479 
480 static number nr2mMod(number a, number b, const coeffs r)
481 {
482  /*
483  We need to return the number rr which is uniquely determined by the
484  following two properties:
485  (1) 0 <= rr < |b| (with respect to '<' and '<=' performed in Z x Z)
486  (2) There exists some k in the integers Z such that a = k * b + rr.
487  Consider g := gcd(2^m, |b|). Note that then |b|/g is a unit in Z/2^m.
488  Now, there are three cases:
489  (a) g = 1
490  Then |b| is a unit in Z/2^m, i.e. |b| (and also b) divides a.
491  Thus rr = 0.
492  (b) g <> 1 and g divides a
493  Then a = (a/g) * (|b|/g)^(-1) * b (up to sign), i.e. again rr = 0.
494  (c) g <> 1 and g does not divide a
495  Let's denote the division with remainder of a by g as follows:
496  a = s * g + t. Then t = a - s * g = a - s * (|b|/g)^(-1) * |b|
497  fulfills (1) and (2), i.e. rr := t is the correct result. Hence
498  in this third case, rr is the remainder of division of a by g in Z.
499  This algorithm is the same as for the case Z/n, except that we may
500  compute the gcd of |b| and 2^m "by hand": We just extract the highest
501  power of 2 (<= 2^m) that is contained in b.
502  */
503  assume((unsigned long) b != 0);
504  unsigned long g = 1;
505  unsigned long b_div = (unsigned long) b;
506 
507  /*
508  * b_div is unsigned, so that (b_div < 0) evaluates false at compile-time
509  *
510  if (b_div < 0) b_div = -b_div; // b_div now represents |b|, BUT b_div is unsigned!
511  */
512 
513  unsigned long rr = 0;
514  while ((g < r->mod2mMask ) && (b_div > 0) && (b_div % 2 == 0))
515  {
516  b_div = b_div >> 1;
517  g = g << 1;
518  } // g is now the gcd of 2^m and |b|
519 
520  if (g != 1) rr = (unsigned long)a % g;
521  return (number)rr;
522 }
523 
524 #if 0
525 // unused
526 static number nr2mIntDiv(number a, number b, const coeffs r)
527 {
528  if ((unsigned long)a == 0)
529  {
530  if ((unsigned long)b == 0)
531  return (number)1;
532  if ((unsigned long)b == 1)
533  return (number)0;
534  unsigned long c = r->mod2mMask + 1;
535  if (c != 0) /* i.e., if no overflow */
536  return (number)(c / (unsigned long)b);
537  else
538  {
539  /* overflow: c = 2^32 resp. 2^64, depending on platform */
540  mpz_ptr cc = (mpz_ptr)omAlloc(sizeof(mpz_t));
541  mpz_init_set_ui(cc, r->mod2mMask); mpz_add_ui(cc, cc, 1);
542  mpz_div_ui(cc, cc, (unsigned long)(unsigned long)b);
543  unsigned long s = mpz_get_ui(cc);
544  mpz_clear(cc); omFree((ADDRESS)cc);
545  return (number)(unsigned long)s;
546  }
547  }
548  else
549  {
550  if ((unsigned long)b == 0)
551  return (number)0;
552  return (number)((unsigned long) a / (unsigned long) b);
553  }
554 }
555 #endif
556 
557 static number nr2mAnn(number b, const coeffs r)
558 {
559  if ((unsigned long)b == 0)
560  return NULL;
561  if ((unsigned long)b == 1)
562  return NULL;
563  unsigned long c = r->mod2mMask + 1;
564  if (c != 0) /* i.e., if no overflow */
565  return (number)(c / (unsigned long)b);
566  else
567  {
568  /* overflow: c = 2^32 resp. 2^64, depending on platform */
569  mpz_ptr cc = (mpz_ptr)omAlloc(sizeof(mpz_t));
570  mpz_init_set_ui(cc, r->mod2mMask); mpz_add_ui(cc, cc, 1);
571  mpz_div_ui(cc, cc, (unsigned long)(unsigned long)b);
572  unsigned long s = mpz_get_ui(cc);
573  mpz_clear(cc); omFree((ADDRESS)cc);
574  return (number)(unsigned long)s;
575  }
576 }
577 
578 static number nr2mNeg(number c, const coeffs r)
579 {
580  if ((unsigned long)c == 0) return c;
581  return nr2mNegM(c, r);
582 }
583 
584 static number nr2mMapMachineInt(number from, const coeffs /*src*/, const coeffs dst)
585 {
586  unsigned long i = ((unsigned long)from) % dst->mod2mMask ;
587  return (number)i;
588 }
589 
590 static number nr2mMapProject(number from, const coeffs /*src*/, const coeffs dst)
591 {
592  unsigned long i = ((unsigned long)from) % (dst->mod2mMask + 1);
593  return (number)i;
594 }
595 
596 number nr2mMapZp(number from, const coeffs /*src*/, const coeffs dst)
597 {
598  unsigned long j = (unsigned long)1;
599  long ii = (long)from;
600  if (ii < 0) { j = dst->mod2mMask; ii = -ii; }
601  unsigned long i = (unsigned long)ii;
602  i = i & dst->mod2mMask;
603  /* now we have: from = j * i mod 2^m */
604  return (number)nr2mMult((number)i, (number)j, dst);
605 }
606 
607 static number nr2mMapGMP(number from, const coeffs /*src*/, const coeffs dst)
608 {
609  mpz_ptr erg = (mpz_ptr)omAllocBin(gmp_nrz_bin);
610  mpz_init(erg);
611  mpz_ptr k = (mpz_ptr)omAlloc(sizeof(mpz_t));
612  mpz_init_set_ui(k, dst->mod2mMask);
613 
614  mpz_and(erg, (mpz_ptr)from, k);
615  number res = (number) mpz_get_ui(erg);
616 
617  mpz_clear(erg); omFree((ADDRESS)erg);
618  mpz_clear(k); omFree((ADDRESS)k);
619 
620  return (number)res;
621 }
622 
623 static number nr2mMapQ(number from, const coeffs src, const coeffs dst)
624 {
625  mpz_ptr gmp = (mpz_ptr)omAllocBin(gmp_nrz_bin);
626  mpz_init(gmp);
627  nlGMP(from, (number)gmp, src); // FIXME? TODO? // extern void nlGMP(number &i, number n, const coeffs r); // to be replaced with n_MPZ(erg, from, src); // ?
628  number res=nr2mMapGMP((number)gmp,src,dst);
629  mpz_clear(gmp); omFree((ADDRESS)gmp);
630  return res;
631 }
632 
633 static number nr2mMapZ(number from, const coeffs src, const coeffs dst)
634 {
635  if (SR_HDL(from) & SR_INT)
636  {
637  long f_i=SR_TO_INT(from);
638  return nr2mInit(f_i,dst);
639  }
640  return nr2mMapGMP(from,src,dst);
641 }
642 
643 static nMapFunc nr2mSetMap(const coeffs src, const coeffs dst)
644 {
645  if ((src->rep==n_rep_int) && nCoeff_is_Ring_2toM(src)
646  && (src->mod2mMask == dst->mod2mMask))
647  {
648  return ndCopyMap;
649  }
650  if ((src->rep==n_rep_int) && nCoeff_is_Ring_2toM(src)
651  && (src->mod2mMask < dst->mod2mMask))
652  { /* i.e. map an integer mod 2^s into Z mod 2^t, where t < s */
653  return nr2mMapMachineInt;
654  }
655  if ((src->rep==n_rep_int) && nCoeff_is_Ring_2toM(src)
656  && (src->mod2mMask > dst->mod2mMask))
657  { /* i.e. map an integer mod 2^s into Z mod 2^t, where t > s */
658  // to be done
659  return nr2mMapProject;
660  }
661  if ((src->rep==n_rep_gmp) && nCoeff_is_Ring_Z(src))
662  {
663  return nr2mMapGMP;
664  }
665  if ((src->rep==n_rep_gap_gmp) /*&& nCoeff_is_Ring_Z(src)*/)
666  {
667  return nr2mMapZ;
668  }
669  if ((src->rep==n_rep_gap_rat) && (nCoeff_is_Q(src)||nCoeff_is_Ring_Z(src)))
670  {
671  return nr2mMapQ;
672  }
673  if ((src->rep==n_rep_int) && nCoeff_is_Zp(src) && (src->ch == 2))
674  {
675  return nr2mMapZp;
676  }
677  if ((src->rep==n_rep_gmp) &&
679  {
680  if (mpz_divisible_2exp_p(src->modNumber,dst->modExponent))
681  return nr2mMapGMP;
682  }
683  return NULL; // default
684 }
685 
686 /*
687  * set the exponent
688  */
689 
690 static void nr2mSetExp(int m, coeffs r)
691 {
692  if (m > 1)
693  {
694  /* we want mod2mMask to be the bit pattern
695  '111..1' consisting of m one's: */
696  r->modExponent= m;
697  r->mod2mMask = 1;
698  for (int i = 1; i < m; i++) r->mod2mMask = (r->mod2mMask << 1) + 1;
699  }
700  else
701  {
702  r->modExponent= 2;
703  /* code unexpectedly called with m = 1; we continue with m = 2: */
704  r->mod2mMask = 3; /* i.e., '11' in binary representation */
705  }
706 }
707 
708 static void nr2mInitExp(int m, coeffs r)
709 {
710  nr2mSetExp(m, r);
711  if (m < 2)
712  WarnS("nr2mInitExp unexpectedly called with m = 1 (we continue with Z/2^2");
713 }
714 
715 #ifdef LDEBUG
716 static BOOLEAN nr2mDBTest (number a, const char *, const int, const coeffs r)
717 {
718  //if ((unsigned long)a < 0) return FALSE; // is unsigned!
719  if (((unsigned long)a & r->mod2mMask) != (unsigned long)a) return FALSE;
720  return TRUE;
721 }
722 #endif
723 
724 static void nr2mWrite (number a, const coeffs r)
725 {
726  long i = nr2mInt(a, r);
727  StringAppend("%ld", i);
728 }
729 
730 static const char* nr2mEati(const char *s, int *i, const coeffs r)
731 {
732 
733  if (((*s) >= '0') && ((*s) <= '9'))
734  {
735  (*i) = 0;
736  do
737  {
738  (*i) *= 10;
739  (*i) += *s++ - '0';
740  if ((*i) >= (MAX_INT_VAL / 10)) (*i) = (*i) & r->mod2mMask;
741  }
742  while (((*s) >= '0') && ((*s) <= '9'));
743  (*i) = (*i) & r->mod2mMask;
744  }
745  else (*i) = 1;
746  return s;
747 }
748 
749 static const char * nr2mRead (const char *s, number *a, const coeffs r)
750 {
751  int z;
752  int n=1;
753 
754  s = nr2mEati(s, &z,r);
755  if ((*s) == '/')
756  {
757  s++;
758  s = nr2mEati(s, &n,r);
759  }
760  if (n == 1)
761  *a = (number)(long)z;
762  else
763  *a = nr2mDiv((number)(long)z,(number)(long)n,r);
764  return s;
765 }
766 
767 /* for initializing function pointers */
769 {
770  assume( getCoeffType(r) == n_Z2m );
771  nr2mInitExp((int)(long)(p), r);
772 
773  r->is_field=FALSE;
774  r->is_domain=FALSE;
775  r->rep=n_rep_int;
776 
777  //r->cfKillChar = ndKillChar; /* dummy*/
778  r->nCoeffIsEqual = nr2mCoeffIsEqual;
779  r->cfCoeffString = nr2mCoeffString;
780 
781  r->modBase = (mpz_ptr) omAllocBin (gmp_nrz_bin);
782  mpz_init_set_si (r->modBase, 2L);
783  r->modNumber= (mpz_ptr) omAllocBin (gmp_nrz_bin);
784  mpz_init (r->modNumber);
785  mpz_pow_ui (r->modNumber, r->modBase, r->modExponent);
786 
787  /* next cast may yield an overflow as mod2mMask is an unsigned long */
788  r->ch = (int)r->mod2mMask + 1;
789 
790  r->cfInit = nr2mInit;
791  //r->cfCopy = ndCopy;
792  r->cfInt = nr2mInt;
793  r->cfAdd = nr2mAdd;
794  r->cfSub = nr2mSub;
795  r->cfMult = nr2mMult;
796  r->cfDiv = nr2mDiv;
797  r->cfAnn = nr2mAnn;
798  r->cfIntMod = nr2mMod;
799  r->cfExactDiv = nr2mDiv;
800  r->cfInpNeg = nr2mNeg;
801  r->cfInvers = nr2mInvers;
802  r->cfDivBy = nr2mDivBy;
803  r->cfDivComp = nr2mDivComp;
804  r->cfGreater = nr2mGreater;
805  r->cfEqual = nr2mEqual;
806  r->cfIsZero = nr2mIsZero;
807  r->cfIsOne = nr2mIsOne;
808  r->cfIsMOne = nr2mIsMOne;
809  r->cfGreaterZero = nr2mGreaterZero;
810  r->cfWriteLong = nr2mWrite;
811  r->cfRead = nr2mRead;
812  r->cfPower = nr2mPower;
813  r->cfSetMap = nr2mSetMap;
814 // r->cfNormalize = ndNormalize; // default
815  r->cfLcm = nr2mLcm;
816  r->cfGcd = nr2mGcd;
817  r->cfIsUnit = nr2mIsUnit;
818  r->cfGetUnit = nr2mGetUnit;
819  r->cfExtGcd = nr2mExtGcd;
820  r->cfCoeffWrite = nr2mCoeffWrite;
821  r->cfCoeffName = nr2mCoeffName;
822  r->cfQuot1 = nr2mQuot1;
823 #ifdef LDEBUG
824  r->cfDBTest = nr2mDBTest;
825 #endif
826  r->has_simple_Alloc=TRUE;
827  return FALSE;
828 }
829 
830 #endif
831 /* #ifdef HAVE_RINGS */
mpz_t z
Definition: longrat.h:51
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
static number nr2mMultM(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:27
static void nr2mSetExp(int m, coeffs r)
Definition: rmodulo2m.cc:690
const CanonicalForm int s
Definition: facAbsFact.cc:55
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_ModN(const coeffs r)
Definition: coeffs.h:753
static BOOLEAN nr2mGreater(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:448
const poly a
Definition: syzextra.cc:212
omBin_t * omBin
Definition: omStructs.h:12
#define Print
Definition: emacs.cc:83
static char * nr2mCoeffName(const coeffs cf)
Definition: rmodulo2m.cc:51
static FORCE_INLINE BOOLEAN nCoeff_is_Zp(const coeffs r)
Definition: coeffs.h:834
static number nr2mLcm(number a, number b, const coeffs)
Definition: rmodulo2m.cc:144
static number nr2mAnn(number b, const coeffs r)
Definition: rmodulo2m.cc:557
static BOOLEAN nr2mDivBy(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:420
static void nr2mWrite(number a, const coeffs r)
Definition: rmodulo2m.cc:724
only used if HAVE_RINGS is defined
Definition: coeffs.h:46
#define FALSE
Definition: auxiliary.h:94
return P p
Definition: myNF.cc:203
number ndCopyMap(number a, const coeffs aRing, const coeffs r)
Definition: numbers.cc:244
static unsigned long InvMod(unsigned long a, const coeffs r)
Definition: rmodulo2m.cc:249
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_Z(const coeffs r)
Definition: coeffs.h:759
static number nr2mMapGMP(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:607
{p < 2^31}
Definition: coeffs.h:30
#define nr2mNegM(A, r)
Definition: rmodulo2m.cc:46
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_2toM(const coeffs r)
Definition: coeffs.h:750
(), see rinteger.h, new impl.
Definition: coeffs.h:112
static long nr2mInt(number &n, const coeffs r)
Definition: rmodulo2m.cc:341
static number nr2mDiv(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:394
#define TRUE
Definition: auxiliary.h:98
static number nr2mGetUnit(number k, const coeffs)
Definition: rmodulo2m.cc:366
static BOOLEAN nr2mIsZero(number a, const coeffs)
Definition: rmodulo2m.cc:374
number nr2mMapZp(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:596
static number nr2mMapMachineInt(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:584
void * ADDRESS
Definition: auxiliary.h:115
g
Definition: cfModGcd.cc:4031
void WerrorS(const char *s)
Definition: feFopen.cc:24
int k
Definition: cfEzgcd.cc:93
BOOLEAN nr2mInitChar(coeffs r, void *p)
Definition: rmodulo2m.cc:768
void nlGMP(number &i, number n, const coeffs r)
Definition: longrat.cc:1467
static FORCE_INLINE BOOLEAN nCoeff_is_Q(const coeffs r)
Definition: coeffs.h:840
#define WarnS
Definition: emacs.cc:81
#define omAlloc(size)
Definition: omAllocDecl.h:210
static BOOLEAN nr2mCoeffIsEqual(const coeffs r, n_coeffType n, void *p)
Definition: rmodulo2m.cc:64
static number nr2mNeg(number c, const coeffs r)
Definition: rmodulo2m.cc:578
static BOOLEAN nr2mIsOne(number a, const coeffs)
Definition: rmodulo2m.cc:379
poly res
Definition: myNF.cc:322
static number nr2mMapProject(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:590
mpz_t n
Definition: longrat.h:52
const ring r
Definition: syzextra.cc:208
#define LDEBUG
Definition: mod2.h:312
Coefficient rings, fields and other domains suitable for Singular polynomials.
static const char * nr2mRead(const char *s, number *a, const coeffs r)
Definition: rmodulo2m.cc:749
int j
Definition: myNF.cc:70
#define omFree(addr)
Definition: omAllocDecl.h:261
#define assume(x)
Definition: mod2.h:394
The main handler for Singular numbers which are suitable for Singular polynomials.
static number nr2mInversM(number c, const coeffs r)
Definition: rmodulo2m.cc:257
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition: coeffs.h:73
static coeffs nr2mQuot1(number c, const coeffs r)
Definition: rmodulo2m.cc:83
static char * nr2mCoeffString(const coeffs r)
Definition: rmodulo2m.cc:75
const int MAX_INT_VAL
Definition: mylimits.h:12
All the auxiliary stuff.
int m
Definition: cfEzgcd.cc:119
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_PtoM(const coeffs r)
Definition: coeffs.h:756
static int nr2mDivComp(number as, number bs, const coeffs)
Definition: rmodulo2m.cc:453
#define StringAppend
Definition: emacs.cc:82
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:284
static void nr2mInitExp(int m, coeffs r)
Definition: rmodulo2m.cc:708
static BOOLEAN nr2mGreaterZero(number k, const coeffs r)
Definition: rmodulo2m.cc:122
(mpz_ptr), see rmodulon,h
Definition: coeffs.h:115
static FORCE_INLINE n_coeffType getCoeffType(const coeffs r)
Returns the type of coeffs domain.
Definition: coeffs.h:425
static const char * nr2mEati(const char *s, int *i, const coeffs r)
Definition: rmodulo2m.cc:730
static number nr2mMult(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:132
static BOOLEAN nr2mDBTest(number a, const char *, const int, const coeffs r)
Definition: rmodulo2m.cc:716
#define SR_TO_INT(SR)
Definition: longrat.h:70
(number), see longrat.h
Definition: coeffs.h:111
static number nr2mExtGcd(number a, number b, number *s, number *t, const coeffs r)
Definition: rmodulo2m.cc:280
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
static BOOLEAN nr2mIsMOne(number a, const coeffs r)
Definition: rmodulo2m.cc:384
n_coeffType
Definition: coeffs.h:27
CanonicalForm cf
Definition: cfModGcd.cc:4024
#define NULL
Definition: omList.c:10
static BOOLEAN nr2mEqual(number a, number b, const coeffs)
Definition: rmodulo2m.cc:389
static number nr2mInvers(number c, const coeffs r)
Definition: rmodulo2m.cc:266
static number nr2mAddM(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:33
static number nr2mSub(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:356
int gcd(int a, int b)
Definition: walkSupport.cc:839
#define SR_INT
Definition: longrat.h:68
static BOOLEAN nr2mIsUnit(number a, const coeffs)
Definition: rmodulo2m.cc:361
static void nr2mCoeffWrite(const coeffs r, BOOLEAN)
Definition: rmodulo2m.cc:58
static number nr2mMapQ(number from, const coeffs src, const coeffs dst)
Definition: rmodulo2m.cc:623
static number nr2mSubM(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:39
static number nr2mInit(long i, const coeffs r)
Definition: rmodulo2m.cc:324
omBin gmp_nrz_bin
Definition: rintegers.cc:76
(int), see modulop.h
Definition: coeffs.h:110
#define SR_HDL(A)
Definition: tgb.cc:35
static number nr2mGcd(number a, number b, const coeffs)
Definition: rmodulo2m.cc:167
static number nr2mAdd(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:351
static number nr2mMapZ(number from, const coeffs src, const coeffs dst)
Definition: rmodulo2m.cc:633
int BOOLEAN
Definition: auxiliary.h:85
const poly b
Definition: syzextra.cc:213
static void nr2mPower(number a, int i, number *result, const coeffs r)
Definition: rmodulo2m.cc:304
static nMapFunc nr2mSetMap(const coeffs src, const coeffs dst)
Definition: rmodulo2m.cc:643
static number nr2mMod(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:480
int l
Definition: cfEzgcd.cc:94
return result
Definition: facAbsBiFact.cc:76
static void specialXGCD(unsigned long &s, unsigned long a, const coeffs r)
Definition: rmodulo2m.cc:191
coeffs nInitChar(n_coeffType t, void *parameter)
one-time initialisations for new coeffs in case of an error return NULL
Definition: numbers.cc:334