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