My Project  debian-1:4.1.2-p1+ds-2
Macros | Functions | Variables
rmodulo2m.cc File Reference
#include "misc/auxiliary.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

EXTERN_VAR omBin gmp_nrz_bin
 

Macro Definition Documentation

◆ nr2mEqualM

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

Definition at line 57 of file rmodulo2m.cc.

◆ nr2mNegM

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

Definition at line 56 of file rmodulo2m.cc.

Function Documentation

◆ InvMod()

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

Definition at line 261 of file rmodulo2m.cc.

263 {
264  assume((unsigned long)a % 2 != 0);
265  unsigned long s;
266  specialXGCD(s, a, r);
267  return s;

◆ nr2mAdd()

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

Definition at line 363 of file rmodulo2m.cc.

365 {
366  number n=nr2mAddM(a, b, r);
367  n_Test(n,r);
368  return n;

◆ nr2mAddM()

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

Definition at line 43 of file rmodulo2m.cc.

45 {
46  return (number)
47  ((((unsigned long) a) + ((unsigned long) b)) & r->mod2mMask);

◆ nr2mAnn()

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

Definition at line 575 of file rmodulo2m.cc.

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

◆ nr2mCoeffIsEqual()

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

Definition at line 76 of file rmodulo2m.cc.

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

◆ nr2mCoeffName()

static char* nr2mCoeffName ( const coeffs  cf)
static

Definition at line 61 of file rmodulo2m.cc.

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;

◆ nr2mCoeffString()

static char* nr2mCoeffString ( const coeffs  r)
static

Definition at line 87 of file rmodulo2m.cc.

89 {
90  return omStrDup(nr2mCoeffName(r));

◆ nr2mCoeffWrite()

static void nr2mCoeffWrite ( const coeffs  r,
BOOLEAN   
)
static

Definition at line 71 of file rmodulo2m.cc.

73 {

◆ nr2mDBTest()

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

Definition at line 25 of file rmodulo2m.cc.

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;

◆ nr2mDiv()

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

Definition at line 410 of file rmodulo2m.cc.

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

◆ nr2mDivBy()

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

Definition at line 438 of file rmodulo2m.cc.

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

◆ nr2mDivComp()

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

Definition at line 471 of file rmodulo2m.cc.

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

◆ nr2mEati()

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

Definition at line 741 of file rmodulo2m.cc.

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

◆ nr2mEqual()

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

Definition at line 405 of file rmodulo2m.cc.

407 {
408  return (a == b);

◆ nr2mExtGcd()

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

Definition at line 292 of file rmodulo2m.cc.

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

◆ nr2mGcd()

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

Definition at line 179 of file rmodulo2m.cc.

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

◆ nr2mGetUnit()

static number nr2mGetUnit ( number  k,
const  coeffs 
)
static

Definition at line 382 of file rmodulo2m.cc.

384 {
385  if (k == NULL) return (number)1;
386  unsigned long erg = (unsigned long)k;
387  while (erg % 2 == 0) erg = erg / 2;
388  return (number)erg;

◆ nr2mGreater()

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

Definition at line 466 of file rmodulo2m.cc.

468 {
469  return nr2mDivBy(a, b,r);

◆ nr2mGreaterZero()

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

Definition at line 131 of file rmodulo2m.cc.

133 {
134  if ((unsigned long)k == 0) return FALSE;
135  if ((unsigned long)k > ((r->mod2mMask >> 1) + 1)) return FALSE;
136  return TRUE;

◆ nr2mInit()

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

Definition at line 336 of file rmodulo2m.cc.

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

◆ nr2mInitChar()

BOOLEAN nr2mInitChar ( coeffs  r,
void *  p 
)

Definition at line 779 of file rmodulo2m.cc.

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

◆ nr2mInitExp()

static void nr2mInitExp ( int  m,
coeffs  r 
)
static

Definition at line 728 of file rmodulo2m.cc.

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

◆ nr2mInt()

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

Definition at line 353 of file rmodulo2m.cc.

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

◆ nr2mInvers()

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

Definition at line 278 of file rmodulo2m.cc.

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

◆ nr2mInversM()

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

Definition at line 269 of file rmodulo2m.cc.

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

◆ nr2mIsMOne()

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

Definition at line 400 of file rmodulo2m.cc.

402 {
403  return ((r->mod2mMask == (unsigned long)a) &&(1L!=(long)a))/*for char 2^1*/;

◆ nr2mIsOne()

static BOOLEAN nr2mIsOne ( number  a,
const  coeffs 
)
static

Definition at line 395 of file rmodulo2m.cc.

397 {
398  return 1 == (unsigned long)a;

◆ nr2mIsUnit()

static BOOLEAN nr2mIsUnit ( number  a,
const  coeffs 
)
static

Definition at line 377 of file rmodulo2m.cc.

379 {
380  return ((unsigned long)a % 2 == 1);

◆ nr2mIsZero()

static BOOLEAN nr2mIsZero ( number  a,
const  coeffs 
)
static

Definition at line 390 of file rmodulo2m.cc.

392 {
393  return 0 == (unsigned long)a;

◆ nr2mLcm()

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

Definition at line 156 of file rmodulo2m.cc.

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

◆ nr2mMapGMP()

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

Definition at line 627 of file rmodulo2m.cc.

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

◆ nr2mMapMachineInt()

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

Definition at line 604 of file rmodulo2m.cc.

606 {
607  unsigned long i = ((unsigned long)from) % (dst->mod2mMask + 1) ;
608  return (number)i;

◆ nr2mMapProject()

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

Definition at line 610 of file rmodulo2m.cc.

612 {
613  unsigned long i = ((unsigned long)from) % (dst->mod2mMask + 1);
614  return (number)i;

◆ nr2mMapQ()

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

Definition at line 643 of file rmodulo2m.cc.

645 {
646  mpz_ptr gmp = (mpz_ptr)omAllocBin(gmp_nrz_bin);
647  mpz_init(gmp);
648  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); // ?
649  number res=nr2mMapGMP((number)gmp,src,dst);
650  mpz_clear(gmp); omFree((ADDRESS)gmp);
651  return res;

◆ nr2mMapZ()

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

Definition at line 653 of file rmodulo2m.cc.

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

◆ nr2mMapZp()

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

Definition at line 616 of file rmodulo2m.cc.

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

◆ nr2mMod()

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

Definition at line 498 of file rmodulo2m.cc.

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

◆ nr2mMult()

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

Definition at line 141 of file rmodulo2m.cc.

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

◆ nr2mMultM()

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

Definition at line 37 of file rmodulo2m.cc.

39 {
40  return (number)
41  ((((unsigned long) a) * ((unsigned long) b)) & r->mod2mMask);

◆ nr2mNeg()

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

Definition at line 596 of file rmodulo2m.cc.

598 {
599  if ((unsigned long)c == 0) return c;
600  number n=nr2mNegM(c, r);
601  n_Test(n,r);
602  return n;

◆ nr2mPower()

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

Definition at line 316 of file rmodulo2m.cc.

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

◆ nr2mQuot1()

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

Definition at line 92 of file rmodulo2m.cc.

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

◆ nr2mRead()

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

Definition at line 760 of file rmodulo2m.cc.

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

◆ nr2mSetExp()

static void nr2mSetExp ( int  m,
coeffs  r 
)
static

Definition at line 710 of file rmodulo2m.cc.

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

◆ nr2mSetMap()

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

Definition at line 663 of file rmodulo2m.cc.

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

◆ nr2mSub()

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

Definition at line 370 of file rmodulo2m.cc.

372 {
373  number n=nr2mSubM(a, b, r);
374  n_Test(n,r);
375  return n;

◆ nr2mSubM()

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

Definition at line 49 of file rmodulo2m.cc.

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);

◆ nr2mWrite()

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

Definition at line 735 of file rmodulo2m.cc.

737 {
738  long i = nr2mInt(a, r);
739  StringAppend("%ld", i);

◆ specialXGCD()

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

Definition at line 203 of file rmodulo2m.cc.

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

Variable Documentation

◆ gmp_nrz_bin

EXTERN_VAR omBin gmp_nrz_bin

Definition at line 59 of file rmodulo2m.cc.

getCoeffType
static FORCE_INLINE n_coeffType getCoeffType(const coeffs r)
Returns the type of coeffs domain.
Definition: coeffs.h:420
n_rep_gap_rat
(number), see longrat.h
Definition: coeffs.h:110
FALSE
#define FALSE
Definition: auxiliary.h:96
n_rep_gmp
(mpz_ptr), see rmodulon,h
Definition: coeffs.h:114
nr2mMapProject
static number nr2mMapProject(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:610
nr2mGreaterZero
static BOOLEAN nr2mGreaterZero(number k, const coeffs r)
Definition: rmodulo2m.cc:131
nCoeff_is_Zp
static FORCE_INLINE BOOLEAN nCoeff_is_Zp(const coeffs r)
Definition: coeffs.h:821
j
int j
Definition: facHensel.cc:105
f
FILE * f
Definition: checklibs.c:9
omFree
#define omFree(addr)
Definition: omAllocDecl.h:259
nr2mNeg
static number nr2mNeg(number c, const coeffs r)
Definition: rmodulo2m.cc:596
k
int k
Definition: cfEzgcd.cc:92
nCoeff_is_Z
static FORCE_INLINE BOOLEAN nCoeff_is_Z(const coeffs r)
Definition: coeffs.h:837
nCoeff_is_Ring_2toM
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_2toM(const coeffs r)
Definition: coeffs.h:745
result
return result
Definition: facAbsBiFact.cc:76
nr2mLcm
static number nr2mLcm(number a, number b, const coeffs)
Definition: rmodulo2m.cc:156
nr2mSub
static number nr2mSub(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:370
ADDRESS
void * ADDRESS
Definition: auxiliary.h:135
mpz_sgn1
#define mpz_sgn1(A)
Definition: si_gmp.h:13
LDEBUG
#define LDEBUG
Definition: mod2.h:303
gmp_nrz_bin
EXTERN_VAR omBin gmp_nrz_bin
Definition: rmodulo2m.cc:59
nr2mAdd
static number nr2mAdd(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:363
nr2mDivComp
static int nr2mDivComp(number as, number bs, const coeffs)
Definition: rmodulo2m.cc:471
n_Z2m
only used if HAVE_RINGS is defined
Definition: coeffs.h:46
cf
CanonicalForm cf
Definition: cfModGcd.cc:4024
nr2mMult
static number nr2mMult(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:141
nr2mInvers
static number nr2mInvers(number c, const coeffs r)
Definition: rmodulo2m.cc:278
STATIC_VAR
#define STATIC_VAR
Definition: globaldefs.h:7
g
g
Definition: cfModGcd.cc:4031
omStrDup
#define omStrDup(s)
Definition: omAllocDecl.h:261
ndCopyMap
number ndCopyMap(number a, const coeffs aRing, const coeffs r)
Definition: numbers.cc:251
nr2mIsUnit
static BOOLEAN nr2mIsUnit(number a, const coeffs)
Definition: rmodulo2m.cc:377
nInitChar
coeffs nInitChar(n_coeffType t, void *parameter)
one-time initialisations for new coeffs in case of an error return NULL
Definition: numbers.cc:349
omAllocBin
#define omAllocBin(bin)
Definition: omAllocDecl.h:203
nr2mInitExp
static void nr2mInitExp(int m, coeffs r)
Definition: rmodulo2m.cc:728
nr2mAnn
static number nr2mAnn(number b, const coeffs r)
Definition: rmodulo2m.cc:575
n_rep_int
(int), see modulop.h
Definition: coeffs.h:109
nr2mRead
static const char * nr2mRead(const char *s, number *a, const coeffs r)
Definition: rmodulo2m.cc:760
nr2mGcd
static number nr2mGcd(number a, number b, const coeffs)
Definition: rmodulo2m.cc:179
b
CanonicalForm b
Definition: cfModGcd.cc:4044
nr2mInit
static number nr2mInit(long i, const coeffs r)
Definition: rmodulo2m.cc:336
nr2mCoeffWrite
static void nr2mCoeffWrite(const coeffs r, BOOLEAN)
Definition: rmodulo2m.cc:71
nr2mMapQ
static number nr2mMapQ(number from, const coeffs src, const coeffs dst)
Definition: rmodulo2m.cc:643
nCoeff_is_Q
static FORCE_INLINE BOOLEAN nCoeff_is_Q(const coeffs r)
Definition: coeffs.h:827
specialXGCD
static void specialXGCD(unsigned long &s, unsigned long a, const coeffs r)
Definition: rmodulo2m.cc:203
nr2mIsMOne
static BOOLEAN nr2mIsMOne(number a, const coeffs r)
Definition: rmodulo2m.cc:400
nr2mSubM
static number nr2mSubM(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:49
TRUE
#define TRUE
Definition: auxiliary.h:100
i
int i
Definition: cfEzgcd.cc:125
nr2mNegM
#define nr2mNegM(A, r)
Definition: rmodulo2m.cc:56
res
CanonicalForm res
Definition: facAbsFact.cc:64
nr2mSetExp
static void nr2mSetExp(int m, coeffs r)
Definition: rmodulo2m.cc:710
nr2mCoeffName
static char * nr2mCoeffName(const coeffs cf)
Definition: rmodulo2m.cc:61
InvMod
static unsigned long InvMod(unsigned long a, const coeffs r)
Definition: rmodulo2m.cc:261
PrintS
void PrintS(const char *s)
Definition: reporter.cc:283
nr2mDiv
static number nr2mDiv(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:410
nr2mEati
static const char * nr2mEati(const char *s, int *i, const coeffs r)
Definition: rmodulo2m.cc:741
coeffs
omAlloc
#define omAlloc(size)
Definition: omAllocDecl.h:208
nr2mMod
static number nr2mMod(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:498
nCoeff_is_Ring_PtoM
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_PtoM(const coeffs r)
Definition: coeffs.h:748
nr2mMultM
static number nr2mMultM(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:37
nr2mGetUnit
static number nr2mGetUnit(number k, const coeffs)
Definition: rmodulo2m.cc:382
nr2mMapZp
number nr2mMapZp(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:616
nr2mSetMap
static nMapFunc nr2mSetMap(const coeffs src, const coeffs dst)
Definition: rmodulo2m.cc:663
nr2mMapZ
static number nr2mMapZ(number from, const coeffs src, const coeffs dst)
Definition: rmodulo2m.cc:653
SR_INT
#define SR_INT
Definition: longrat.h:65
SR_TO_INT
#define SR_TO_INT(SR)
Definition: longrat.h:67
nr2mMapMachineInt
static number nr2mMapMachineInt(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:604
nr2mQuot1
static coeffs nr2mQuot1(number c, const coeffs r)
Definition: rmodulo2m.cc:92
nr2mInt
static long nr2mInt(number &n, const coeffs r)
Definition: rmodulo2m.cc:353
n_Zp
\F{p < 2^31}
Definition: coeffs.h:29
nr2mExtGcd
static number nr2mExtGcd(number a, number b, number *s, number *t, const coeffs r)
Definition: rmodulo2m.cc:292
Print
#define Print
Definition: emacs.cc:79
nr2mMapGMP
static number nr2mMapGMP(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:627
nr2mIsZero
static BOOLEAN nr2mIsZero(number a, const coeffs)
Definition: rmodulo2m.cc:390
WerrorS
void WerrorS(const char *s)
Definition: feFopen.cc:24
nr2mInversM
static number nr2mInversM(number c, const coeffs r)
Definition: rmodulo2m.cc:269
SR_HDL
#define SR_HDL(A)
Definition: tgb.cc:35
m
int m
Definition: cfEzgcd.cc:121
WarnS
#define WarnS
Definition: emacs.cc:77
assume
#define assume(x)
Definition: mod2.h:384
NULL
#define NULL
Definition: omList.c:11
l
int l
Definition: cfEzgcd.cc:93
nCoeff_is_Zn
static FORCE_INLINE BOOLEAN nCoeff_is_Zn(const coeffs r)
Definition: coeffs.h:847
nr2mCoeffIsEqual
static BOOLEAN nr2mCoeffIsEqual(const coeffs r, n_coeffType n, void *p)
Definition: rmodulo2m.cc:76
nr2mWrite
static void nr2mWrite(number a, const coeffs r)
Definition: rmodulo2m.cc:735
nr2mCoeffString
static char * nr2mCoeffString(const coeffs r)
Definition: rmodulo2m.cc:87
nr2mGreater
static BOOLEAN nr2mGreater(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:466
gcd
int gcd(int a, int b)
Definition: walkSupport.cc:836
StringAppend
#define StringAppend
Definition: emacs.cc:78
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
nr2mIsOne
static BOOLEAN nr2mIsOne(number a, const coeffs)
Definition: rmodulo2m.cc:395
nr2mDivBy
static BOOLEAN nr2mDivBy(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:438
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:25
nr2mEqual
static BOOLEAN nr2mEqual(number a, number b, const coeffs)
Definition: rmodulo2m.cc:405
n_Test
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:737
nr2mAddM
static number nr2mAddM(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:43
nr2mPower
static void nr2mPower(number a, int i, number *result, const coeffs r)
Definition: rmodulo2m.cc:316
MAX_INT_VAL
const int MAX_INT_VAL
Definition: mylimits.h:11
nlGMP
void nlGMP(number &i, mpz_t n, const coeffs r)
Definition: longrat.cc:1475
n_rep_gap_gmp
(), see rinteger.h, new impl.
Definition: coeffs.h:111