# source:git/kernel/rmodulo2m.cc@ac05e22

spielwiese
Last change on this file since ac05e22 was ac05e22, checked in by Hans Schoenemann <hannes@…>, 12 years ago
• Property mode set to `100644`
File size: 14.4 KB
Line
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* \$Id\$ */
5/*
6* ABSTRACT: numbers modulo 2^m
7*/
8
9#include <string.h>
10#include <kernel/mod2.h>
11
12#ifdef HAVE_RINGS
13#include <omalloc/mylimits.h>
14#include <kernel/structs.h>
15#include <kernel/febase.h>
16#include <omalloc/omalloc.h>
17#include <kernel/numbers.h>
18#include <kernel/longrat.h>
19#include <kernel/mpr_complex.h>
20#include <kernel/ring.h>
21#include <kernel/rmodulo2m.h>
22#include <kernel/si_gmp.h>
23
24int nr2mExp;
25
26/*
27 * Multiply two numbers
28 */
29number nr2mMult (number a, number b)
30{
31  if (((NATNUMBER)a == 0) || ((NATNUMBER)b == 0))
32    return (number)0;
33  else
34    return nr2mMultM(a,b);
35}
36
37/*
38 * Give the smallest non unit k, such that a * x = k = b * y has a solution
39 */
40number nr2mLcm (number a,number b,ring r)
41{
42  NATNUMBER res = 0;
43  if ((NATNUMBER) a == 0) a = (number) 1;
44  if ((NATNUMBER) b == 0) b = (number) 1;
45  while ((NATNUMBER) a % 2 == 0)
46  {
47    a = (number) ((NATNUMBER) a / 2);
48    if ((NATNUMBER) b % 2 == 0) b = (number) ((NATNUMBER) b / 2);
49    res++;
50  }
51  while ((NATNUMBER) b % 2 == 0)
52  {
53    b = (number) ((NATNUMBER) b / 2);
54    res++;
55  }
56  return (number) (1L << res);  // (2**res)
57}
58
59/*
60 * Give the largest non unit k, such that a = x * k, b = y * k has
61 * a solution.
62 */
63number nr2mGcd (number a,number b,ring r)
64{
65  NATNUMBER res = 0;
66  if ((NATNUMBER) a == 0 && (NATNUMBER) b == 0) return (number) 1;
67  while ((NATNUMBER) a % 2 == 0 && (NATNUMBER) b % 2 == 0)
68  {
69    a = (number) ((NATNUMBER) a / 2);
70    b = (number) ((NATNUMBER) b / 2);
71    res++;
72  }
73//  if ((NATNUMBER) b % 2 == 0)
74//  {
75//    return (number) ((1L << res));// * (NATNUMBER) a);  // (2**res)*a    a ist Einheit
76//  }
77//  else
78//  {
79    return (number) ((1L << res));// * (NATNUMBER) b);  // (2**res)*b    b ist Einheit
80//  }
81}
82
83/*
84 * Give the largest non unit k, such that a = x * k, b = y * k has
85 * a solution.
86 */
87number nr2mExtGcd (number a, number b, number *s, number *t)
88{
89  NATNUMBER res = 0;
90  if ((NATNUMBER) a == 0 && (NATNUMBER) b == 0) return (number) 1;
91  while ((NATNUMBER) a % 2 == 0 && (NATNUMBER) b % 2 == 0)
92  {
93    a = (number) ((NATNUMBER) a / 2);
94    b = (number) ((NATNUMBER) b / 2);
95    res++;
96  }
97  if ((NATNUMBER) b % 2 == 0)
98  {
99    *t = NULL;
100    *s = nr2mInvers(a);
101    return (number) ((1L << res));// * (NATNUMBER) a);  // (2**res)*a    a ist Einheit
102  }
103  else
104  {
105    *s = NULL;
106    *t = nr2mInvers(b);
107    return (number) ((1L << res));// * (NATNUMBER) b);  // (2**res)*b    b ist Einheit
108  }
109}
110
111void nr2mPower (number a, int i, number * result)
112{
113  if (i==0)
114  {
115    *(NATNUMBER *)result = 1;
116  }
117  else if (i==1)
118  {
119    *result = a;
120  }
121  else
122  {
123    nr2mPower(a,i-1,result);
124    *result = nr2mMultM(a,*result);
125  }
126}
127
128/*
129 * create a number from int
130 */
131number nr2mInit (int i, const ring r)
132{
133  if (i == 0) return (number)(NATNUMBER)i;
134
135  long ii = i;
136  NATNUMBER j = (NATNUMBER)1;
137  if (ii < 0) { j = currRing->nr2mModul; ii = -ii; }
138  NATNUMBER k = (NATNUMBER)ii;
139  k = k & currRing->nr2mModul;
140  /* now we have: from = j * k mod 2^m */
141  return (number)nr2mMult((number)j, (number)k);
142}
143
144/*
145 * convert a number to an int in ]-k/2 .. k/2],
146 * where k = 2^m; i.e., an int in ]-2^(m-1) .. 2^(m-1)];
147 * note that the code computes a long which will then
148 * automatically casted to int
149 */
150int nr2mInt(number &n, const ring r)
151{
152  NATNUMBER nn = (unsigned long)(NATNUMBER)n & r->nr2mModul;
153  unsigned long l = r->nr2mModul >> 1; l++; /* now: l = 2^(m-1) */
154  if ((NATNUMBER)nn > l)
155    return (int)((NATNUMBER)nn - r->nr2mModul - 1);
156  else
157    return (int)((NATNUMBER)nn);
158}
159
160number nr2mAdd (number a, number b)
161{
163}
164
165number nr2mSub (number a, number b)
166{
167  return nr2mSubM(a,b);
168}
169
170BOOLEAN nr2mIsUnit (number a)
171{
172  return ((NATNUMBER) a % 2 == 1);
173}
174
175number  nr2mGetUnit (number k)
176{
177  if (k == NULL)
178    return (number) 1;
179  NATNUMBER tmp = (NATNUMBER) k;
180  while (tmp % 2 == 0)
181    tmp = tmp / 2;
182  return (number) tmp;
183}
184
185BOOLEAN nr2mIsZero (number  a)
186{
187  return 0 == (NATNUMBER)a;
188}
189
190BOOLEAN nr2mIsOne (number a)
191{
192  return 1 == (NATNUMBER)a;
193}
194
195BOOLEAN nr2mIsMOne (number a)
196{
197  return (currRing->nr2mModul == (NATNUMBER)a);
198}
199
200BOOLEAN nr2mEqual (number a, number b)
201{
202  return nr2mEqualM(a,b);
203}
204
205BOOLEAN nr2mGreater (number a, number b)
206{
207  return nr2mDivBy(a, b);
208}
209
210/* Is a divisible by b? There are two cases:
211   1) a = 0 mod 2^m; then TRUE iff b = 0 or b is a power of 2
212   2) a, b <> 0; then TRUE iff b/gcd(a, b) is a unit mod 2^m
213   TRUE iff b(gcd(a, b) is a unit */
214BOOLEAN nr2mDivBy (number a, number b)
215{
216  if (a == NULL)
217  {
218    NATNUMBER c = currRing->nr2mModul + 1;
219    if (c != 0) /* i.e., if no overflow */
220      return (c % (NATNUMBER)b) == 0;
221    else
222    {
223      /* overflow: we need to check whether b
224         is zero or a power of 2: */
225      c = (NATNUMBER)b;
226      while (c != 0)
227      {
228        if ((c % 2) != 0) return FALSE;
229        c = c >> 1;
230      }
231      return TRUE;
232    }
233  }
234  else
235  {
236    number n = nr2mGcd(a, b, currRing);
237    n = nr2mDiv(b, n);
238    return nr2mIsUnit(n);
239  }
240}
241
242int nr2mDivComp(number as, number bs)
243{
244  NATNUMBER a = (NATNUMBER) as;
245  NATNUMBER b = (NATNUMBER) bs;
246  assume(a != 0 && b != 0);
247  while (a % 2 == 0 && b % 2 == 0)
248  {
249    a = a / 2;
250    b = b / 2;
251  }
252  if (a % 2 == 0)
253  {
254    return -1;
255  }
256  else
257  {
258    if (b % 2 == 1)
259    {
260      return 2;
261    }
262    else
263    {
264      return 1;
265    }
266  }
267}
268
269/* TRUE iff 0 < k <= 2^m / 2 */
270BOOLEAN nr2mGreaterZero (number k)
271{
272  if ((NATNUMBER)k == 0) return FALSE;
273  if ((NATNUMBER)k > ((currRing->nr2mModul >> 1) + 1)) return FALSE;
274  return TRUE;
275}
276
277/* assumes that 'a' is odd, i.e., a unit in Z/2^m, and computes
278   the extended gcd of 'a' and 2^m, in order to find some 's'
279   and 't' such that a * s + 2^m * t = gcd(a, 2^m) = 1;
280   this code will always find a positive 's' */
281void specialXGCD(unsigned long& s, unsigned long a)
282{
283  int_number u = (int_number)omAlloc(sizeof(mpz_t));
284  mpz_init_set_ui(u, a);
285  int_number u0 = (int_number)omAlloc(sizeof(mpz_t));
286  mpz_init(u0);
287  int_number u1 = (int_number)omAlloc(sizeof(mpz_t));
288  mpz_init_set_ui(u1, 1);
289  int_number u2 = (int_number)omAlloc(sizeof(mpz_t));
290  mpz_init(u2);
291  int_number v = (int_number)omAlloc(sizeof(mpz_t));
292  mpz_init_set_ui(v, currRing->nr2mModul);
293  mpz_add_ui(v, v, 1); /* now: v = 2^m */
294  int_number v0 = (int_number)omAlloc(sizeof(mpz_t));
295  mpz_init(v0);
296  int_number v1 = (int_number)omAlloc(sizeof(mpz_t));
297  mpz_init(v1);
298  int_number v2 = (int_number)omAlloc(sizeof(mpz_t));
299  mpz_init_set_ui(v2, 1);
300  int_number q = (int_number)omAlloc(sizeof(mpz_t));
301  mpz_init(q);
302  int_number r = (int_number)omAlloc(sizeof(mpz_t));
303  mpz_init(r);
304
305  while (mpz_cmp_ui(v, 0) != 0) /* i.e., while v != 0 */
306  {
307    mpz_div(q, u, v);
308    mpz_mod(r, u, v);
309    mpz_set(u, v);
310    mpz_set(v, r);
311    mpz_set(u0, u2);
312    mpz_set(v0, v2);
313    mpz_mul(u2, u2, q); mpz_sub(u2, u1, u2); /* u2 = u1 - q * u2 */
314    mpz_mul(v2, v2, q); mpz_sub(v2, v1, v2); /* v2 = v1 - q * v2 */
315    mpz_set(u1, u0);
316    mpz_set(v1, v0);
317  }
318
319  while (mpz_cmp_ui(u1, 0) < 0) /* i.e., while u1 < 0 */
320  {
321    /* we add 2^m = (2^m - 1) + 1 to u1: */
324  }
325  s = mpz_get_ui(u1); /* now: 0 <= s <= 2^m - 1 */
326
337}
338
339NATNUMBER InvMod(NATNUMBER a)
340{
341  assume((NATNUMBER)a % 2 != 0);
342  unsigned long s;
343  specialXGCD(s, a);
344  return s;
345}
346//#endif
347
348inline number nr2mInversM (number c)
349{
350  assume((NATNUMBER)c % 2 != 0);
351  return (number)InvMod((NATNUMBER)c);
352}
353
354number nr2mDiv (number a,number b)
355{
356  if ((NATNUMBER)a==0)
357    return (number)0;
358  else if ((NATNUMBER)b%2==0)
359  {
360    if ((NATNUMBER)b != 0)
361    {
362      while ((NATNUMBER) b%2 == 0 && (NATNUMBER) a%2 == 0)
363      {
364        a = (number) ((NATNUMBER) a / 2);
365        b = (number) ((NATNUMBER) b / 2);
366      }
367    }
368    if ((NATNUMBER) b%2 == 0)
369    {
370      WerrorS("Division not possible, even by cancelling zero divisors.");
371      WerrorS("Result is integer division without remainder.");
372      return (number) ((NATNUMBER) a / (NATNUMBER) b);
373    }
374  }
375  return (number) nr2mMult(a, nr2mInversM(b));
376}
377
378number nr2mMod (number a, number b)
379{
380  /*
381    We need to return the number r which is uniquely determined by the
382    following two properties:
383      (1) 0 <= r < |b| (with respect to '<' and '<=' performed in Z x Z)
384      (2) There exists some k in the integers Z such that a = k * b + r.
385    Consider g := gcd(2^m, |b|). Note that then |b|/g is a unit in Z/2^m.
386    Now, there are three cases:
387      (a) g = 1
388          Then |b| is a unit in Z/2^m, i.e. |b| (and also b) divides a.
389          Thus r = 0.
390      (b) g <> 1 and g divides a
391          Then a = (a/g) * (|b|/g)^(-1) * b (up to sign), i.e. again r = 0.
392      (c) g <> 1 and g does not divide a
393          Let's denote the division with remainder of a by g as follows:
394          a = s * g + t. Then t = a - s * g = a - s * (|b|/g)^(-1) * |b|
395          fulfills (1) and (2), i.e. r := t is the correct result. Hence
396          in this third case, r is the remainder of division of a by g in Z.
397    This algorithm is the same as for the case Z/n, except that we may
398    compute the gcd of |b| and 2^m "by hand": We just extract the highest
399    power of 2 (<= 2^m) that is contained in b.
400  */
401  assume((NATNUMBER)b != 0);
402  NATNUMBER g = 1;
403  NATNUMBER b_div = (NATNUMBER)b;
404  if (b_div < 0) b_div = -b_div; // b_div now represents |b|
405  NATNUMBER r = 0;
406  while ((g < currRing->nr2mModul) && (b_div > 0) && (b_div % 2 == 0))
407  {
408    b_div = b_div >> 1;
409    g = g << 1;
410  } // g is now the gcd of 2^m and |b|
411
412  if (g != 1) r = (NATNUMBER)a % g;
413  return (number)r;
414}
415
416number nr2mIntDiv (number a, number b)
417{
418  if ((NATNUMBER)a == 0)
419  {
420    if ((NATNUMBER)b == 0)
421      return (number)1;
422    if ((NATNUMBER)b == 1)
423      return (number)0;
424    NATNUMBER c = currRing->nr2mModul + 1;
425    if (c != 0) /* i.e., if no overflow */
426      return (number)(c / (NATNUMBER)b);
427    else
428    {
429      /* overflow: c = 2^32 resp. 2^64, depending on platform */
430      int_number cc = (int_number)omAlloc(sizeof(mpz_t));
431      mpz_init_set_ui(cc, currRing->nr2mModul); mpz_add_ui(cc, cc, 1);
432      mpz_div_ui(cc, cc, (unsigned long)(NATNUMBER)b);
433      unsigned long s = mpz_get_ui(cc);
435      return (number)(NATNUMBER)s;
436    }
437  }
438  else
439  {
440    if ((NATNUMBER)b == 0)
441      return (number)0;
442    return (number)((NATNUMBER) a / (NATNUMBER) b);
443  }
444}
445
446number  nr2mInvers (number c)
447{
448  if ((NATNUMBER)c%2==0)
449  {
450    WerrorS("division by zero divisor");
451    return (number)0;
452  }
453  return nr2mInversM(c);
454}
455
456number nr2mNeg (number c)
457{
458  if ((NATNUMBER)c==0) return c;
459  return nr2mNegM(c);
460}
461
462number nr2mCopy(number a)
463{
464  return a;
465}
466
467number nr2mMapMachineInt(number from)
468{
469  NATNUMBER i = ((NATNUMBER) from) & currRing->nr2mModul;
470  return (number) i;
471}
472
473number nr2mMapZp(number from)
474{
475  long ii = (long)from;
476  NATNUMBER j = (NATNUMBER)1;
477  if (ii < 0) { j = currRing->nr2mModul; ii = -ii; }
478  NATNUMBER i = (NATNUMBER)ii;
479  i = i & currRing->nr2mModul;
480  /* now we have: from = j * i mod 2^m */
481  return (number)nr2mMult((number)i, (number)j);
482}
483
484number nr2mMapQ(number from)
485{
486  int_number erg = (int_number) omAlloc(sizeof(mpz_t));
487  mpz_init(erg);
488  int_number k = (int_number) omAlloc(sizeof(mpz_t));
489  mpz_init_set_ui(k, currRing->nr2mModul);
490
491  nlGMP(from, (number)erg);
492  mpz_and(erg, erg, k);
493  number r = (number)mpz_get_ui(erg);
494
497
498  return (number) r;
499}
500
501number nr2mMapGMP(number from)
502{
503  int_number erg = (int_number) omAlloc(sizeof(mpz_t));
504  mpz_init(erg);
505  int_number k = (int_number) omAlloc(sizeof(mpz_t));
506  mpz_init_set_ui(k, currRing->nr2mModul);
507
508  mpz_and(erg, (int_number)from, k);
509  number r = (number) mpz_get_ui(erg);
510
513
514  return (number) r;
515}
516
517nMapFunc nr2mSetMap(const ring src, const ring dst)
518{
519  if (rField_is_Ring_2toM(src)
520     && (src->ringflagb >= dst->ringflagb))
521  {
522    //return nr2mCopy;
523    return nr2mMapMachineInt;
524  }
525  if (rField_is_Ring_Z(src))
526  {
527    return nr2mMapGMP;
528  }
529  if (rField_is_Q(src))
530  {
531    return nr2mMapQ;
532  }
533  if (rField_is_Zp(src)
534     && (src->ch == 2)
535     && (dst->ringflagb == 1))
536  {
537    return nr2mMapZp;
538  }
539  if (rField_is_Ring_PtoM(src) || rField_is_Ring_ModN(src))
540  {
541    // Computing the n of Z/n
542    int_number modul = (int_number) omAlloc(sizeof(mpz_t)); // evtl. spaeter mit bin
543    mpz_init(modul);
544    mpz_set(modul, src->ringflaga);
545    mpz_pow_ui(modul, modul, src->ringflagb);
546    if (mpz_divisible_2exp_p(modul, dst->ringflagb))
547    {
548      mpz_clear(modul);
550      return nr2mMapGMP;
551    }
552    mpz_clear(modul);
554  }
555  return NULL;      // default
556}
557
558/*
559 * set the exponent (allocate and init tables) (TODO)
560 */
561
562void nr2mSetExp(int m, const ring r)
563{
564  if (m > 1)
565  {
566    nr2mExp = m;
567    /* we want nr2mModul to be the bit pattern '11..1' consisting
568       of m one's: */
569    r->nr2mModul = 1;
570    for (int i = 1; i < m; i++) r->nr2mModul = (r->nr2mModul * 2) + 1;
571  }
572  else
573  {
574    nr2mExp = 2;
575    r->nr2mModul = 3; /* i.e., '11' in binary representation */
576  }
577}
578
579void nr2mInitExp(int m, const ring r)
580{
581  nr2mSetExp(m, r);
582  if (m < 2) WarnS("nr2mInitExp failed: we go on with Z/2^2");
583}
584
585#ifdef LDEBUG
586BOOLEAN nr2mDBTest (number a, const char *f, const int l)
587{
588  if ((NATNUMBER)a < 0) return FALSE;
589  if (((NATNUMBER)a & currRing->nr2mModul) != (NATNUMBER)a) return FALSE;
590  return TRUE;
591}
592#endif
593
594void nr2mWrite (number &a, const ring r)
595{
596  int i = nr2mInt(a, r);
597  StringAppend("%d", i);
598}
599
600static const char* nr2mEati(const char *s, int *i)
601{
602
603  if (((*s) >= '0') && ((*s) <= '9'))
604  {
605    (*i) = 0;
606    do
607    {
608      (*i) *= 10;
609      (*i) += *s++ - '0';
610      if ((*i) >= (MAX_INT_VAL / 10)) (*i) = (*i) & currRing->nr2mModul;
611    }
612    while (((*s) >= '0') && ((*s) <= '9'));
613    (*i) = (*i) & currRing->nr2mModul;
614  }
615  else (*i) = 1;
616  return s;
617}
618
619const char * nr2mRead (const char *s, number *a)
620{
621  int z;
622  int n=1;
623
624  s = nr2mEati(s, &z);
625  if ((*s) == '/')
626  {
627    s++;
628    s = nr2mEati(s, &n);
629  }
630  if (n == 1)
631    *a = (number)z;
632  else
633      *a = nr2mDiv((number)z,(number)n);
634  return s;
635}
636#endif
Note: See TracBrowser for help on using the repository browser.