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