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