My Project
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 BOOLEAN nr2mCoeffIsEqual (const coeffs r, n_coeffType n, void *p)
 
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 58 of file rmodulo2m.cc.

◆ nr2mNegM

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

Definition at line 57 of file rmodulo2m.cc.

Function Documentation

◆ InvMod()

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

Definition at line 252 of file rmodulo2m.cc.

253 {
254  assume((unsigned long)a % 2 != 0);
255  unsigned long s;
256  specialXGCD(s, a, r);
257  return s;
258 }
const CanonicalForm int s
Definition: facAbsFact.cc:51
#define assume(x)
Definition: mod2.h:387
static void specialXGCD(unsigned long &s, unsigned long a, const coeffs r)
Definition: rmodulo2m.cc:194

◆ nr2mAdd()

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

Definition at line 354 of file rmodulo2m.cc.

355 {
356  number n=nr2mAddM(a, b, r);
357  n_Test(n,r);
358  return n;
359 }
CanonicalForm b
Definition: cfModGcd.cc:4105
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:736
static number nr2mAddM(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:44

◆ nr2mAddM()

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

Definition at line 44 of file rmodulo2m.cc.

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

◆ nr2mAnn()

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

Definition at line 571 of file rmodulo2m.cc.

572 {
573  if ((unsigned long)b == 0)
574  return NULL;
575  if ((unsigned long)b == 1)
576  return NULL;
577  unsigned long c = r->mod2mMask + 1;
578  if (c != 0) /* i.e., if no overflow */
579  return (number)(c / (unsigned long)b);
580  else
581  {
582  /* overflow: c = 2^32 resp. 2^64, depending on platform */
583  mpz_ptr cc = (mpz_ptr)omAlloc(sizeof(mpz_t));
584  mpz_init_set_ui(cc, r->mod2mMask); mpz_add_ui(cc, cc, 1);
585  mpz_div_ui(cc, cc, (unsigned long)(unsigned long)b);
586  unsigned long s = mpz_get_ui(cc);
587  mpz_clear(cc); omFree((ADDRESS)cc);
588  return (number)(unsigned long)s;
589  }
590 }
void * ADDRESS
Definition: auxiliary.h:119
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omFree(addr)
Definition: omAllocDecl.h:261
#define NULL
Definition: omList.c:12

◆ nr2mCoeffIsEqual()

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

Definition at line 72 of file rmodulo2m.cc.

73 {
74  if (n==n_Z2m)
75  {
76  int m=(int)(long)(p);
77  unsigned long mm=r->mod2mMask;
78  if (((mm+1)>>m)==1L) return TRUE;
79  }
80  return FALSE;
81 }
#define TRUE
Definition: auxiliary.h:100
#define FALSE
Definition: auxiliary.h:96
int m
Definition: cfEzgcd.cc:128
int p
Definition: cfModGcd.cc:4080
@ n_Z2m
only used if HAVE_RINGS is defined
Definition: coeffs.h:47

◆ nr2mCoeffName()

static char* nr2mCoeffName ( const coeffs  cf)
static

Definition at line 62 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;
70 }
CanonicalForm cf
Definition: cfModGcd.cc:4085
#define STATIC_VAR
Definition: globaldefs.h:7

◆ nr2mDBTest()

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

Definition at line 26 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;
34 }
int l
Definition: cfEzgcd.cc:100
FILE * f
Definition: checklibs.c:9
#define Print
Definition: emacs.cc:80

◆ nr2mDiv()

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

Definition at line 401 of file rmodulo2m.cc.

402 {
403  if ((unsigned long)a == 0) return (number)0;
404  else if ((unsigned long)b % 2 == 0)
405  {
406  if ((unsigned long)b != 0)
407  {
408  while (((unsigned long)b % 2 == 0) && ((unsigned long)a % 2 == 0))
409  {
410  a = (number)((unsigned long)a / 2);
411  b = (number)((unsigned long)b / 2);
412  }
413  }
414  if ((long)b==0L)
415  {
416  WerrorS(nDivBy0);
417  return (number)0L;
418  }
419  else if ((unsigned long)b % 2 == 0)
420  {
421  WerrorS("Division not possible, even by cancelling zero divisors.");
422  WerrorS("Result is integer division without remainder.");
423  return (number) ((unsigned long) a / (unsigned long) b);
424  }
425  }
426  number n=(number)nr2mMult(a, nr2mInversM(b,r),r);
427  n_Test(n,r);
428  return n;
429 }
void WerrorS(const char *s)
Definition: feFopen.cc:24
const char *const nDivBy0
Definition: numbers.h:87
static number nr2mInversM(number c, const coeffs r)
Definition: rmodulo2m.cc:260
static number nr2mMult(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:132

◆ nr2mDivBy()

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

Definition at line 434 of file rmodulo2m.cc.

435 {
436  if (a == NULL)
437  {
438  unsigned long c = r->mod2mMask + 1;
439  if (c != 0) /* i.e., if no overflow */
440  return (c % (unsigned long)b) == 0;
441  else
442  {
443  /* overflow: we need to check whether b
444  is zero or a power of 2: */
445  c = (unsigned long)b;
446  while (c != 0)
447  {
448  if ((c % 2) != 0) return FALSE;
449  c = c >> 1;
450  }
451  return TRUE;
452  }
453  }
454  else
455  {
456  number n = nr2mGcd(a, b, r);
457  n = nr2mDiv(b, n, r);
458  return nr2mIsUnit(n, r);
459  }
460 }
static number nr2mGcd(number a, number b, const coeffs)
Definition: rmodulo2m.cc:170
static BOOLEAN nr2mIsUnit(number a, const coeffs)
Definition: rmodulo2m.cc:368
static number nr2mDiv(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:401

◆ nr2mDivComp()

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

Definition at line 467 of file rmodulo2m.cc.

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

◆ nr2mEati()

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

Definition at line 731 of file rmodulo2m.cc.

732 {
733 
734  if (((*s) >= '0') && ((*s) <= '9'))
735  {
736  (*i) = 0;
737  do
738  {
739  (*i) *= 10;
740  (*i) += *s++ - '0';
741  if ((*i) >= (MAX_INT_VAL / 10)) (*i) = (*i) & r->mod2mMask;
742  }
743  while (((*s) >= '0') && ((*s) <= '9'));
744  (*i) = (*i) & r->mod2mMask;
745  }
746  else (*i) = 1;
747  return s;
748 }
int i
Definition: cfEzgcd.cc:132
const int MAX_INT_VAL
Definition: mylimits.h:12

◆ nr2mEqual()

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

Definition at line 396 of file rmodulo2m.cc.

397 {
398  return (a == b);
399 }

◆ nr2mExtGcd()

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

Definition at line 283 of file rmodulo2m.cc.

284 {
285  unsigned long res = 0;
286  if ((unsigned long)a == 0 && (unsigned long)b == 0) return (number)1;
287  while ((unsigned long)a % 2 == 0 && (unsigned long)b % 2 == 0)
288  {
289  a = (number)((unsigned long)a / 2);
290  b = (number)((unsigned long)b / 2);
291  res++;
292  }
293  if ((unsigned long)b % 2 == 0)
294  {
295  *t = NULL;
296  *s = nr2mInvers(a,r);
297  return (number)((1L << res)); // * (unsigned long) a); // (2**res)*a a is a unit
298  }
299  else
300  {
301  *s = NULL;
302  *t = nr2mInvers(b,r);
303  return (number)((1L << res)); // * (unsigned long) b); // (2**res)*b b is a unit
304  }
305 }
CanonicalForm res
Definition: facAbsFact.cc:60
static number nr2mInvers(number c, const coeffs r)
Definition: rmodulo2m.cc:269

◆ nr2mGcd()

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

Definition at line 170 of file rmodulo2m.cc.

171 {
172  unsigned long res = 0;
173  if ((unsigned long)a == 0 && (unsigned long)b == 0) return (number)1;
174  while ((unsigned long)a % 2 == 0 && (unsigned long)b % 2 == 0)
175  {
176  a = (number)((unsigned long)a / 2);
177  b = (number)((unsigned long)b / 2);
178  res++;
179  }
180 // if ((unsigned long)b % 2 == 0)
181 // {
182 // return (number)((1L << res)); // * (unsigned long) a); // (2**res)*a a is a unit
183 // }
184 // else
185 // {
186  return (number)((1L << res)); // * (unsigned long) b); // (2**res)*b b is a unit
187 // }
188 }

◆ nr2mGetUnit()

static number nr2mGetUnit ( number  k,
const  coeffs 
)
static

Definition at line 373 of file rmodulo2m.cc.

374 {
375  if (k == NULL) return (number)1;
376  unsigned long erg = (unsigned long)k;
377  while (erg % 2 == 0) erg = erg / 2;
378  return (number)erg;
379 }
int k
Definition: cfEzgcd.cc:99

◆ nr2mGreater()

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

Definition at line 462 of file rmodulo2m.cc.

463 {
464  return nr2mDivBy(a, b,r);
465 }
static BOOLEAN nr2mDivBy(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:434

◆ nr2mGreaterZero()

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

Definition at line 122 of file rmodulo2m.cc.

123 {
124  if ((unsigned long)k == 0) return FALSE;
125  if ((unsigned long)k > ((r->mod2mMask >> 1) + 1)) return FALSE;
126  return TRUE;
127 }

◆ nr2mInit()

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

Definition at line 327 of file rmodulo2m.cc.

328 {
329  if (i == 0) return (number)(unsigned long)i;
330 
331  long ii = i;
332  unsigned long j = (unsigned long)1;
333  if (ii < 0) { j = r->mod2mMask; ii = -ii; }
334  unsigned long k = (unsigned long)ii;
335  k = k & r->mod2mMask;
336  /* now we have: i = j * k mod 2^m */
337  return (number)nr2mMult((number)j, (number)k, r);
338 }
int j
Definition: facHensel.cc:110

◆ nr2mInitChar()

BOOLEAN nr2mInitChar ( coeffs  r,
void *  p 
)

Definition at line 769 of file rmodulo2m.cc.

770 {
771  assume( getCoeffType(r) == n_Z2m );
772  nr2mInitExp((int)(long)(p), r);
773 
774  r->is_field=FALSE;
775  r->is_domain=FALSE;
776  r->rep=n_rep_int;
777 
778  //r->cfKillChar = ndKillChar; /* dummy*/
779  r->nCoeffIsEqual = nr2mCoeffIsEqual;
780 
781  r->modBase = (mpz_ptr) omAllocBin (gmp_nrz_bin);
782  mpz_init_set_si (r->modBase, 2L);
783  r->modNumber= (mpz_ptr) omAllocBin (gmp_nrz_bin);
784  mpz_init (r->modNumber);
785  mpz_pow_ui (r->modNumber, r->modBase, r->modExponent);
786 
787  /* next cast may yield an overflow as mod2mMask is an unsigned long */
788  r->ch = (int)r->mod2mMask + 1;
789 
790  r->cfInit = nr2mInit;
791  //r->cfCopy = ndCopy;
792  r->cfInt = nr2mInt;
793  r->cfAdd = nr2mAdd;
794  r->cfSub = nr2mSub;
795  r->cfMult = nr2mMult;
796  r->cfDiv = nr2mDiv;
797  r->cfAnn = nr2mAnn;
798  r->cfIntMod = nr2mMod;
799  r->cfExactDiv = nr2mDiv;
800  r->cfInpNeg = nr2mNeg;
801  r->cfInvers = nr2mInvers;
802  r->cfDivBy = nr2mDivBy;
803  r->cfDivComp = nr2mDivComp;
804  r->cfGreater = nr2mGreater;
805  r->cfEqual = nr2mEqual;
806  r->cfIsZero = nr2mIsZero;
807  r->cfIsOne = nr2mIsOne;
808  r->cfIsMOne = nr2mIsMOne;
809  r->cfGreaterZero = nr2mGreaterZero;
810  r->cfWriteLong = nr2mWrite;
811  r->cfRead = nr2mRead;
812  r->cfPower = nr2mPower;
813  r->cfSetMap = nr2mSetMap;
814 // r->cfNormalize = ndNormalize; // default
815  r->cfLcm = nr2mLcm;
816  r->cfGcd = nr2mGcd;
817  r->cfIsUnit = nr2mIsUnit;
818  r->cfGetUnit = nr2mGetUnit;
819  r->cfExtGcd = nr2mExtGcd;
820  r->cfCoeffName = nr2mCoeffName;
821  r->cfQuot1 = nr2mQuot1;
822 #ifdef LDEBUG
823  r->cfDBTest = nr2mDBTest;
824 #endif
825  r->has_simple_Alloc=TRUE;
826  return FALSE;
827 }
static FORCE_INLINE n_coeffType getCoeffType(const coeffs r)
Returns the type of coeffs domain.
Definition: coeffs.h:422
@ n_rep_int
(int), see modulop.h
Definition: coeffs.h:111
#define LDEBUG
Definition: mod2.h:305
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
static nMapFunc nr2mSetMap(const coeffs src, const coeffs dst)
Definition: rmodulo2m.cc:658
static void nr2mWrite(number a, const coeffs r)
Definition: rmodulo2m.cc:725
static number nr2mSub(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:361
static number nr2mLcm(number a, number b, const coeffs)
Definition: rmodulo2m.cc:147
static BOOLEAN nr2mIsOne(number a, const coeffs)
Definition: rmodulo2m.cc:386
static number nr2mAnn(number b, const coeffs r)
Definition: rmodulo2m.cc:571
static number nr2mInit(long i, const coeffs r)
Definition: rmodulo2m.cc:327
static char * nr2mCoeffName(const coeffs cf)
Definition: rmodulo2m.cc:62
static number nr2mExtGcd(number a, number b, number *s, number *t, const coeffs r)
Definition: rmodulo2m.cc:283
static number nr2mGetUnit(number k, const coeffs)
Definition: rmodulo2m.cc:373
static void nr2mInitExp(int m, coeffs r)
Definition: rmodulo2m.cc:718
static void nr2mPower(number a, int i, number *result, const coeffs r)
Definition: rmodulo2m.cc:307
static int nr2mDivComp(number as, number bs, const coeffs)
Definition: rmodulo2m.cc:467
BOOLEAN nr2mDBTest(number a, const char *f, const int l, const coeffs r)
Definition: rmodulo2m.cc:26
static long nr2mInt(number &n, const coeffs r)
Definition: rmodulo2m.cc:344
static BOOLEAN nr2mGreaterZero(number k, const coeffs r)
Definition: rmodulo2m.cc:122
static number nr2mNeg(number c, const coeffs r)
Definition: rmodulo2m.cc:592
EXTERN_VAR omBin gmp_nrz_bin
Definition: rmodulo2m.cc:60
static number nr2mMod(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:494
static BOOLEAN nr2mCoeffIsEqual(const coeffs r, n_coeffType n, void *p)
Definition: rmodulo2m.cc:72
static number nr2mAdd(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:354
static BOOLEAN nr2mEqual(number a, number b, const coeffs)
Definition: rmodulo2m.cc:396
static BOOLEAN nr2mGreater(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:462
static BOOLEAN nr2mIsZero(number a, const coeffs)
Definition: rmodulo2m.cc:381
static const char * nr2mRead(const char *s, number *a, const coeffs r)
Definition: rmodulo2m.cc:750
static BOOLEAN nr2mIsMOne(number a, const coeffs r)
Definition: rmodulo2m.cc:391
static coeffs nr2mQuot1(number c, const coeffs r)
Definition: rmodulo2m.cc:83

◆ nr2mInitExp()

static void nr2mInitExp ( int  m,
coeffs  r 
)
static

Definition at line 718 of file rmodulo2m.cc.

719 {
720  nr2mSetExp(m, r);
721  if (m < 2)
722  WarnS("nr2mInitExp unexpectedly called with m = 1 (we continue with Z/2^2");
723 }
#define WarnS
Definition: emacs.cc:78
static void nr2mSetExp(int m, coeffs r)
Definition: rmodulo2m.cc:700

◆ nr2mInt()

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

Definition at line 344 of file rmodulo2m.cc.

345 {
346  unsigned long nn = (unsigned long)n;
347  unsigned long l = r->mod2mMask >> 1; l++; /* now: l = 2^(m-1) */
348  if ((unsigned long)nn > l)
349  return (long)((unsigned long)nn - r->mod2mMask - 1);
350  else
351  return (long)((unsigned long)nn);
352 }

◆ nr2mInvers()

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

Definition at line 269 of file rmodulo2m.cc.

270 {
271  if ((unsigned long)c % 2 == 0)
272  {
273  WerrorS("division by zero divisor");
274  return (number)0;
275  }
276  return nr2mInversM(c, r);
277 }

◆ nr2mInversM()

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

Definition at line 260 of file rmodulo2m.cc.

261 {
262  assume((unsigned long)c % 2 != 0);
263  // Table !!!
264  unsigned long inv;
265  inv = InvMod((unsigned long)c,r);
266  return (number)inv;
267 }
static unsigned long InvMod(unsigned long a, const coeffs r)
Definition: rmodulo2m.cc:252

◆ nr2mIsMOne()

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

Definition at line 391 of file rmodulo2m.cc.

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

◆ nr2mIsOne()

static BOOLEAN nr2mIsOne ( number  a,
const  coeffs 
)
static

Definition at line 386 of file rmodulo2m.cc.

387 {
388  return 1 == (unsigned long)a;
389 }

◆ nr2mIsUnit()

static BOOLEAN nr2mIsUnit ( number  a,
const  coeffs 
)
static

Definition at line 368 of file rmodulo2m.cc.

369 {
370  return ((unsigned long)a % 2 == 1);
371 }

◆ nr2mIsZero()

static BOOLEAN nr2mIsZero ( number  a,
const  coeffs 
)
static

Definition at line 381 of file rmodulo2m.cc.

382 {
383  return 0 == (unsigned long)a;
384 }

◆ nr2mLcm()

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

Definition at line 147 of file rmodulo2m.cc.

148 {
149  unsigned long res = 0;
150  if ((unsigned long)a == 0) a = (number) 1;
151  if ((unsigned long)b == 0) b = (number) 1;
152  while ((unsigned long)a % 2 == 0)
153  {
154  a = (number)((unsigned long)a / 2);
155  if ((unsigned long)b % 2 == 0) b = (number)((unsigned long)b / 2);
156  res++;
157  }
158  while ((unsigned long)b % 2 == 0)
159  {
160  b = (number)((unsigned long)b / 2);
161  res++;
162  }
163  return (number)(1L << res); // (2**res)
164 }

◆ nr2mMapGMP()

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

Definition at line 623 of file rmodulo2m.cc.

624 {
625  mpz_ptr erg = (mpz_ptr)omAllocBin(gmp_nrz_bin);
626  mpz_init(erg);
627  mpz_ptr k = (mpz_ptr)omAlloc(sizeof(mpz_t));
628  mpz_init_set_ui(k, dst->mod2mMask);
629 
630  mpz_and(erg, (mpz_ptr)from, k);
631  number res = (number) mpz_get_ui(erg);
632 
633  mpz_clear(erg); omFree((ADDRESS)erg);
634  mpz_clear(k); omFree((ADDRESS)k);
635 
636  return (number)res;
637 }

◆ nr2mMapMachineInt()

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

Definition at line 600 of file rmodulo2m.cc.

601 {
602  unsigned long i = ((unsigned long)from) % (dst->mod2mMask + 1) ;
603  return (number)i;
604 }

◆ nr2mMapProject()

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

Definition at line 606 of file rmodulo2m.cc.

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

◆ nr2mMapQ()

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

Definition at line 639 of file rmodulo2m.cc.

640 {
641  mpz_ptr gmp = (mpz_ptr)omAllocBin(gmp_nrz_bin);
642  nlMPZ(gmp, from, src);
643  number res=nr2mMapGMP((number)gmp,src,dst);
644  mpz_clear(gmp); omFree((ADDRESS)gmp);
645  return res;
646 }
void nlMPZ(mpz_t m, number &n, const coeffs r)
Definition: longrat.cc:2779
static number nr2mMapGMP(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:623

◆ nr2mMapZ()

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

Definition at line 648 of file rmodulo2m.cc.

649 {
650  if (SR_HDL(from) & SR_INT)
651  {
652  long f_i=SR_TO_INT(from);
653  return nr2mInit(f_i,dst);
654  }
655  return nr2mMapGMP(from,src,dst);
656 }
#define SR_INT
Definition: longrat.h:67
#define SR_TO_INT(SR)
Definition: longrat.h:69
#define SR_HDL(A)
Definition: tgb.cc:35

◆ nr2mMapZp()

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

Definition at line 612 of file rmodulo2m.cc.

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

◆ nr2mMod()

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

Definition at line 494 of file rmodulo2m.cc.

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

◆ nr2mMult()

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

Definition at line 132 of file rmodulo2m.cc.

133 {
134  number n;
135  if (((unsigned long)a == 0) || ((unsigned long)b == 0))
136  return (number)0;
137  else
138  n=nr2mMultM(a, b, r);
139  n_Test(n,r);
140  return n;
141 }
static number nr2mMultM(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:38

◆ nr2mMultM()

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

Definition at line 38 of file rmodulo2m.cc.

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

◆ nr2mNeg()

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

Definition at line 592 of file rmodulo2m.cc.

593 {
594  if ((unsigned long)c == 0) return c;
595  number n=nr2mNegM(c, r);
596  n_Test(n,r);
597  return n;
598 }
#define nr2mNegM(A, r)
Definition: rmodulo2m.cc:57

◆ nr2mPower()

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

Definition at line 307 of file rmodulo2m.cc.

308 {
309  if (i == 0)
310  {
311  *(unsigned long *)result = 1;
312  }
313  else if (i == 1)
314  {
315  *result = a;
316  }
317  else
318  {
319  nr2mPower(a, i-1, result, r);
320  *result = nr2mMultM(a, *result, r);
321  }
322 }
return result
Definition: facAbsBiFact.cc:75

◆ nr2mQuot1()

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

Definition at line 83 of file rmodulo2m.cc.

84 {
85  coeffs rr;
86  long ch = r->cfInt(c, r);
87  mpz_t a,b;
88  mpz_init_set(a, r->modNumber);
89  mpz_init_set_ui(b, ch);
90  mpz_ptr gcd;
91  gcd = (mpz_ptr) omAlloc(sizeof(mpz_t));
92  mpz_init(gcd);
93  mpz_gcd(gcd, a,b);
94  if(mpz_cmp_ui(gcd, 1) == 0)
95  {
96  WerrorS("constant in q-ideal is coprime to modulus in ground ring");
97  WerrorS("Unable to create qring!");
98  return NULL;
99  }
100  if(mpz_cmp_ui(gcd, 2) == 0)
101  {
102  rr = nInitChar(n_Zp, (void*)2);
103  }
104  else
105  {
106  int kNew = 1;
107  mpz_t baseTokNew;
108  mpz_init(baseTokNew);
109  mpz_set(baseTokNew, r->modBase);
110  while(mpz_cmp(gcd, baseTokNew) > 0)
111  {
112  kNew++;
113  mpz_mul(baseTokNew, baseTokNew, r->modBase);
114  }
115  mpz_clear(baseTokNew);
116  rr = nInitChar(n_Z2m, (void*)(long)kNew);
117  }
118  return(rr);
119 }
@ n_Zp
\F{p < 2^31}
Definition: coeffs.h:30
coeffs nInitChar(n_coeffType t, void *parameter)
one-time initialisations for new coeffs in case of an error return NULL
Definition: numbers.cc:353
The main handler for Singular numbers which are suitable for Singular polynomials.
int gcd(int a, int b)
Definition: walkSupport.cc:836

◆ nr2mRead()

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

Definition at line 750 of file rmodulo2m.cc.

751 {
752  int z;
753  int n=1;
754 
755  s = nr2mEati(s, &z,r);
756  if ((*s) == '/')
757  {
758  s++;
759  s = nr2mEati(s, &n,r);
760  }
761  if (n == 1)
762  *a = (number)(long)z;
763  else
764  *a = nr2mDiv((number)(long)z,(number)(long)n,r);
765  return s;
766 }
static const char * nr2mEati(const char *s, int *i, const coeffs r)
Definition: rmodulo2m.cc:731

◆ nr2mSetExp()

static void nr2mSetExp ( int  m,
coeffs  r 
)
static

Definition at line 700 of file rmodulo2m.cc.

701 {
702  if (m > 1)
703  {
704  /* we want mod2mMask to be the bit pattern
705  '111..1' consisting of m one's: */
706  r->modExponent= m;
707  r->mod2mMask = 1;
708  for (int i = 1; i < m; i++) r->mod2mMask = (r->mod2mMask << 1) + 1;
709  }
710  else
711  {
712  r->modExponent= 2;
713  /* code unexpectedly called with m = 1; we continue with m = 2: */
714  r->mod2mMask = 3; /* i.e., '11' in binary representation */
715  }
716 }

◆ nr2mSetMap()

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

Definition at line 658 of file rmodulo2m.cc.

659 {
660  if ((src->rep==n_rep_int) && nCoeff_is_Ring_2toM(src)
661  && (src->mod2mMask < dst->mod2mMask))
662  { /* i.e. map an integer mod 2^s into Z mod 2^t, where t < s */
663  return nr2mMapMachineInt;
664  }
665  if ((src->rep==n_rep_int) && nCoeff_is_Ring_2toM(src)
666  && (src->mod2mMask > dst->mod2mMask))
667  { /* i.e. map an integer mod 2^s into Z mod 2^t, where t > s */
668  // to be done
669  return nr2mMapProject;
670  }
671  if ((src->rep==n_rep_gmp) && nCoeff_is_Z(src))
672  {
673  return nr2mMapGMP;
674  }
675  if ((src->rep==n_rep_gap_gmp) /*&& nCoeff_is_Z(src)*/)
676  {
677  return nr2mMapZ;
678  }
679  if ((src->rep==n_rep_gap_rat) && (nCoeff_is_Q(src)||nCoeff_is_Z(src)))
680  {
681  return nr2mMapQ;
682  }
683  if ((src->rep==n_rep_int) && nCoeff_is_Zp(src) && (src->ch == 2))
684  {
685  return nr2mMapZp;
686  }
687  if ((src->rep==n_rep_gmp) &&
688  (nCoeff_is_Ring_PtoM(src) || nCoeff_is_Zn(src)))
689  {
690  if (mpz_divisible_2exp_p(src->modNumber,dst->modExponent))
691  return nr2mMapGMP;
692  }
693  return NULL; // default
694 }
static FORCE_INLINE BOOLEAN nCoeff_is_Z(const coeffs r)
Definition: coeffs.h:840
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_PtoM(const coeffs r)
Definition: coeffs.h:751
static FORCE_INLINE BOOLEAN nCoeff_is_Q(const coeffs r)
Definition: coeffs.h:830
static FORCE_INLINE BOOLEAN nCoeff_is_Zn(const coeffs r)
Definition: coeffs.h:850
static FORCE_INLINE BOOLEAN nCoeff_is_Zp(const coeffs r)
Definition: coeffs.h:824
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_2toM(const coeffs r)
Definition: coeffs.h:748
@ n_rep_gap_rat
(number), see longrat.h
Definition: coeffs.h:112
@ n_rep_gap_gmp
(), see rinteger.h, new impl.
Definition: coeffs.h:113
@ n_rep_gmp
(mpz_ptr), see rmodulon,h
Definition: coeffs.h:116
static number nr2mMapProject(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:606
static number nr2mMapQ(number from, const coeffs src, const coeffs dst)
Definition: rmodulo2m.cc:639
number nr2mMapZp(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:612
static number nr2mMapMachineInt(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:600
static number nr2mMapZ(number from, const coeffs src, const coeffs dst)
Definition: rmodulo2m.cc:648

◆ nr2mSub()

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

Definition at line 361 of file rmodulo2m.cc.

362 {
363  number n=nr2mSubM(a, b, r);
364  n_Test(n,r);
365  return n;
366 }
static number nr2mSubM(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:50

◆ nr2mSubM()

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

Definition at line 50 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);
55 }

◆ nr2mWrite()

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

Definition at line 725 of file rmodulo2m.cc.

726 {
727  long i = nr2mInt(a, r);
728  StringAppend("%ld", i);
729 }
#define StringAppend
Definition: emacs.cc:79

◆ specialXGCD()

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

Definition at line 194 of file rmodulo2m.cc.

195 {
196  mpz_ptr u = (mpz_ptr)omAlloc(sizeof(mpz_t));
197  mpz_init_set_ui(u, a);
198  mpz_ptr u0 = (mpz_ptr)omAlloc(sizeof(mpz_t));
199  mpz_init(u0);
200  mpz_ptr u1 = (mpz_ptr)omAlloc(sizeof(mpz_t));
201  mpz_init_set_ui(u1, 1);
202  mpz_ptr u2 = (mpz_ptr)omAlloc(sizeof(mpz_t));
203  mpz_init(u2);
204  mpz_ptr v = (mpz_ptr)omAlloc(sizeof(mpz_t));
205  mpz_init_set_ui(v, r->mod2mMask);
206  mpz_add_ui(v, v, 1); /* now: v = 2^m */
207  mpz_ptr v0 = (mpz_ptr)omAlloc(sizeof(mpz_t));
208  mpz_init(v0);
209  mpz_ptr v1 = (mpz_ptr)omAlloc(sizeof(mpz_t));
210  mpz_init(v1);
211  mpz_ptr v2 = (mpz_ptr)omAlloc(sizeof(mpz_t));
212  mpz_init_set_ui(v2, 1);
213  mpz_ptr q = (mpz_ptr)omAlloc(sizeof(mpz_t));
214  mpz_init(q);
215  mpz_ptr rr = (mpz_ptr)omAlloc(sizeof(mpz_t));
216  mpz_init(rr);
217 
218  while (mpz_sgn1(v) != 0) /* i.e., while v != 0 */
219  {
220  mpz_div(q, u, v);
221  mpz_mod(rr, u, v);
222  mpz_set(u, v);
223  mpz_set(v, rr);
224  mpz_set(u0, u2);
225  mpz_set(v0, v2);
226  mpz_mul(u2, u2, q); mpz_sub(u2, u1, u2); /* u2 = u1 - q * u2 */
227  mpz_mul(v2, v2, q); mpz_sub(v2, v1, v2); /* v2 = v1 - q * v2 */
228  mpz_set(u1, u0);
229  mpz_set(v1, v0);
230  }
231 
232  while (mpz_sgn1(u1) < 0) /* i.e., while u1 < 0 */
233  {
234  /* we add 2^m = (2^m - 1) + 1 to u1: */
235  mpz_add_ui(u1, u1, r->mod2mMask);
236  mpz_add_ui(u1, u1, 1);
237  }
238  s = mpz_get_ui(u1); /* now: 0 <= s <= 2^m - 1 */
239 
240  mpz_clear(u); omFree((ADDRESS)u);
241  mpz_clear(u0); omFree((ADDRESS)u0);
242  mpz_clear(u1); omFree((ADDRESS)u1);
243  mpz_clear(u2); omFree((ADDRESS)u2);
244  mpz_clear(v); omFree((ADDRESS)v);
245  mpz_clear(v0); omFree((ADDRESS)v0);
246  mpz_clear(v1); omFree((ADDRESS)v1);
247  mpz_clear(v2); omFree((ADDRESS)v2);
248  mpz_clear(q); omFree((ADDRESS)q);
249  mpz_clear(rr); omFree((ADDRESS)rr);
250 }
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
#define mpz_sgn1(A)
Definition: si_gmp.h:13

Variable Documentation

◆ gmp_nrz_bin

EXTERN_VAR omBin gmp_nrz_bin

Definition at line 60 of file rmodulo2m.cc.