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