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