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 59 of file rmodulo2m.cc.

◆ nr2mNegM

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

Definition at line 58 of file rmodulo2m.cc.

Function Documentation

◆ InvMod()

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

Definition at line 253 of file rmodulo2m.cc.

254 {
255  assume((unsigned long)a % 2 != 0);
256  unsigned long s;
257  specialXGCD(s, a, r);
258  return s;
259 }
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:195

◆ nr2mAdd()

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

Definition at line 355 of file rmodulo2m.cc.

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

◆ nr2mAddM()

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

Definition at line 45 of file rmodulo2m.cc.

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

◆ nr2mAnn()

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

Definition at line 572 of file rmodulo2m.cc.

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

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

◆ nr2mCoeffName()

static char* nr2mCoeffName ( const coeffs  cf)
static

Definition at line 63 of file rmodulo2m.cc.

64 {
65  STATIC_VAR char n2mCoeffName_buf[30];
66  if (cf->modExponent>32) /* for 32/64bit arch.*/
67  snprintf(n2mCoeffName_buf,21,"ZZ/(bigint(2)^%lu)",cf->modExponent);
68  else
69  snprintf(n2mCoeffName_buf,21,"ZZ/(2^%lu)",cf->modExponent);
70  return n2mCoeffName_buf;
71 }
CanonicalForm cf
Definition: cfModGcd.cc:4083
#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  && (r->mod2mMask!= ~0UL))
30  {
31  Print("wrong mod 2^n number %ld (m:%ld) at %s,%d\n",(long)a,(long)r->mod2mMask,f,l);
32  return FALSE;
33  }
34  return TRUE;
35 }
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 402 of file rmodulo2m.cc.

403 {
404  if ((unsigned long)a == 0) return (number)0;
405  else if ((unsigned long)b % 2 == 0)
406  {
407  if ((unsigned long)b != 0)
408  {
409  while (((unsigned long)b % 2 == 0) && ((unsigned long)a % 2 == 0))
410  {
411  a = (number)((unsigned long)a / 2);
412  b = (number)((unsigned long)b / 2);
413  }
414  }
415  if ((long)b==0L)
416  {
417  WerrorS(nDivBy0);
418  return (number)0L;
419  }
420  else if ((unsigned long)b % 2 == 0)
421  {
422  WerrorS("Division not possible, even by cancelling zero divisors.");
423  WerrorS("Result is integer division without remainder.");
424  return (number) ((unsigned long) a / (unsigned long) b);
425  }
426  }
427  number n=(number)nr2mMult(a, nr2mInversM(b,r),r);
428  n_Test(n,r);
429  return n;
430 }
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:261
static number nr2mMult(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:133

◆ nr2mDivBy()

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

Definition at line 435 of file rmodulo2m.cc.

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

◆ nr2mDivComp()

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

Definition at line 468 of file rmodulo2m.cc.

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

◆ nr2mEati()

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

Definition at line 732 of file rmodulo2m.cc.

733 {
734 
735  if (((*s) >= '0') && ((*s) <= '9'))
736  {
737  (*i) = 0;
738  do
739  {
740  (*i) *= 10;
741  (*i) += *s++ - '0';
742  if ((*i) >= (MAX_INT_VAL / 10)) (*i) = (*i) & r->mod2mMask;
743  }
744  while (((*s) >= '0') && ((*s) <= '9'));
745  (*i) = (*i) & r->mod2mMask;
746  }
747  else (*i) = 1;
748  return s;
749 }
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 397 of file rmodulo2m.cc.

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

◆ nr2mExtGcd()

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

Definition at line 284 of file rmodulo2m.cc.

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

◆ nr2mGcd()

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

Definition at line 171 of file rmodulo2m.cc.

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

◆ nr2mGetUnit()

static number nr2mGetUnit ( number  k,
const  coeffs 
)
static

Definition at line 374 of file rmodulo2m.cc.

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

◆ nr2mGreater()

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

Definition at line 463 of file rmodulo2m.cc.

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

◆ nr2mGreaterZero()

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

Definition at line 123 of file rmodulo2m.cc.

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

◆ nr2mInit()

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

Definition at line 328 of file rmodulo2m.cc.

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

◆ nr2mInitChar()

BOOLEAN nr2mInitChar ( coeffs  r,
void *  p 
)

Definition at line 770 of file rmodulo2m.cc.

771 {
772  assume( getCoeffType(r) == n_Z2m );
773  nr2mInitExp((int)(long)(p), r);
774 
775  r->is_field=FALSE;
776  r->is_domain=FALSE;
777  r->rep=n_rep_int;
778 
779  //r->cfKillChar = ndKillChar; /* dummy*/
780  r->nCoeffIsEqual = nr2mCoeffIsEqual;
781 
782  r->modBase = (mpz_ptr) omAllocBin (gmp_nrz_bin);
783  mpz_init_set_si (r->modBase, 2L);
784  r->modNumber= (mpz_ptr) omAllocBin (gmp_nrz_bin);
785  mpz_init (r->modNumber);
786  mpz_pow_ui (r->modNumber, r->modBase, r->modExponent);
787 
788  /* next cast may yield an overflow as mod2mMask is an unsigned long */
789  r->ch = (int)r->mod2mMask + 1;
790 
791  r->cfInit = nr2mInit;
792  //r->cfCopy = ndCopy;
793  r->cfInt = nr2mInt;
794  r->cfAdd = nr2mAdd;
795  r->cfSub = nr2mSub;
796  r->cfMult = nr2mMult;
797  r->cfDiv = nr2mDiv;
798  r->cfAnn = nr2mAnn;
799  r->cfIntMod = nr2mMod;
800  r->cfExactDiv = nr2mDiv;
801  r->cfInpNeg = nr2mNeg;
802  r->cfInvers = nr2mInvers;
803  r->cfDivBy = nr2mDivBy;
804  r->cfDivComp = nr2mDivComp;
805  r->cfGreater = nr2mGreater;
806  r->cfEqual = nr2mEqual;
807  r->cfIsZero = nr2mIsZero;
808  r->cfIsOne = nr2mIsOne;
809  r->cfIsMOne = nr2mIsMOne;
810  r->cfGreaterZero = nr2mGreaterZero;
811  r->cfWriteLong = nr2mWrite;
812  r->cfRead = nr2mRead;
813  r->cfPower = nr2mPower;
814  r->cfSetMap = nr2mSetMap;
815 // r->cfNormalize = ndNormalize; // default
816  r->cfLcm = nr2mLcm;
817  r->cfGcd = nr2mGcd;
818  r->cfIsUnit = nr2mIsUnit;
819  r->cfGetUnit = nr2mGetUnit;
820  r->cfExtGcd = nr2mExtGcd;
821  r->cfCoeffName = nr2mCoeffName;
822  r->cfQuot1 = nr2mQuot1;
823 #ifdef LDEBUG
824  r->cfDBTest = nr2mDBTest;
825 #endif
826  r->has_simple_Alloc=TRUE;
827  return FALSE;
828 }
static FORCE_INLINE n_coeffType getCoeffType(const coeffs r)
Returns the type of coeffs domain.
Definition: coeffs.h:421
@ n_rep_int
(int), see modulop.h
Definition: coeffs.h:110
#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:659
static void nr2mWrite(number a, const coeffs r)
Definition: rmodulo2m.cc:726
static number nr2mSub(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:362
static number nr2mLcm(number a, number b, const coeffs)
Definition: rmodulo2m.cc:148
static BOOLEAN nr2mIsOne(number a, const coeffs)
Definition: rmodulo2m.cc:387
static number nr2mAnn(number b, const coeffs r)
Definition: rmodulo2m.cc:572
static number nr2mInit(long i, const coeffs r)
Definition: rmodulo2m.cc:328
static char * nr2mCoeffName(const coeffs cf)
Definition: rmodulo2m.cc:63
static number nr2mExtGcd(number a, number b, number *s, number *t, const coeffs r)
Definition: rmodulo2m.cc:284
static number nr2mGetUnit(number k, const coeffs)
Definition: rmodulo2m.cc:374
static void nr2mInitExp(int m, coeffs r)
Definition: rmodulo2m.cc:719
static void nr2mPower(number a, int i, number *result, const coeffs r)
Definition: rmodulo2m.cc:308
static int nr2mDivComp(number as, number bs, const coeffs)
Definition: rmodulo2m.cc:468
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:345
static BOOLEAN nr2mGreaterZero(number k, const coeffs r)
Definition: rmodulo2m.cc:123
static number nr2mNeg(number c, const coeffs r)
Definition: rmodulo2m.cc:593
EXTERN_VAR omBin gmp_nrz_bin
Definition: rmodulo2m.cc:61
static number nr2mMod(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:495
static BOOLEAN nr2mCoeffIsEqual(const coeffs r, n_coeffType n, void *p)
Definition: rmodulo2m.cc:73
static number nr2mAdd(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:355
static BOOLEAN nr2mEqual(number a, number b, const coeffs)
Definition: rmodulo2m.cc:397
static BOOLEAN nr2mGreater(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:463
static BOOLEAN nr2mIsZero(number a, const coeffs)
Definition: rmodulo2m.cc:382
static const char * nr2mRead(const char *s, number *a, const coeffs r)
Definition: rmodulo2m.cc:751
static BOOLEAN nr2mIsMOne(number a, const coeffs r)
Definition: rmodulo2m.cc:392
static coeffs nr2mQuot1(number c, const coeffs r)
Definition: rmodulo2m.cc:84

◆ nr2mInitExp()

static void nr2mInitExp ( int  m,
coeffs  r 
)
static

Definition at line 719 of file rmodulo2m.cc.

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

◆ nr2mInt()

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

Definition at line 345 of file rmodulo2m.cc.

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

◆ nr2mInvers()

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

Definition at line 270 of file rmodulo2m.cc.

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

◆ nr2mInversM()

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

Definition at line 261 of file rmodulo2m.cc.

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

◆ nr2mIsMOne()

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

Definition at line 392 of file rmodulo2m.cc.

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

◆ nr2mIsOne()

static BOOLEAN nr2mIsOne ( number  a,
const  coeffs 
)
static

Definition at line 387 of file rmodulo2m.cc.

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

◆ nr2mIsUnit()

static BOOLEAN nr2mIsUnit ( number  a,
const  coeffs 
)
static

Definition at line 369 of file rmodulo2m.cc.

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

◆ nr2mIsZero()

static BOOLEAN nr2mIsZero ( number  a,
const  coeffs 
)
static

Definition at line 382 of file rmodulo2m.cc.

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

◆ nr2mLcm()

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

Definition at line 148 of file rmodulo2m.cc.

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

◆ nr2mMapGMP()

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

Definition at line 624 of file rmodulo2m.cc.

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

◆ nr2mMapMachineInt()

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

Definition at line 601 of file rmodulo2m.cc.

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

◆ nr2mMapProject()

static number nr2mMapProject ( 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 }

◆ nr2mMapQ()

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

Definition at line 640 of file rmodulo2m.cc.

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

◆ nr2mMapZ()

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

Definition at line 649 of file rmodulo2m.cc.

650 {
651  if (SR_HDL(from) & SR_INT)
652  {
653  long f_i=SR_TO_INT(from);
654  return nr2mInit(f_i,dst);
655  }
656  return nr2mMapGMP(from,src,dst);
657 }
#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 613 of file rmodulo2m.cc.

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

◆ nr2mMod()

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

Definition at line 495 of file rmodulo2m.cc.

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

◆ nr2mMult()

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

Definition at line 133 of file rmodulo2m.cc.

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

◆ nr2mMultM()

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

Definition at line 39 of file rmodulo2m.cc.

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

◆ nr2mNeg()

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

Definition at line 593 of file rmodulo2m.cc.

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

◆ nr2mPower()

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

Definition at line 308 of file rmodulo2m.cc.

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

◆ nr2mQuot1()

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

Definition at line 84 of file rmodulo2m.cc.

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

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

◆ nr2mSetExp()

static void nr2mSetExp ( int  m,
coeffs  r 
)
static

Definition at line 701 of file rmodulo2m.cc.

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

◆ nr2mSetMap()

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

Definition at line 659 of file rmodulo2m.cc.

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

◆ nr2mSub()

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

Definition at line 362 of file rmodulo2m.cc.

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

◆ nr2mSubM()

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

Definition at line 51 of file rmodulo2m.cc.

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

◆ nr2mWrite()

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

Definition at line 726 of file rmodulo2m.cc.

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

◆ specialXGCD()

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

Definition at line 195 of file rmodulo2m.cc.

196 {
197  mpz_ptr u = (mpz_ptr)omAlloc(sizeof(mpz_t));
198  mpz_init_set_ui(u, a);
199  mpz_ptr u0 = (mpz_ptr)omAlloc(sizeof(mpz_t));
200  mpz_init(u0);
201  mpz_ptr u1 = (mpz_ptr)omAlloc(sizeof(mpz_t));
202  mpz_init_set_ui(u1, 1);
203  mpz_ptr u2 = (mpz_ptr)omAlloc(sizeof(mpz_t));
204  mpz_init(u2);
205  mpz_ptr v = (mpz_ptr)omAlloc(sizeof(mpz_t));
206  mpz_init_set_ui(v, r->mod2mMask);
207  mpz_add_ui(v, v, 1); /* now: v = 2^m */
208  mpz_ptr v0 = (mpz_ptr)omAlloc(sizeof(mpz_t));
209  mpz_init(v0);
210  mpz_ptr v1 = (mpz_ptr)omAlloc(sizeof(mpz_t));
211  mpz_init(v1);
212  mpz_ptr v2 = (mpz_ptr)omAlloc(sizeof(mpz_t));
213  mpz_init_set_ui(v2, 1);
214  mpz_ptr q = (mpz_ptr)omAlloc(sizeof(mpz_t));
215  mpz_init(q);
216  mpz_ptr rr = (mpz_ptr)omAlloc(sizeof(mpz_t));
217  mpz_init(rr);
218 
219  while (mpz_sgn1(v) != 0) /* i.e., while v != 0 */
220  {
221  mpz_div(q, u, v);
222  mpz_mod(rr, u, v);
223  mpz_set(u, v);
224  mpz_set(v, rr);
225  mpz_set(u0, u2);
226  mpz_set(v0, v2);
227  mpz_mul(u2, u2, q); mpz_sub(u2, u1, u2); /* u2 = u1 - q * u2 */
228  mpz_mul(v2, v2, q); mpz_sub(v2, v1, v2); /* v2 = v1 - q * v2 */
229  mpz_set(u1, u0);
230  mpz_set(v1, v0);
231  }
232 
233  while (mpz_sgn1(u1) < 0) /* i.e., while u1 < 0 */
234  {
235  /* we add 2^m = (2^m - 1) + 1 to u1: */
236  mpz_add_ui(u1, u1, r->mod2mMask);
237  mpz_add_ui(u1, u1, 1);
238  }
239  s = mpz_get_ui(u1); /* now: 0 <= s <= 2^m - 1 */
240 
241  mpz_clear(u); omFree((ADDRESS)u);
242  mpz_clear(u0); omFree((ADDRESS)u0);
243  mpz_clear(u1); omFree((ADDRESS)u1);
244  mpz_clear(u2); omFree((ADDRESS)u2);
245  mpz_clear(v); omFree((ADDRESS)v);
246  mpz_clear(v0); omFree((ADDRESS)v0);
247  mpz_clear(v1); omFree((ADDRESS)v1);
248  mpz_clear(v2); omFree((ADDRESS)v2);
249  mpz_clear(q); omFree((ADDRESS)q);
250  mpz_clear(rr); omFree((ADDRESS)rr);
251 }
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 61 of file rmodulo2m.cc.