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