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