My Project  UNKNOWN_GIT_VERSION
Macros | Functions | Variables
rmodulo2m.cc File Reference
#include "misc/auxiliary.h"
#include "omalloc/omalloc.h"
#include "misc/mylimits.h"
#include "reporter/reporter.h"
#include "coeffs/si_gmp.h"
#include "coeffs/coeffs.h"
#include "coeffs/numbers.h"
#include "coeffs/longrat.h"
#include "coeffs/mpr_complex.h"
#include "coeffs/rmodulo2m.h"
#include "coeffs/rmodulon.h"
#include <string.h>

Go to the source code of this file.

Macros

#define nr2mNegM(A, r)   (number)((r->mod2mMask+1 - (unsigned long)(A)) & r->mod2mMask)
 
#define nr2mEqualM(A, B)   ((A)==(B))
 

Functions

BOOLEAN nr2mDBTest (number a, const char *f, const int l, const coeffs r)
 
static number nr2mMultM (number a, number b, const coeffs r)
 
static number nr2mAddM (number a, number b, const coeffs r)
 
static number nr2mSubM (number a, number b, const coeffs r)
 
static char * nr2mCoeffName (const coeffs cf)
 
static void nr2mCoeffWrite (const coeffs r, BOOLEAN)
 
static BOOLEAN nr2mCoeffIsEqual (const coeffs r, n_coeffType n, void *p)
 
static char * nr2mCoeffString (const coeffs r)
 
static coeffs nr2mQuot1 (number c, const coeffs r)
 
static BOOLEAN nr2mGreaterZero (number k, const coeffs r)
 
static number nr2mMult (number a, number b, const coeffs r)
 
static number nr2mAnn (number b, const coeffs r)
 
static number nr2mLcm (number a, number b, const coeffs)
 
static number nr2mGcd (number a, number b, const coeffs)
 
static void specialXGCD (unsigned long &s, unsigned long a, const coeffs r)
 
static unsigned long InvMod (unsigned long a, const coeffs r)
 
static number nr2mInversM (number c, const coeffs r)
 
static number nr2mInvers (number c, const coeffs r)
 
static number nr2mExtGcd (number a, number b, number *s, number *t, const coeffs r)
 
static void nr2mPower (number a, int i, number *result, const coeffs r)
 
static number nr2mInit (long i, const coeffs r)
 
static long nr2mInt (number &n, const coeffs r)
 
static number nr2mAdd (number a, number b, const coeffs r)
 
static number nr2mSub (number a, number b, const coeffs r)
 
static BOOLEAN nr2mIsUnit (number a, const coeffs)
 
static number nr2mGetUnit (number k, const coeffs)
 
static BOOLEAN nr2mIsZero (number a, const coeffs)
 
static BOOLEAN nr2mIsOne (number a, const coeffs)
 
static BOOLEAN nr2mIsMOne (number a, const coeffs r)
 
static BOOLEAN nr2mEqual (number a, number b, const coeffs)
 
static number nr2mDiv (number a, number b, const coeffs r)
 
static BOOLEAN nr2mDivBy (number a, number b, const coeffs r)
 
static BOOLEAN nr2mGreater (number a, number b, const coeffs r)
 
static int nr2mDivComp (number as, number bs, const coeffs)
 
static number nr2mMod (number a, number b, const coeffs r)
 
static number nr2mNeg (number c, const coeffs r)
 
static number nr2mMapMachineInt (number from, const coeffs, const coeffs dst)
 
static number nr2mMapProject (number from, const coeffs, const coeffs dst)
 
number nr2mMapZp (number from, const coeffs, const coeffs dst)
 
static number nr2mMapGMP (number from, const coeffs, const coeffs dst)
 
static number nr2mMapQ (number from, const coeffs src, const coeffs dst)
 
static number nr2mMapZ (number from, const coeffs src, const coeffs dst)
 
static nMapFunc nr2mSetMap (const coeffs src, const coeffs dst)
 
static void nr2mSetExp (int m, coeffs r)
 
static void nr2mInitExp (int m, coeffs r)
 
static void nr2mWrite (number a, const coeffs r)
 
static const char * nr2mEati (const char *s, int *i, const coeffs r)
 
static const char * nr2mRead (const char *s, number *a, const coeffs r)
 
BOOLEAN nr2mInitChar (coeffs r, void *p)
 

Variables

omBin gmp_nrz_bin
 

Macro Definition Documentation

◆ nr2mEqualM

#define nr2mEqualM (   A,
  B 
)    ((A)==(B))

Definition at line 60 of file rmodulo2m.cc.

◆ nr2mNegM

#define nr2mNegM (   A,
 
)    (number)((r->mod2mMask+1 - (unsigned long)(A)) & r->mod2mMask)

Definition at line 59 of file rmodulo2m.cc.

Function Documentation

◆ InvMod()

static unsigned long InvMod ( unsigned long  a,
const coeffs  r 
)
static

Definition at line 264 of file rmodulo2m.cc.

265 {
266  assume((unsigned long)a % 2 != 0);
267  unsigned long s;
268  specialXGCD(s, a, r);
269  return s;
270 }

◆ nr2mAdd()

static number nr2mAdd ( number  a,
number  b,
const coeffs  r 
)
static

Definition at line 366 of file rmodulo2m.cc.

367 {
368  number n=nr2mAddM(a, b, r);
369  n_Test(n,r);
370  return n;
371 }

◆ nr2mAddM()

static number nr2mAddM ( number  a,
number  b,
const coeffs  r 
)
inlinestatic

Definition at line 46 of file rmodulo2m.cc.

47 {
48  return (number)
49  ((((unsigned long) a) + ((unsigned long) b)) & r->mod2mMask);
50 }

◆ nr2mAnn()

static number nr2mAnn ( number  b,
const coeffs  r 
)
static

Definition at line 578 of file rmodulo2m.cc.

579 {
580  if ((unsigned long)b == 0)
581  return NULL;
582  if ((unsigned long)b == 1)
583  return NULL;
584  unsigned long c = r->mod2mMask + 1;
585  if (c != 0) /* i.e., if no overflow */
586  return (number)(c / (unsigned long)b);
587  else
588  {
589  /* overflow: c = 2^32 resp. 2^64, depending on platform */
590  mpz_ptr cc = (mpz_ptr)omAlloc(sizeof(mpz_t));
591  mpz_init_set_ui(cc, r->mod2mMask); mpz_add_ui(cc, cc, 1);
592  mpz_div_ui(cc, cc, (unsigned long)(unsigned long)b);
593  unsigned long s = mpz_get_ui(cc);
594  mpz_clear(cc); omFree((ADDRESS)cc);
595  return (number)(unsigned long)s;
596  }
597 }

◆ nr2mCoeffIsEqual()

static BOOLEAN nr2mCoeffIsEqual ( const coeffs  r,
n_coeffType  n,
void *  p 
)
static

Definition at line 79 of file rmodulo2m.cc.

80 {
81  if (n==n_Z2m)
82  {
83  int m=(int)(long)(p);
84  unsigned long mm=r->mod2mMask;
85  if (((mm+1)>>m)==1L) return TRUE;
86  }
87  return FALSE;
88 }

◆ nr2mCoeffName()

static char* nr2mCoeffName ( const coeffs  cf)
static

Definition at line 64 of file rmodulo2m.cc.

65 {
66  static char n2mCoeffName_buf[30];
67  if (cf->modExponent>32) /* for 32/64bit arch.*/
68  snprintf(n2mCoeffName_buf,21,"ZZ/(bigint(2)^%lu)",cf->modExponent);
69  else
70  snprintf(n2mCoeffName_buf,21,"ZZ/(2^%lu)",cf->modExponent);
71  return n2mCoeffName_buf;
72 }

◆ nr2mCoeffString()

static char* nr2mCoeffString ( const coeffs  r)
static

Definition at line 90 of file rmodulo2m.cc.

91 {
92  return omStrDup(nr2mCoeffName(r));
93 }

◆ nr2mCoeffWrite()

static void nr2mCoeffWrite ( const coeffs  r,
BOOLEAN   
)
static

Definition at line 74 of file rmodulo2m.cc.

75 {
77 }

◆ nr2mDBTest()

BOOLEAN nr2mDBTest ( number  a,
const char *  f,
const int  l,
const coeffs  r 
)

Definition at line 28 of file rmodulo2m.cc.

29 {
30  if (((long)a<0L) || ((long)a>(long)r->mod2mMask))
31  {
32  Print("wrong mod 2^n number %ld at %s,%d\n",(long)a,f,l);
33  return FALSE;
34  }
35  return TRUE;
36 }

◆ nr2mDiv()

static number nr2mDiv ( number  a,
number  b,
const coeffs  r 
)
static

Definition at line 413 of file rmodulo2m.cc.

414 {
415  if ((unsigned long)a == 0) return (number)0;
416  else if ((unsigned long)b % 2 == 0)
417  {
418  if ((unsigned long)b != 0)
419  {
420  while (((unsigned long)b % 2 == 0) && ((unsigned long)a % 2 == 0))
421  {
422  a = (number)((unsigned long)a / 2);
423  b = (number)((unsigned long)b / 2);
424  }
425  }
426  if ((unsigned long)b % 2 == 0)
427  {
428  WerrorS("Division not possible, even by cancelling zero divisors.");
429  WerrorS("Result is integer division without remainder.");
430  return (number) ((unsigned long) a / (unsigned long) b);
431  }
432  }
433  number n=(number)nr2mMult(a, nr2mInversM(b,r),r);
434  n_Test(n,r);
435  return n;
436 }

◆ nr2mDivBy()

static BOOLEAN nr2mDivBy ( number  a,
number  b,
const coeffs  r 
)
static

Definition at line 441 of file rmodulo2m.cc.

442 {
443  if (a == NULL)
444  {
445  unsigned long c = r->mod2mMask + 1;
446  if (c != 0) /* i.e., if no overflow */
447  return (c % (unsigned long)b) == 0;
448  else
449  {
450  /* overflow: we need to check whether b
451  is zero or a power of 2: */
452  c = (unsigned long)b;
453  while (c != 0)
454  {
455  if ((c % 2) != 0) return FALSE;
456  c = c >> 1;
457  }
458  return TRUE;
459  }
460  }
461  else
462  {
463  number n = nr2mGcd(a, b, r);
464  n = nr2mDiv(b, n, r);
465  return nr2mIsUnit(n, r);
466  }
467 }

◆ nr2mDivComp()

static int nr2mDivComp ( number  as,
number  bs,
const  coeffs 
)
static

Definition at line 474 of file rmodulo2m.cc.

475 {
476  unsigned long a = (unsigned long)as;
477  unsigned long b = (unsigned long)bs;
478  assume(a != 0 && b != 0);
479  while (a % 2 == 0 && b % 2 == 0)
480  {
481  a = a / 2;
482  b = b / 2;
483  }
484  if (a % 2 == 0)
485  {
486  return -1;
487  }
488  else
489  {
490  if (b % 2 == 1)
491  {
492  return 2;
493  }
494  else
495  {
496  return 1;
497  }
498  }
499 }

◆ nr2mEati()

static const char* nr2mEati ( const char *  s,
int *  i,
const coeffs  r 
)
static

Definition at line 744 of file rmodulo2m.cc.

745 {
746 
747  if (((*s) >= '0') && ((*s) <= '9'))
748  {
749  (*i) = 0;
750  do
751  {
752  (*i) *= 10;
753  (*i) += *s++ - '0';
754  if ((*i) >= (MAX_INT_VAL / 10)) (*i) = (*i) & r->mod2mMask;
755  }
756  while (((*s) >= '0') && ((*s) <= '9'));
757  (*i) = (*i) & r->mod2mMask;
758  }
759  else (*i) = 1;
760  return s;
761 }

◆ nr2mEqual()

static BOOLEAN nr2mEqual ( number  a,
number  b,
const  coeffs 
)
static

Definition at line 408 of file rmodulo2m.cc.

409 {
410  return (a == b);
411 }

◆ nr2mExtGcd()

static number nr2mExtGcd ( number  a,
number  b,
number *  s,
number *  t,
const coeffs  r 
)
static

Definition at line 295 of file rmodulo2m.cc.

296 {
297  unsigned long res = 0;
298  if ((unsigned long)a == 0 && (unsigned long)b == 0) return (number)1;
299  while ((unsigned long)a % 2 == 0 && (unsigned long)b % 2 == 0)
300  {
301  a = (number)((unsigned long)a / 2);
302  b = (number)((unsigned long)b / 2);
303  res++;
304  }
305  if ((unsigned long)b % 2 == 0)
306  {
307  *t = NULL;
308  *s = nr2mInvers(a,r);
309  return (number)((1L << res)); // * (unsigned long) a); // (2**res)*a a is a unit
310  }
311  else
312  {
313  *s = NULL;
314  *t = nr2mInvers(b,r);
315  return (number)((1L << res)); // * (unsigned long) b); // (2**res)*b b is a unit
316  }
317 }

◆ nr2mGcd()

static number nr2mGcd ( number  a,
number  b,
const  coeffs 
)
static

Definition at line 182 of file rmodulo2m.cc.

183 {
184  unsigned long res = 0;
185  if ((unsigned long)a == 0 && (unsigned long)b == 0) return (number)1;
186  while ((unsigned long)a % 2 == 0 && (unsigned long)b % 2 == 0)
187  {
188  a = (number)((unsigned long)a / 2);
189  b = (number)((unsigned long)b / 2);
190  res++;
191  }
192 // if ((unsigned long)b % 2 == 0)
193 // {
194 // return (number)((1L << res)); // * (unsigned long) a); // (2**res)*a a is a unit
195 // }
196 // else
197 // {
198  return (number)((1L << res)); // * (unsigned long) b); // (2**res)*b b is a unit
199 // }
200 }

◆ nr2mGetUnit()

static number nr2mGetUnit ( number  k,
const  coeffs 
)
static

Definition at line 385 of file rmodulo2m.cc.

386 {
387  if (k == NULL) return (number)1;
388  unsigned long erg = (unsigned long)k;
389  while (erg % 2 == 0) erg = erg / 2;
390  return (number)erg;
391 }

◆ nr2mGreater()

static BOOLEAN nr2mGreater ( number  a,
number  b,
const coeffs  r 
)
static

Definition at line 469 of file rmodulo2m.cc.

470 {
471  return nr2mDivBy(a, b,r);
472 }

◆ nr2mGreaterZero()

static BOOLEAN nr2mGreaterZero ( number  k,
const coeffs  r 
)
static

Definition at line 134 of file rmodulo2m.cc.

135 {
136  if ((unsigned long)k == 0) return FALSE;
137  if ((unsigned long)k > ((r->mod2mMask >> 1) + 1)) return FALSE;
138  return TRUE;
139 }

◆ nr2mInit()

static number nr2mInit ( long  i,
const coeffs  r 
)
static

Definition at line 339 of file rmodulo2m.cc.

340 {
341  if (i == 0) return (number)(unsigned long)i;
342 
343  long ii = i;
344  unsigned long j = (unsigned long)1;
345  if (ii < 0) { j = r->mod2mMask; ii = -ii; }
346  unsigned long k = (unsigned long)ii;
347  k = k & r->mod2mMask;
348  /* now we have: i = j * k mod 2^m */
349  return (number)nr2mMult((number)j, (number)k, r);
350 }

◆ nr2mInitChar()

BOOLEAN nr2mInitChar ( coeffs  r,
void *  p 
)

Definition at line 782 of file rmodulo2m.cc.

783 {
784  assume( getCoeffType(r) == n_Z2m );
785  nr2mInitExp((int)(long)(p), r);
786 
787  r->is_field=FALSE;
788  r->is_domain=FALSE;
789  r->rep=n_rep_int;
790 
791  //r->cfKillChar = ndKillChar; /* dummy*/
792  r->nCoeffIsEqual = nr2mCoeffIsEqual;
793  r->cfCoeffString = nr2mCoeffString;
794 
795  r->modBase = (mpz_ptr) omAllocBin (gmp_nrz_bin);
796  mpz_init_set_si (r->modBase, 2L);
797  r->modNumber= (mpz_ptr) omAllocBin (gmp_nrz_bin);
798  mpz_init (r->modNumber);
799  mpz_pow_ui (r->modNumber, r->modBase, r->modExponent);
800 
801  /* next cast may yield an overflow as mod2mMask is an unsigned long */
802  r->ch = (int)r->mod2mMask + 1;
803 
804  r->cfInit = nr2mInit;
805  //r->cfCopy = ndCopy;
806  r->cfInt = nr2mInt;
807  r->cfAdd = nr2mAdd;
808  r->cfSub = nr2mSub;
809  r->cfMult = nr2mMult;
810  r->cfDiv = nr2mDiv;
811  r->cfAnn = nr2mAnn;
812  r->cfIntMod = nr2mMod;
813  r->cfExactDiv = nr2mDiv;
814  r->cfInpNeg = nr2mNeg;
815  r->cfInvers = nr2mInvers;
816  r->cfDivBy = nr2mDivBy;
817  r->cfDivComp = nr2mDivComp;
818  r->cfGreater = nr2mGreater;
819  r->cfEqual = nr2mEqual;
820  r->cfIsZero = nr2mIsZero;
821  r->cfIsOne = nr2mIsOne;
822  r->cfIsMOne = nr2mIsMOne;
823  r->cfGreaterZero = nr2mGreaterZero;
824  r->cfWriteLong = nr2mWrite;
825  r->cfRead = nr2mRead;
826  r->cfPower = nr2mPower;
827  r->cfSetMap = nr2mSetMap;
828 // r->cfNormalize = ndNormalize; // default
829  r->cfLcm = nr2mLcm;
830  r->cfGcd = nr2mGcd;
831  r->cfIsUnit = nr2mIsUnit;
832  r->cfGetUnit = nr2mGetUnit;
833  r->cfExtGcd = nr2mExtGcd;
834  r->cfCoeffWrite = nr2mCoeffWrite;
835  r->cfCoeffName = nr2mCoeffName;
836  r->cfQuot1 = nr2mQuot1;
837 #ifdef LDEBUG
838  r->cfDBTest = nr2mDBTest;
839 #endif
840  r->has_simple_Alloc=TRUE;
841  return FALSE;
842 }

◆ nr2mInitExp()

static void nr2mInitExp ( int  m,
coeffs  r 
)
static

Definition at line 731 of file rmodulo2m.cc.

732 {
733  nr2mSetExp(m, r);
734  if (m < 2)
735  WarnS("nr2mInitExp unexpectedly called with m = 1 (we continue with Z/2^2");
736 }

◆ nr2mInt()

static long nr2mInt ( number &  n,
const coeffs  r 
)
static

Definition at line 356 of file rmodulo2m.cc.

357 {
358  unsigned long nn = (unsigned long)n;
359  unsigned long l = r->mod2mMask >> 1; l++; /* now: l = 2^(m-1) */
360  if ((unsigned long)nn > l)
361  return (long)((unsigned long)nn - r->mod2mMask - 1);
362  else
363  return (long)((unsigned long)nn);
364 }

◆ nr2mInvers()

static number nr2mInvers ( number  c,
const coeffs  r 
)
static

Definition at line 281 of file rmodulo2m.cc.

282 {
283  if ((unsigned long)c % 2 == 0)
284  {
285  WerrorS("division by zero divisor");
286  return (number)0;
287  }
288  return nr2mInversM(c, r);
289 }

◆ nr2mInversM()

static number nr2mInversM ( number  c,
const coeffs  r 
)
inlinestatic

Definition at line 272 of file rmodulo2m.cc.

273 {
274  assume((unsigned long)c % 2 != 0);
275  // Table !!!
276  unsigned long inv;
277  inv = InvMod((unsigned long)c,r);
278  return (number)inv;
279 }

◆ nr2mIsMOne()

static BOOLEAN nr2mIsMOne ( number  a,
const coeffs  r 
)
static

Definition at line 403 of file rmodulo2m.cc.

404 {
405  return ((r->mod2mMask == (unsigned long)a) &&(1L!=(long)a))/*for char 2^1*/;
406 }

◆ nr2mIsOne()

static BOOLEAN nr2mIsOne ( number  a,
const  coeffs 
)
static

Definition at line 398 of file rmodulo2m.cc.

399 {
400  return 1 == (unsigned long)a;
401 }

◆ nr2mIsUnit()

static BOOLEAN nr2mIsUnit ( number  a,
const  coeffs 
)
static

Definition at line 380 of file rmodulo2m.cc.

381 {
382  return ((unsigned long)a % 2 == 1);
383 }

◆ nr2mIsZero()

static BOOLEAN nr2mIsZero ( number  a,
const  coeffs 
)
static

Definition at line 393 of file rmodulo2m.cc.

394 {
395  return 0 == (unsigned long)a;
396 }

◆ nr2mLcm()

static number nr2mLcm ( number  a,
number  b,
const  coeffs 
)
static

Definition at line 159 of file rmodulo2m.cc.

160 {
161  unsigned long res = 0;
162  if ((unsigned long)a == 0) a = (number) 1;
163  if ((unsigned long)b == 0) b = (number) 1;
164  while ((unsigned long)a % 2 == 0)
165  {
166  a = (number)((unsigned long)a / 2);
167  if ((unsigned long)b % 2 == 0) b = (number)((unsigned long)b / 2);
168  res++;
169  }
170  while ((unsigned long)b % 2 == 0)
171  {
172  b = (number)((unsigned long)b / 2);
173  res++;
174  }
175  return (number)(1L << res); // (2**res)
176 }

◆ nr2mMapGMP()

static number nr2mMapGMP ( number  from,
const  coeffs,
const coeffs  dst 
)
static

Definition at line 630 of file rmodulo2m.cc.

631 {
632  mpz_ptr erg = (mpz_ptr)omAllocBin(gmp_nrz_bin);
633  mpz_init(erg);
634  mpz_ptr k = (mpz_ptr)omAlloc(sizeof(mpz_t));
635  mpz_init_set_ui(k, dst->mod2mMask);
636 
637  mpz_and(erg, (mpz_ptr)from, k);
638  number res = (number) mpz_get_ui(erg);
639 
640  mpz_clear(erg); omFree((ADDRESS)erg);
641  mpz_clear(k); omFree((ADDRESS)k);
642 
643  return (number)res;
644 }

◆ nr2mMapMachineInt()

static number nr2mMapMachineInt ( number  from,
const  coeffs,
const coeffs  dst 
)
static

Definition at line 607 of file rmodulo2m.cc.

608 {
609  unsigned long i = ((unsigned long)from) % (dst->mod2mMask + 1) ;
610  return (number)i;
611 }

◆ nr2mMapProject()

static number nr2mMapProject ( number  from,
const  coeffs,
const coeffs  dst 
)
static

Definition at line 613 of file rmodulo2m.cc.

614 {
615  unsigned long i = ((unsigned long)from) % (dst->mod2mMask + 1);
616  return (number)i;
617 }

◆ nr2mMapQ()

static number nr2mMapQ ( number  from,
const coeffs  src,
const coeffs  dst 
)
static

Definition at line 646 of file rmodulo2m.cc.

647 {
648  mpz_ptr gmp = (mpz_ptr)omAllocBin(gmp_nrz_bin);
649  mpz_init(gmp);
650  nlGMP(from, gmp, src); // FIXME? TODO? // extern void nlGMP(number &i, number n, const coeffs r); // to be replaced with n_MPZ(erg, from, src); // ?
651  number res=nr2mMapGMP((number)gmp,src,dst);
652  mpz_clear(gmp); omFree((ADDRESS)gmp);
653  return res;
654 }

◆ nr2mMapZ()

static number nr2mMapZ ( number  from,
const coeffs  src,
const coeffs  dst 
)
static

Definition at line 656 of file rmodulo2m.cc.

657 {
658  if (SR_HDL(from) & SR_INT)
659  {
660  long f_i=SR_TO_INT(from);
661  return nr2mInit(f_i,dst);
662  }
663  return nr2mMapGMP(from,src,dst);
664 }

◆ nr2mMapZp()

number nr2mMapZp ( number  from,
const  coeffs,
const coeffs  dst 
)

Definition at line 619 of file rmodulo2m.cc.

620 {
621  unsigned long j = (unsigned long)1;
622  long ii = (long)from;
623  if (ii < 0) { j = dst->mod2mMask; ii = -ii; }
624  unsigned long i = (unsigned long)ii;
625  i = i & dst->mod2mMask;
626  /* now we have: from = j * i mod 2^m */
627  return (number)nr2mMult((number)i, (number)j, dst);
628 }

◆ nr2mMod()

static number nr2mMod ( number  a,
number  b,
const coeffs  r 
)
static

Definition at line 501 of file rmodulo2m.cc.

502 {
503  /*
504  We need to return the number rr which is uniquely determined by the
505  following two properties:
506  (1) 0 <= rr < |b| (with respect to '<' and '<=' performed in Z x Z)
507  (2) There exists some k in the integers Z such that a = k * b + rr.
508  Consider g := gcd(2^m, |b|). Note that then |b|/g is a unit in Z/2^m.
509  Now, there are three cases:
510  (a) g = 1
511  Then |b| is a unit in Z/2^m, i.e. |b| (and also b) divides a.
512  Thus rr = 0.
513  (b) g <> 1 and g divides a
514  Then a = (a/g) * (|b|/g)^(-1) * b (up to sign), i.e. again rr = 0.
515  (c) g <> 1 and g does not divide a
516  Let's denote the division with remainder of a by g as follows:
517  a = s * g + t. Then t = a - s * g = a - s * (|b|/g)^(-1) * |b|
518  fulfills (1) and (2), i.e. rr := t is the correct result. Hence
519  in this third case, rr is the remainder of division of a by g in Z.
520  This algorithm is the same as for the case Z/n, except that we may
521  compute the gcd of |b| and 2^m "by hand": We just extract the highest
522  power of 2 (<= 2^m) that is contained in b.
523  */
524  assume((unsigned long) b != 0);
525  unsigned long g = 1;
526  unsigned long b_div = (unsigned long) b;
527 
528  /*
529  * b_div is unsigned, so that (b_div < 0) evaluates false at compile-time
530  *
531  if (b_div < 0) b_div = -b_div; // b_div now represents |b|, BUT b_div is unsigned!
532  */
533 
534  unsigned long rr = 0;
535  while ((g < r->mod2mMask ) && (b_div > 0) && (b_div % 2 == 0))
536  {
537  b_div = b_div >> 1;
538  g = g << 1;
539  } // g is now the gcd of 2^m and |b|
540 
541  if (g != 1) rr = (unsigned long)a % g;
542  return (number)rr;
543 }

◆ nr2mMult()

static number nr2mMult ( number  a,
number  b,
const coeffs  r 
)
static

Definition at line 144 of file rmodulo2m.cc.

145 {
146  number n;
147  if (((unsigned long)a == 0) || ((unsigned long)b == 0))
148  return (number)0;
149  else
150  n=nr2mMultM(a, b, r);
151  n_Test(n,r);
152  return n;
153 }

◆ nr2mMultM()

static number nr2mMultM ( number  a,
number  b,
const coeffs  r 
)
inlinestatic

Definition at line 40 of file rmodulo2m.cc.

41 {
42  return (number)
43  ((((unsigned long) a) * ((unsigned long) b)) & r->mod2mMask);
44 }

◆ nr2mNeg()

static number nr2mNeg ( number  c,
const coeffs  r 
)
static

Definition at line 599 of file rmodulo2m.cc.

600 {
601  if ((unsigned long)c == 0) return c;
602  number n=nr2mNegM(c, r);
603  n_Test(n,r);
604  return n;
605 }

◆ nr2mPower()

static void nr2mPower ( number  a,
int  i,
number *  result,
const coeffs  r 
)
static

Definition at line 319 of file rmodulo2m.cc.

320 {
321  if (i == 0)
322  {
323  *(unsigned long *)result = 1;
324  }
325  else if (i == 1)
326  {
327  *result = a;
328  }
329  else
330  {
331  nr2mPower(a, i-1, result, r);
332  *result = nr2mMultM(a, *result, r);
333  }
334 }

◆ nr2mQuot1()

static coeffs nr2mQuot1 ( number  c,
const coeffs  r 
)
static

Definition at line 95 of file rmodulo2m.cc.

96 {
97  coeffs rr;
98  long ch = r->cfInt(c, r);
99  mpz_t a,b;
100  mpz_init_set(a, r->modNumber);
101  mpz_init_set_ui(b, ch);
102  mpz_ptr gcd;
103  gcd = (mpz_ptr) omAlloc(sizeof(mpz_t));
104  mpz_init(gcd);
105  mpz_gcd(gcd, a,b);
106  if(mpz_cmp_ui(gcd, 1) == 0)
107  {
108  WerrorS("constant in q-ideal is coprime to modulus in ground ring");
109  WerrorS("Unable to create qring!");
110  return NULL;
111  }
112  if(mpz_cmp_ui(gcd, 2) == 0)
113  {
114  rr = nInitChar(n_Zp, (void*)2);
115  }
116  else
117  {
118  int kNew = 1;
119  mpz_t baseTokNew;
120  mpz_init(baseTokNew);
121  mpz_set(baseTokNew, r->modBase);
122  while(mpz_cmp(gcd, baseTokNew) > 0)
123  {
124  kNew++;
125  mpz_mul(baseTokNew, baseTokNew, r->modBase);
126  }
127  mpz_clear(baseTokNew);
128  rr = nInitChar(n_Z2m, (void*)(long)kNew);
129  }
130  return(rr);
131 }

◆ nr2mRead()

static const char* nr2mRead ( const char *  s,
number *  a,
const coeffs  r 
)
static

Definition at line 763 of file rmodulo2m.cc.

764 {
765  int z;
766  int n=1;
767 
768  s = nr2mEati(s, &z,r);
769  if ((*s) == '/')
770  {
771  s++;
772  s = nr2mEati(s, &n,r);
773  }
774  if (n == 1)
775  *a = (number)(long)z;
776  else
777  *a = nr2mDiv((number)(long)z,(number)(long)n,r);
778  return s;
779 }

◆ nr2mSetExp()

static void nr2mSetExp ( int  m,
coeffs  r 
)
static

Definition at line 713 of file rmodulo2m.cc.

714 {
715  if (m > 1)
716  {
717  /* we want mod2mMask to be the bit pattern
718  '111..1' consisting of m one's: */
719  r->modExponent= m;
720  r->mod2mMask = 1;
721  for (int i = 1; i < m; i++) r->mod2mMask = (r->mod2mMask << 1) + 1;
722  }
723  else
724  {
725  r->modExponent= 2;
726  /* code unexpectedly called with m = 1; we continue with m = 2: */
727  r->mod2mMask = 3; /* i.e., '11' in binary representation */
728  }
729 }

◆ nr2mSetMap()

static nMapFunc nr2mSetMap ( const coeffs  src,
const coeffs  dst 
)
static

Definition at line 666 of file rmodulo2m.cc.

667 {
668  if ((src->rep==n_rep_int) && nCoeff_is_Ring_2toM(src)
669  && (src->mod2mMask == dst->mod2mMask))
670  {
671  return ndCopyMap;
672  }
673  if ((src->rep==n_rep_int) && nCoeff_is_Ring_2toM(src)
674  && (src->mod2mMask < dst->mod2mMask))
675  { /* i.e. map an integer mod 2^s into Z mod 2^t, where t < s */
676  return nr2mMapMachineInt;
677  }
678  if ((src->rep==n_rep_int) && nCoeff_is_Ring_2toM(src)
679  && (src->mod2mMask > dst->mod2mMask))
680  { /* i.e. map an integer mod 2^s into Z mod 2^t, where t > s */
681  // to be done
682  return nr2mMapProject;
683  }
684  if ((src->rep==n_rep_gmp) && nCoeff_is_Z(src))
685  {
686  return nr2mMapGMP;
687  }
688  if ((src->rep==n_rep_gap_gmp) /*&& nCoeff_is_Z(src)*/)
689  {
690  return nr2mMapZ;
691  }
692  if ((src->rep==n_rep_gap_rat) && (nCoeff_is_Q(src)||nCoeff_is_Z(src)))
693  {
694  return nr2mMapQ;
695  }
696  if ((src->rep==n_rep_int) && nCoeff_is_Zp(src) && (src->ch == 2))
697  {
698  return nr2mMapZp;
699  }
700  if ((src->rep==n_rep_gmp) &&
701  (nCoeff_is_Ring_PtoM(src) || nCoeff_is_Zn(src)))
702  {
703  if (mpz_divisible_2exp_p(src->modNumber,dst->modExponent))
704  return nr2mMapGMP;
705  }
706  return NULL; // default
707 }

◆ nr2mSub()

static number nr2mSub ( number  a,
number  b,
const coeffs  r 
)
static

Definition at line 373 of file rmodulo2m.cc.

374 {
375  number n=nr2mSubM(a, b, r);
376  n_Test(n,r);
377  return n;
378 }

◆ nr2mSubM()

static number nr2mSubM ( number  a,
number  b,
const coeffs  r 
)
inlinestatic

Definition at line 52 of file rmodulo2m.cc.

53 {
54  return (number)((unsigned long)a < (unsigned long)b ?
55  r->mod2mMask+1 - (unsigned long)b + (unsigned long)a:
56  (unsigned long)a - (unsigned long)b);
57 }

◆ nr2mWrite()

static void nr2mWrite ( number  a,
const coeffs  r 
)
static

Definition at line 738 of file rmodulo2m.cc.

739 {
740  long i = nr2mInt(a, r);
741  StringAppend("%ld", i);
742 }

◆ specialXGCD()

static void specialXGCD ( unsigned long &  s,
unsigned long  a,
const coeffs  r 
)
static

Definition at line 206 of file rmodulo2m.cc.

207 {
208  mpz_ptr u = (mpz_ptr)omAlloc(sizeof(mpz_t));
209  mpz_init_set_ui(u, a);
210  mpz_ptr u0 = (mpz_ptr)omAlloc(sizeof(mpz_t));
211  mpz_init(u0);
212  mpz_ptr u1 = (mpz_ptr)omAlloc(sizeof(mpz_t));
213  mpz_init_set_ui(u1, 1);
214  mpz_ptr u2 = (mpz_ptr)omAlloc(sizeof(mpz_t));
215  mpz_init(u2);
216  mpz_ptr v = (mpz_ptr)omAlloc(sizeof(mpz_t));
217  mpz_init_set_ui(v, r->mod2mMask);
218  mpz_add_ui(v, v, 1); /* now: v = 2^m */
219  mpz_ptr v0 = (mpz_ptr)omAlloc(sizeof(mpz_t));
220  mpz_init(v0);
221  mpz_ptr v1 = (mpz_ptr)omAlloc(sizeof(mpz_t));
222  mpz_init(v1);
223  mpz_ptr v2 = (mpz_ptr)omAlloc(sizeof(mpz_t));
224  mpz_init_set_ui(v2, 1);
225  mpz_ptr q = (mpz_ptr)omAlloc(sizeof(mpz_t));
226  mpz_init(q);
227  mpz_ptr rr = (mpz_ptr)omAlloc(sizeof(mpz_t));
228  mpz_init(rr);
229 
230  while (mpz_sgn1(v) != 0) /* i.e., while v != 0 */
231  {
232  mpz_div(q, u, v);
233  mpz_mod(rr, u, v);
234  mpz_set(u, v);
235  mpz_set(v, rr);
236  mpz_set(u0, u2);
237  mpz_set(v0, v2);
238  mpz_mul(u2, u2, q); mpz_sub(u2, u1, u2); /* u2 = u1 - q * u2 */
239  mpz_mul(v2, v2, q); mpz_sub(v2, v1, v2); /* v2 = v1 - q * v2 */
240  mpz_set(u1, u0);
241  mpz_set(v1, v0);
242  }
243 
244  while (mpz_sgn1(u1) < 0) /* i.e., while u1 < 0 */
245  {
246  /* we add 2^m = (2^m - 1) + 1 to u1: */
247  mpz_add_ui(u1, u1, r->mod2mMask);
248  mpz_add_ui(u1, u1, 1);
249  }
250  s = mpz_get_ui(u1); /* now: 0 <= s <= 2^m - 1 */
251 
252  mpz_clear(u); omFree((ADDRESS)u);
253  mpz_clear(u0); omFree((ADDRESS)u0);
254  mpz_clear(u1); omFree((ADDRESS)u1);
255  mpz_clear(u2); omFree((ADDRESS)u2);
256  mpz_clear(v); omFree((ADDRESS)v);
257  mpz_clear(v0); omFree((ADDRESS)v0);
258  mpz_clear(v1); omFree((ADDRESS)v1);
259  mpz_clear(v2); omFree((ADDRESS)v2);
260  mpz_clear(q); omFree((ADDRESS)q);
261  mpz_clear(rr); omFree((ADDRESS)rr);
262 }

Variable Documentation

◆ gmp_nrz_bin

omBin gmp_nrz_bin

Definition at line 31 of file rintegers.cc.

getCoeffType
static FORCE_INLINE n_coeffType getCoeffType(const coeffs r)
Returns the type of coeffs domain.
Definition: coeffs.h:421
n_rep_gap_rat
@ n_rep_gap_rat
(number), see longrat.h
Definition: coeffs.h:111
FALSE
#define FALSE
Definition: auxiliary.h:94
n_rep_gmp
@ n_rep_gmp
(mpz_ptr), see rmodulon,h
Definition: coeffs.h:115
nr2mMapProject
static number nr2mMapProject(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:613
nr2mGreaterZero
static BOOLEAN nr2mGreaterZero(number k, const coeffs r)
Definition: rmodulo2m.cc:134
nCoeff_is_Zp
static FORCE_INLINE BOOLEAN nCoeff_is_Zp(const coeffs r)
Definition: coeffs.h:822
j
int j
Definition: facHensel.cc:105
f
FILE * f
Definition: checklibs.c:9
omFree
#define omFree(addr)
Definition: omAllocDecl.h:261
nr2mNeg
static number nr2mNeg(number c, const coeffs r)
Definition: rmodulo2m.cc:599
k
int k
Definition: cfEzgcd.cc:92
nCoeff_is_Z
static FORCE_INLINE BOOLEAN nCoeff_is_Z(const coeffs r)
Definition: coeffs.h:838
nCoeff_is_Ring_2toM
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_2toM(const coeffs r)
Definition: coeffs.h:746
result
return result
Definition: facAbsBiFact.cc:76
nr2mLcm
static number nr2mLcm(number a, number b, const coeffs)
Definition: rmodulo2m.cc:159
nr2mSub
static number nr2mSub(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:373
ADDRESS
void * ADDRESS
Definition: auxiliary.h:133
mpz_sgn1
#define mpz_sgn1(A)
Definition: si_gmp.h:13
LDEBUG
#define LDEBUG
Definition: mod2.h:308
nr2mAdd
static number nr2mAdd(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:366
nr2mDivComp
static int nr2mDivComp(number as, number bs, const coeffs)
Definition: rmodulo2m.cc:474
n_Z2m
@ n_Z2m
only used if HAVE_RINGS is defined
Definition: coeffs.h:47
cf
CanonicalForm cf
Definition: cfModGcd.cc:4024
nr2mMult
static number nr2mMult(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:144
nr2mInvers
static number nr2mInvers(number c, const coeffs r)
Definition: rmodulo2m.cc:281
g
g
Definition: cfModGcd.cc:4031
omStrDup
#define omStrDup(s)
Definition: omAllocDecl.h:263
ndCopyMap
number ndCopyMap(number a, const coeffs aRing, const coeffs r)
Definition: numbers.cc:252
nr2mIsUnit
static BOOLEAN nr2mIsUnit(number a, const coeffs)
Definition: rmodulo2m.cc:380
nInitChar
coeffs nInitChar(n_coeffType t, void *parameter)
one-time initialisations for new coeffs in case of an error return NULL
Definition: numbers.cc:350
omAllocBin
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
nr2mInitExp
static void nr2mInitExp(int m, coeffs r)
Definition: rmodulo2m.cc:731
nr2mAnn
static number nr2mAnn(number b, const coeffs r)
Definition: rmodulo2m.cc:578
n_rep_int
@ n_rep_int
(int), see modulop.h
Definition: coeffs.h:110
nr2mRead
static const char * nr2mRead(const char *s, number *a, const coeffs r)
Definition: rmodulo2m.cc:763
nr2mGcd
static number nr2mGcd(number a, number b, const coeffs)
Definition: rmodulo2m.cc:182
b
CanonicalForm b
Definition: cfModGcd.cc:4044
nr2mInit
static number nr2mInit(long i, const coeffs r)
Definition: rmodulo2m.cc:339
nr2mCoeffWrite
static void nr2mCoeffWrite(const coeffs r, BOOLEAN)
Definition: rmodulo2m.cc:74
nr2mMapQ
static number nr2mMapQ(number from, const coeffs src, const coeffs dst)
Definition: rmodulo2m.cc:646
nCoeff_is_Q
static FORCE_INLINE BOOLEAN nCoeff_is_Q(const coeffs r)
Definition: coeffs.h:828
specialXGCD
static void specialXGCD(unsigned long &s, unsigned long a, const coeffs r)
Definition: rmodulo2m.cc:206
nr2mIsMOne
static BOOLEAN nr2mIsMOne(number a, const coeffs r)
Definition: rmodulo2m.cc:403
nr2mSubM
static number nr2mSubM(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:52
TRUE
#define TRUE
Definition: auxiliary.h:98
i
int i
Definition: cfEzgcd.cc:125
nr2mNegM
#define nr2mNegM(A, r)
Definition: rmodulo2m.cc:59
res
CanonicalForm res
Definition: facAbsFact.cc:64
nr2mSetExp
static void nr2mSetExp(int m, coeffs r)
Definition: rmodulo2m.cc:713
nr2mCoeffName
static char * nr2mCoeffName(const coeffs cf)
Definition: rmodulo2m.cc:64
InvMod
static unsigned long InvMod(unsigned long a, const coeffs r)
Definition: rmodulo2m.cc:264
PrintS
void PrintS(const char *s)
Definition: reporter.cc:284
nr2mDiv
static number nr2mDiv(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:413
nr2mEati
static const char * nr2mEati(const char *s, int *i, const coeffs r)
Definition: rmodulo2m.cc:744
coeffs
omAlloc
#define omAlloc(size)
Definition: omAllocDecl.h:210
nr2mMod
static number nr2mMod(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:501
nCoeff_is_Ring_PtoM
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_PtoM(const coeffs r)
Definition: coeffs.h:749
nr2mMultM
static number nr2mMultM(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:40
nr2mGetUnit
static number nr2mGetUnit(number k, const coeffs)
Definition: rmodulo2m.cc:385
nr2mMapZp
number nr2mMapZp(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:619
nr2mSetMap
static nMapFunc nr2mSetMap(const coeffs src, const coeffs dst)
Definition: rmodulo2m.cc:666
gmp_nrz_bin
omBin gmp_nrz_bin
Definition: rintegers.cc:31
nr2mMapZ
static number nr2mMapZ(number from, const coeffs src, const coeffs dst)
Definition: rmodulo2m.cc:656
SR_INT
#define SR_INT
Definition: longrat.h:66
SR_TO_INT
#define SR_TO_INT(SR)
Definition: longrat.h:68
nr2mMapMachineInt
static number nr2mMapMachineInt(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:607
nr2mQuot1
static coeffs nr2mQuot1(number c, const coeffs r)
Definition: rmodulo2m.cc:95
nr2mInt
static long nr2mInt(number &n, const coeffs r)
Definition: rmodulo2m.cc:356
n_Zp
@ n_Zp
\F{p < 2^31}
Definition: coeffs.h:30
nr2mExtGcd
static number nr2mExtGcd(number a, number b, number *s, number *t, const coeffs r)
Definition: rmodulo2m.cc:295
Print
#define Print
Definition: emacs.cc:80
nr2mMapGMP
static number nr2mMapGMP(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:630
nr2mIsZero
static BOOLEAN nr2mIsZero(number a, const coeffs)
Definition: rmodulo2m.cc:393
WerrorS
void WerrorS(const char *s)
Definition: feFopen.cc:24
nr2mInversM
static number nr2mInversM(number c, const coeffs r)
Definition: rmodulo2m.cc:272
SR_HDL
#define SR_HDL(A)
Definition: tgb.cc:35
m
int m
Definition: cfEzgcd.cc:121
WarnS
#define WarnS
Definition: emacs.cc:78
assume
#define assume(x)
Definition: mod2.h:390
NULL
#define NULL
Definition: omList.c:10
l
int l
Definition: cfEzgcd.cc:93
nCoeff_is_Zn
static FORCE_INLINE BOOLEAN nCoeff_is_Zn(const coeffs r)
Definition: coeffs.h:848
nr2mCoeffIsEqual
static BOOLEAN nr2mCoeffIsEqual(const coeffs r, n_coeffType n, void *p)
Definition: rmodulo2m.cc:79
nr2mWrite
static void nr2mWrite(number a, const coeffs r)
Definition: rmodulo2m.cc:738
nr2mCoeffString
static char * nr2mCoeffString(const coeffs r)
Definition: rmodulo2m.cc:90
nr2mGreater
static BOOLEAN nr2mGreater(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:469
gcd
int gcd(int a, int b)
Definition: walkSupport.cc:836
StringAppend
#define StringAppend
Definition: emacs.cc:79
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
nr2mIsOne
static BOOLEAN nr2mIsOne(number a, const coeffs)
Definition: rmodulo2m.cc:398
nr2mDivBy
static BOOLEAN nr2mDivBy(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:441
p
int p
Definition: cfModGcd.cc:4019
s
const CanonicalForm int s
Definition: facAbsFact.cc:55
nr2mDBTest
BOOLEAN nr2mDBTest(number a, const char *f, const int l, const coeffs r)
Definition: rmodulo2m.cc:28
nr2mEqual
static BOOLEAN nr2mEqual(number a, number b, const coeffs)
Definition: rmodulo2m.cc:408
n_Test
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:738
nr2mAddM
static number nr2mAddM(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:46
nr2mPower
static void nr2mPower(number a, int i, number *result, const coeffs r)
Definition: rmodulo2m.cc:319
MAX_INT_VAL
const int MAX_INT_VAL
Definition: mylimits.h:12
nlGMP
void nlGMP(number &i, mpz_t n, const coeffs r)
Definition: longrat.cc:1478
n_rep_gap_gmp
@ n_rep_gap_gmp
(), see rinteger.h, new impl.
Definition: coeffs.h:112