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