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

static BOOLEAN nr2mDBTest (number a, const char *f, const int l, const coeffs r)
 
static number nr2mMultM (number a, number b, const coeffs r)
 
static void nr2mInpMultM (number &a, number b, const coeffs r)
 
static number nr2mAddM (number a, number b, const coeffs r)
 
static void nr2mInpAddM (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 void nr2mInpMult (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 void nr2mInpAdd (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 71 of file rmodulo2m.cc.

◆ nr2mNegM

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

Definition at line 70 of file rmodulo2m.cc.

Function Documentation

◆ InvMod()

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

Definition at line 274 of file rmodulo2m.cc.

275 {
276  assume((unsigned long)a % 2 != 0);
277  unsigned long s;
278  specialXGCD(s, a, r);
279  return s;
280 }
const CanonicalForm int s
Definition: facAbsFact.cc:51
#define assume(x)
Definition: mod2.h:389
static void specialXGCD(unsigned long &s, unsigned long a, const coeffs r)
Definition: rmodulo2m.cc:216

◆ nr2mAdd()

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

Definition at line 376 of file rmodulo2m.cc.

377 {
378  number n=nr2mAddM(a, b, r);
379  n_Test(n,r);
380  return n;
381 }
CanonicalForm b
Definition: cfModGcd.cc:4103
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:709
static number nr2mAddM(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:51

◆ nr2mAddM()

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

Definition at line 51 of file rmodulo2m.cc.

52 {
53  return (number)
54  ((((unsigned long) a) + ((unsigned long) b)) & r->mod2mMask);
55 }

◆ nr2mAnn()

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

Definition at line 599 of file rmodulo2m.cc.

600 {
601  if ((unsigned long)b == 0)
602  return NULL;
603  if ((unsigned long)b == 1)
604  return NULL;
605  unsigned long c = r->mod2mMask + 1;
606  if (c != 0) /* i.e., if no overflow */
607  return (number)(c / (unsigned long)b);
608  else
609  {
610  /* overflow: c = 2^32 resp. 2^64, depending on platform */
611  mpz_ptr cc = (mpz_ptr)omAlloc(sizeof(mpz_t));
612  mpz_init_set_ui(cc, r->mod2mMask); mpz_add_ui(cc, cc, 1);
613  mpz_div_ui(cc, cc, (unsigned long)(unsigned long)b);
614  unsigned long s = mpz_get_ui(cc);
615  mpz_clear(cc); omFreeBinAddr((ADDRESS)cc);
616  return (number)(unsigned long)s;
617  }
618 }
void * ADDRESS
Definition: auxiliary.h:119
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omFreeBinAddr(addr)
Definition: omAllocDecl.h:258
#define NULL
Definition: omList.c:12

◆ nr2mCoeffIsEqual()

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

Definition at line 85 of file rmodulo2m.cc.

86 {
87  if (n==n_Z2m)
88  {
89  int m=(int)(long)(p);
90  unsigned long mm=r->mod2mMask;
91  if (((mm+1)>>m)==1L) return TRUE;
92  }
93  return FALSE;
94 }
#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 75 of file rmodulo2m.cc.

76 {
77  STATIC_VAR char n2mCoeffName_buf[37];
78  if (cf->modExponent>32) /* for 32/64bit arch.*/
79  snprintf(n2mCoeffName_buf,36,"ZZ/(bigint(2)^%lu)",cf->modExponent);
80  else
81  snprintf(n2mCoeffName_buf,36,"ZZ/(2^%lu)",cf->modExponent);
82  return n2mCoeffName_buf;
83 }
CanonicalForm cf
Definition: cfModGcd.cc:4083
#define STATIC_VAR
Definition: globaldefs.h:7

◆ nr2mDBTest()

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

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

430 {
431  if ((unsigned long)a == 0) return (number)0;
432  else if ((unsigned long)b % 2 == 0)
433  {
434  if ((unsigned long)b != 0)
435  {
436  while (((unsigned long)b % 2 == 0) && ((unsigned long)a % 2 == 0))
437  {
438  a = (number)((unsigned long)a / 2);
439  b = (number)((unsigned long)b / 2);
440  }
441  }
442  if ((long)b==0L)
443  {
444  WerrorS(nDivBy0);
445  return (number)0L;
446  }
447  else if ((unsigned long)b % 2 == 0)
448  {
449  WerrorS("Division not possible, even by cancelling zero divisors.");
450  WerrorS("Result is integer division without remainder.");
451  return (number) ((unsigned long) a / (unsigned long) b);
452  }
453  }
454  number n=nr2mMult(a, nr2mInversM(b,r),r);
455  n_Test(n,r);
456  return n;
457 }
void WerrorS(const char *s)
Definition: feFopen.cc:24
const char *const nDivBy0
Definition: numbers.h:89
static number nr2mInversM(number c, const coeffs r)
Definition: rmodulo2m.cc:282
static number nr2mMult(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:145

◆ nr2mDivBy()

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

Definition at line 462 of file rmodulo2m.cc.

463 {
464  if (a == NULL)
465  {
466  unsigned long c = r->mod2mMask + 1;
467  if (c != 0) /* i.e., if no overflow */
468  return (c % (unsigned long)b) == 0;
469  else
470  {
471  /* overflow: we need to check whether b
472  is zero or a power of 2: */
473  c = (unsigned long)b;
474  while (c != 0)
475  {
476  if ((c % 2) != 0) return FALSE;
477  c = c >> 1;
478  }
479  return TRUE;
480  }
481  }
482  else
483  {
484  number n = nr2mGcd(a, b, r);
485  n = nr2mDiv(b, n, r);
486  return nr2mIsUnit(n, r);
487  }
488 }
static number nr2mGcd(number a, number b, const coeffs)
Definition: rmodulo2m.cc:192
static BOOLEAN nr2mIsUnit(number a, const coeffs)
Definition: rmodulo2m.cc:396
static number nr2mDiv(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:429

◆ nr2mDivComp()

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

Definition at line 495 of file rmodulo2m.cc.

496 {
497  unsigned long a = (unsigned long)as;
498  unsigned long b = (unsigned long)bs;
499  assume(a != 0 && b != 0);
500  while (a % 2 == 0 && b % 2 == 0)
501  {
502  a = a / 2;
503  b = b / 2;
504  }
505  if (a % 2 == 0)
506  {
507  return -1;
508  }
509  else
510  {
511  if (b % 2 == 1)
512  {
513  return 2;
514  }
515  else
516  {
517  return 1;
518  }
519  }
520 }

◆ nr2mEati()

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

Definition at line 759 of file rmodulo2m.cc.

760 {
761 
762  if (((*s) >= '0') && ((*s) <= '9'))
763  {
764  (*i) = 0;
765  do
766  {
767  (*i) *= 10;
768  (*i) += *s++ - '0';
769  if ((*i) >= (MAX_INT_VAL / 10)) (*i) = (*i) & r->mod2mMask;
770  }
771  while (((*s) >= '0') && ((*s) <= '9'));
772  (*i) = (*i) & r->mod2mMask;
773  }
774  else (*i) = 1;
775  return s;
776 }
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 424 of file rmodulo2m.cc.

425 {
426  return (a == b);
427 }

◆ nr2mExtGcd()

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

Definition at line 305 of file rmodulo2m.cc.

306 {
307  unsigned long res = 0;
308  if ((unsigned long)a == 0 && (unsigned long)b == 0) return (number)1;
309  while ((unsigned long)a % 2 == 0 && (unsigned long)b % 2 == 0)
310  {
311  a = (number)((unsigned long)a / 2);
312  b = (number)((unsigned long)b / 2);
313  res++;
314  }
315  if ((unsigned long)b % 2 == 0)
316  {
317  *t = NULL;
318  *s = nr2mInvers(a,r);
319  return (number)((1L << res)); // * (unsigned long) a); // (2**res)*a a is a unit
320  }
321  else
322  {
323  *s = NULL;
324  *t = nr2mInvers(b,r);
325  return (number)((1L << res)); // * (unsigned long) b); // (2**res)*b b is a unit
326  }
327 }
CanonicalForm res
Definition: facAbsFact.cc:60
static number nr2mInvers(number c, const coeffs r)
Definition: rmodulo2m.cc:291

◆ nr2mGcd()

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

Definition at line 192 of file rmodulo2m.cc.

193 {
194  unsigned long res = 0;
195  if ((unsigned long)a == 0 && (unsigned long)b == 0) return (number)1;
196  while ((unsigned long)a % 2 == 0 && (unsigned long)b % 2 == 0)
197  {
198  a = (number)((unsigned long)a / 2);
199  b = (number)((unsigned long)b / 2);
200  res++;
201  }
202 // if ((unsigned long)b % 2 == 0)
203 // {
204 // return (number)((1L << res)); // * (unsigned long) a); // (2**res)*a a is a unit
205 // }
206 // else
207 // {
208  return (number)((1L << res)); // * (unsigned long) b); // (2**res)*b b is a unit
209 // }
210 }

◆ nr2mGetUnit()

static number nr2mGetUnit ( number  k,
const  coeffs 
)
static

Definition at line 401 of file rmodulo2m.cc.

402 {
403  if (k == NULL) return (number)1;
404  unsigned long erg = (unsigned long)k;
405  while (erg % 2 == 0) erg = erg / 2;
406  return (number)erg;
407 }
int k
Definition: cfEzgcd.cc:99

◆ nr2mGreater()

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

Definition at line 490 of file rmodulo2m.cc.

491 {
492  return nr2mDivBy(a, b,r);
493 }
static BOOLEAN nr2mDivBy(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:462

◆ nr2mGreaterZero()

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

Definition at line 135 of file rmodulo2m.cc.

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

◆ nr2mInit()

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

Definition at line 349 of file rmodulo2m.cc.

350 {
351  if (i == 0) return (number)(unsigned long)0;
352 
353  long ii = i;
354  unsigned long j = (unsigned long)1;
355  if (ii < 0) { j = r->mod2mMask; ii = -ii; }
356  unsigned long k = (unsigned long)ii;
357  k = k & r->mod2mMask;
358  /* now we have: i = j * k mod 2^m */
359  return nr2mMult((number)j, (number)k, r);
360 }
int j
Definition: facHensel.cc:110

◆ nr2mInitChar()

BOOLEAN nr2mInitChar ( coeffs  r,
void *  p 
)

Definition at line 797 of file rmodulo2m.cc.

798 {
799  assume( getCoeffType(r) == n_Z2m );
800  nr2mInitExp((int)(long)(p), r);
801 
802  r->is_field=FALSE;
803  r->is_domain=FALSE;
804  r->rep=n_rep_int;
805 
806  //r->cfKillChar = ndKillChar; /* dummy*/
807  r->nCoeffIsEqual = nr2mCoeffIsEqual;
808 
809  r->modBase = (mpz_ptr) omAllocBin (gmp_nrz_bin);
810  mpz_init_set_si (r->modBase, 2L);
811  r->modNumber= (mpz_ptr) omAllocBin (gmp_nrz_bin);
812  mpz_init (r->modNumber);
813  mpz_pow_ui (r->modNumber, r->modBase, r->modExponent);
814 
815  /* next cast may yield an overflow as mod2mMask is an unsigned long */
816  r->ch = (int)r->mod2mMask + 1;
817 
818  r->cfInit = nr2mInit;
819  //r->cfCopy = ndCopy;
820  r->cfInt = nr2mInt;
821  r->cfAdd = nr2mAdd;
822  r->cfInpAdd = nr2mInpAdd;
823  r->cfSub = nr2mSub;
824  r->cfMult = nr2mMult;
825  r->cfInpMult = nr2mInpMult;
826  r->cfDiv = nr2mDiv;
827  r->cfAnn = nr2mAnn;
828  r->cfIntMod = nr2mMod;
829  r->cfExactDiv = nr2mDiv;
830  r->cfInpNeg = nr2mNeg;
831  r->cfInvers = nr2mInvers;
832  r->cfDivBy = nr2mDivBy;
833  r->cfDivComp = nr2mDivComp;
834  r->cfGreater = nr2mGreater;
835  r->cfEqual = nr2mEqual;
836  r->cfIsZero = nr2mIsZero;
837  r->cfIsOne = nr2mIsOne;
838  r->cfIsMOne = nr2mIsMOne;
839  r->cfGreaterZero = nr2mGreaterZero;
840  r->cfWriteLong = nr2mWrite;
841  r->cfRead = nr2mRead;
842  r->cfPower = nr2mPower;
843  r->cfSetMap = nr2mSetMap;
844 // r->cfNormalize = ndNormalize; // default
845  r->cfLcm = nr2mLcm;
846  r->cfGcd = nr2mGcd;
847  r->cfIsUnit = nr2mIsUnit;
848  r->cfGetUnit = nr2mGetUnit;
849  r->cfExtGcd = nr2mExtGcd;
850  r->cfCoeffName = nr2mCoeffName;
851  r->cfQuot1 = nr2mQuot1;
852 #ifdef LDEBUG
853  r->cfDBTest = nr2mDBTest;
854 #endif
855  r->has_simple_Alloc=TRUE;
856  return FALSE;
857 }
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:110
#define LDEBUG
Definition: mod2.h:307
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
static nMapFunc nr2mSetMap(const coeffs src, const coeffs dst)
Definition: rmodulo2m.cc:686
static void nr2mWrite(number a, const coeffs r)
Definition: rmodulo2m.cc:753
static void nr2mInpAdd(number &a, number b, const coeffs r)
Definition: rmodulo2m.cc:383
static number nr2mSub(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:389
static number nr2mLcm(number a, number b, const coeffs)
Definition: rmodulo2m.cc:169
static BOOLEAN nr2mIsOne(number a, const coeffs)
Definition: rmodulo2m.cc:414
static number nr2mAnn(number b, const coeffs r)
Definition: rmodulo2m.cc:599
static number nr2mInit(long i, const coeffs r)
Definition: rmodulo2m.cc:349
static char * nr2mCoeffName(const coeffs cf)
Definition: rmodulo2m.cc:75
static number nr2mExtGcd(number a, number b, number *s, number *t, const coeffs r)
Definition: rmodulo2m.cc:305
static number nr2mGetUnit(number k, const coeffs)
Definition: rmodulo2m.cc:401
static void nr2mInitExp(int m, coeffs r)
Definition: rmodulo2m.cc:746
static void nr2mPower(number a, int i, number *result, const coeffs r)
Definition: rmodulo2m.cc:329
static int nr2mDivComp(number as, number bs, const coeffs)
Definition: rmodulo2m.cc:495
static long nr2mInt(number &n, const coeffs r)
Definition: rmodulo2m.cc:366
static BOOLEAN nr2mGreaterZero(number k, const coeffs r)
Definition: rmodulo2m.cc:135
static number nr2mNeg(number c, const coeffs r)
Definition: rmodulo2m.cc:620
EXTERN_VAR omBin gmp_nrz_bin
Definition: rmodulo2m.cc:73
static BOOLEAN nr2mDBTest(number a, const char *f, const int l, const coeffs r)
Definition: rmodulo2m.cc:26
static number nr2mMod(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:522
static BOOLEAN nr2mCoeffIsEqual(const coeffs r, n_coeffType n, void *p)
Definition: rmodulo2m.cc:85
static number nr2mAdd(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:376
static void nr2mInpMult(number &a, number b, const coeffs r)
Definition: rmodulo2m.cc:156
static BOOLEAN nr2mEqual(number a, number b, const coeffs)
Definition: rmodulo2m.cc:424
static BOOLEAN nr2mGreater(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:490
static BOOLEAN nr2mIsZero(number a, const coeffs)
Definition: rmodulo2m.cc:409
static const char * nr2mRead(const char *s, number *a, const coeffs r)
Definition: rmodulo2m.cc:778
static BOOLEAN nr2mIsMOne(number a, const coeffs r)
Definition: rmodulo2m.cc:419
static coeffs nr2mQuot1(number c, const coeffs r)
Definition: rmodulo2m.cc:96

◆ nr2mInitExp()

static void nr2mInitExp ( int  m,
coeffs  r 
)
static

Definition at line 746 of file rmodulo2m.cc.

747 {
748  nr2mSetExp(m, r);
749  if (m < 2)
750  WarnS("nr2mInitExp unexpectedly called with m = 1 (we continue with Z/2^2");
751 }
#define WarnS
Definition: emacs.cc:78
static void nr2mSetExp(int m, coeffs r)
Definition: rmodulo2m.cc:728

◆ nr2mInpAdd()

static void nr2mInpAdd ( number &  a,
number  b,
const coeffs  r 
)
static

Definition at line 383 of file rmodulo2m.cc.

384 {
385  nr2mInpAddM(a, b, r);
386  n_Test(a,r);
387 }
static void nr2mInpAddM(number &a, number b, const coeffs r)
Definition: rmodulo2m.cc:57

◆ nr2mInpAddM()

static void nr2mInpAddM ( number &  a,
number  b,
const coeffs  r 
)
inlinestatic

Definition at line 57 of file rmodulo2m.cc.

58 {
59  a= (number)
60  ((((unsigned long) a) + ((unsigned long) b)) & r->mod2mMask);
61 }

◆ nr2mInpMult()

static void nr2mInpMult ( number &  a,
number  b,
const coeffs  r 
)
static

Definition at line 156 of file rmodulo2m.cc.

157 {
158  if (((unsigned long)a == 0) || ((unsigned long)b == 0))
159  { a=(number)0; return; }
160  else
161  nr2mInpMultM(a, b, r);
162  n_Test(a,r);
163 }
static void nr2mInpMultM(number &a, number b, const coeffs r)
Definition: rmodulo2m.cc:45

◆ nr2mInpMultM()

static void nr2mInpMultM ( number &  a,
number  b,
const coeffs  r 
)
inlinestatic

Definition at line 45 of file rmodulo2m.cc.

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

◆ nr2mInt()

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

Definition at line 366 of file rmodulo2m.cc.

367 {
368  unsigned long nn = (unsigned long)n;
369  unsigned long l = r->mod2mMask >> 1; l++; /* now: l = 2^(m-1) */
370  if ((unsigned long)nn > l)
371  return (long)((unsigned long)nn - r->mod2mMask - 1);
372  else
373  return (long)((unsigned long)nn);
374 }

◆ nr2mInvers()

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

Definition at line 291 of file rmodulo2m.cc.

292 {
293  if ((unsigned long)c % 2 == 0)
294  {
295  WerrorS("division by zero divisor");
296  return (number)0;
297  }
298  return nr2mInversM(c, r);
299 }

◆ nr2mInversM()

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

Definition at line 282 of file rmodulo2m.cc.

283 {
284  assume((unsigned long)c % 2 != 0);
285  // Table !!!
286  unsigned long inv;
287  inv = InvMod((unsigned long)c,r);
288  return (number)inv;
289 }
static unsigned long InvMod(unsigned long a, const coeffs r)
Definition: rmodulo2m.cc:274

◆ nr2mIsMOne()

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

Definition at line 419 of file rmodulo2m.cc.

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

◆ nr2mIsOne()

static BOOLEAN nr2mIsOne ( number  a,
const  coeffs 
)
static

Definition at line 414 of file rmodulo2m.cc.

415 {
416  return 1 == (unsigned long)a;
417 }

◆ nr2mIsUnit()

static BOOLEAN nr2mIsUnit ( number  a,
const  coeffs 
)
static

Definition at line 396 of file rmodulo2m.cc.

397 {
398  return ((unsigned long)a % 2 == 1);
399 }

◆ nr2mIsZero()

static BOOLEAN nr2mIsZero ( number  a,
const  coeffs 
)
static

Definition at line 409 of file rmodulo2m.cc.

410 {
411  return 0 == (unsigned long)a;
412 }

◆ nr2mLcm()

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

Definition at line 169 of file rmodulo2m.cc.

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

◆ nr2mMapGMP()

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

Definition at line 651 of file rmodulo2m.cc.

652 {
653  mpz_ptr erg = (mpz_ptr)omAllocBin(gmp_nrz_bin);
654  mpz_init(erg);
655  mpz_ptr k = (mpz_ptr)omAlloc(sizeof(mpz_t));
656  mpz_init_set_ui(k, dst->mod2mMask);
657 
658  mpz_and(erg, (mpz_ptr)from, k);
659  number res = (number) mpz_get_ui(erg);
660 
661  mpz_clear(erg); omFreeBinAddr((ADDRESS)erg);
662  mpz_clear(k); omFreeBinAddr((ADDRESS)k);
663 
664  return (number)res;
665 }

◆ nr2mMapMachineInt()

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

Definition at line 628 of file rmodulo2m.cc.

629 {
630  unsigned long i = ((unsigned long)from) % (dst->mod2mMask + 1) ;
631  return (number)i;
632 }

◆ nr2mMapProject()

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

Definition at line 634 of file rmodulo2m.cc.

635 {
636  unsigned long i = ((unsigned long)from) % (dst->mod2mMask + 1);
637  return (number)i;
638 }

◆ nr2mMapQ()

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

Definition at line 667 of file rmodulo2m.cc.

668 {
669  mpz_ptr gmp = (mpz_ptr)omAllocBin(gmp_nrz_bin);
670  nlMPZ(gmp, from, src);
671  number res=nr2mMapGMP((number)gmp,src,dst);
672  mpz_clear(gmp); omFreeBinAddr((ADDRESS)gmp);
673  return res;
674 }
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:651

◆ nr2mMapZ()

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

Definition at line 676 of file rmodulo2m.cc.

677 {
678  if (SR_HDL(from) & SR_INT)
679  {
680  long f_i=SR_TO_INT(from);
681  return nr2mInit(f_i,dst);
682  }
683  return nr2mMapGMP(from,src,dst);
684 }
#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 640 of file rmodulo2m.cc.

641 {
642  unsigned long j = (unsigned long)1;
643  long ii = (long)from;
644  if (ii < 0) { j = dst->mod2mMask; ii = -ii; }
645  unsigned long i = (unsigned long)ii;
646  i = i & dst->mod2mMask;
647  /* now we have: from = j * i mod 2^m */
648  return nr2mMult((number)i, (number)j, dst);
649 }

◆ nr2mMod()

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

Definition at line 522 of file rmodulo2m.cc.

523 {
524  /*
525  We need to return the number rr which is uniquely determined by the
526  following two properties:
527  (1) 0 <= rr < |b| (with respect to '<' and '<=' performed in Z x Z)
528  (2) There exists some k in the integers Z such that a = k * b + rr.
529  Consider g := gcd(2^m, |b|). Note that then |b|/g is a unit in Z/2^m.
530  Now, there are three cases:
531  (a) g = 1
532  Then |b| is a unit in Z/2^m, i.e. |b| (and also b) divides a.
533  Thus rr = 0.
534  (b) g <> 1 and g divides a
535  Then a = (a/g) * (|b|/g)^(-1) * b (up to sign), i.e. again rr = 0.
536  (c) g <> 1 and g does not divide a
537  Let's denote the division with remainder of a by g as follows:
538  a = s * g + t. Then t = a - s * g = a - s * (|b|/g)^(-1) * |b|
539  fulfills (1) and (2), i.e. rr := t is the correct result. Hence
540  in this third case, rr is the remainder of division of a by g in Z.
541  This algorithm is the same as for the case Z/n, except that we may
542  compute the gcd of |b| and 2^m "by hand": We just extract the highest
543  power of 2 (<= 2^m) that is contained in b.
544  */
545  assume((unsigned long) b != 0);
546  unsigned long g = 1;
547  unsigned long b_div = (unsigned long) b;
548 
549  /*
550  * b_div is unsigned, so that (b_div < 0) evaluates false at compile-time
551  *
552  if (b_div < 0) b_div = -b_div; // b_div now represents |b|, BUT b_div is unsigned!
553  */
554 
555  unsigned long rr = 0;
556  while ((g < r->mod2mMask ) && (b_div > 0) && (b_div % 2 == 0))
557  {
558  b_div = b_div >> 1;
559  g = g << 1;
560  } // g is now the gcd of 2^m and |b|
561 
562  if (g != 1) rr = (unsigned long)a % g;
563  return (number)rr;
564 }
g
Definition: cfModGcd.cc:4090

◆ nr2mMult()

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

Definition at line 145 of file rmodulo2m.cc.

146 {
147  number n;
148  if (((unsigned long)a == 0) || ((unsigned long)b == 0))
149  return (number)0;
150  else
151  n=nr2mMultM(a, b, r);
152  n_Test(n,r);
153  return n;
154 }
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 620 of file rmodulo2m.cc.

621 {
622  if ((unsigned long)c == 0) return c;
623  number n=nr2mNegM(c, r);
624  n_Test(n,r);
625  return n;
626 }
#define nr2mNegM(A, r)
Definition: rmodulo2m.cc:70

◆ nr2mPower()

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

Definition at line 329 of file rmodulo2m.cc.

330 {
331  if (i == 0)
332  {
333  *(unsigned long *)result = 1;
334  }
335  else if (i == 1)
336  {
337  *result = a;
338  }
339  else
340  {
341  nr2mPower(a, i-1, result, r);
342  *result = nr2mMultM(a, *result, r);
343  }
344 }
return result
Definition: facAbsBiFact.cc:75

◆ nr2mQuot1()

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

Definition at line 96 of file rmodulo2m.cc.

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

779 {
780  int z;
781  int n=1;
782 
783  s = nr2mEati(s, &z,r);
784  if ((*s) == '/')
785  {
786  s++;
787  s = nr2mEati(s, &n,r);
788  }
789  if (n == 1)
790  *a = (number)(long)z;
791  else
792  *a = nr2mDiv((number)(long)z,(number)(long)n,r);
793  return s;
794 }
static const char * nr2mEati(const char *s, int *i, const coeffs r)
Definition: rmodulo2m.cc:759

◆ nr2mSetExp()

static void nr2mSetExp ( int  m,
coeffs  r 
)
static

Definition at line 728 of file rmodulo2m.cc.

729 {
730  if (m > 1)
731  {
732  /* we want mod2mMask to be the bit pattern
733  '111..1' consisting of m one's: */
734  r->modExponent= m;
735  r->mod2mMask = 1;
736  for (int i = 1; i < m; i++) r->mod2mMask = (r->mod2mMask << 1) + 1;
737  }
738  else
739  {
740  r->modExponent= 2;
741  /* code unexpectedly called with m = 1; we continue with m = 2: */
742  r->mod2mMask = 3; /* i.e., '11' in binary representation */
743  }
744 }

◆ nr2mSetMap()

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

Definition at line 686 of file rmodulo2m.cc.

687 {
688  if ((src->rep==n_rep_int) && nCoeff_is_Ring_2toM(src)
689  && (src->mod2mMask < dst->mod2mMask))
690  { /* i.e. map an integer mod 2^s into Z mod 2^t, where t < s */
691  return nr2mMapMachineInt;
692  }
693  if ((src->rep==n_rep_int) && nCoeff_is_Ring_2toM(src)
694  && (src->mod2mMask > dst->mod2mMask))
695  { /* i.e. map an integer mod 2^s into Z mod 2^t, where t > s */
696  // to be done
697  return nr2mMapProject;
698  }
699  if ((src->rep==n_rep_gmp) && nCoeff_is_Z(src))
700  {
701  return nr2mMapGMP;
702  }
703  if ((src->rep==n_rep_gap_gmp) /*&& nCoeff_is_Z(src)*/)
704  {
705  return nr2mMapZ;
706  }
707  if ((src->rep==n_rep_gap_rat) && (nCoeff_is_Q(src)||nCoeff_is_Z(src)))
708  {
709  return nr2mMapQ;
710  }
711  if ((src->rep==n_rep_int) && nCoeff_is_Zp(src) && (src->ch == 2))
712  {
713  return nr2mMapZp;
714  }
715  if ((src->rep==n_rep_gmp) &&
716  (nCoeff_is_Ring_PtoM(src) || nCoeff_is_Zn(src)))
717  {
718  if (mpz_divisible_2exp_p(src->modNumber,dst->modExponent))
719  return nr2mMapGMP;
720  }
721  return NULL; // default
722 }
static FORCE_INLINE BOOLEAN nCoeff_is_Z(const coeffs r)
Definition: coeffs.h:813
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_PtoM(const coeffs r)
Definition: coeffs.h:724
static FORCE_INLINE BOOLEAN nCoeff_is_Q(const coeffs r)
Definition: coeffs.h:803
static FORCE_INLINE BOOLEAN nCoeff_is_Zn(const coeffs r)
Definition: coeffs.h:823
static FORCE_INLINE BOOLEAN nCoeff_is_Zp(const coeffs r)
Definition: coeffs.h:797
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_2toM(const coeffs r)
Definition: coeffs.h:721
@ 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:634
static number nr2mMapQ(number from, const coeffs src, const coeffs dst)
Definition: rmodulo2m.cc:667
number nr2mMapZp(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:640
static number nr2mMapMachineInt(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:628
static number nr2mMapZ(number from, const coeffs src, const coeffs dst)
Definition: rmodulo2m.cc:676

◆ nr2mSub()

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

Definition at line 389 of file rmodulo2m.cc.

390 {
391  number n=nr2mSubM(a, b, r);
392  n_Test(n,r);
393  return n;
394 }
static number nr2mSubM(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:63

◆ nr2mSubM()

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

Definition at line 63 of file rmodulo2m.cc.

64 {
65  return (number)((unsigned long)a < (unsigned long)b ?
66  r->mod2mMask+1 - (unsigned long)b + (unsigned long)a:
67  (unsigned long)a - (unsigned long)b);
68 }

◆ nr2mWrite()

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

Definition at line 753 of file rmodulo2m.cc.

754 {
755  long i = nr2mInt(a, r);
756  StringAppend("%ld", i);
757 }
#define StringAppend
Definition: emacs.cc:79

◆ specialXGCD()

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

Definition at line 216 of file rmodulo2m.cc.

217 {
218  mpz_ptr u = (mpz_ptr)omAlloc(sizeof(mpz_t));
219  mpz_init_set_ui(u, a);
220  mpz_ptr u0 = (mpz_ptr)omAlloc(sizeof(mpz_t));
221  mpz_init(u0);
222  mpz_ptr u1 = (mpz_ptr)omAlloc(sizeof(mpz_t));
223  mpz_init_set_ui(u1, 1);
224  mpz_ptr u2 = (mpz_ptr)omAlloc(sizeof(mpz_t));
225  mpz_init(u2);
226  mpz_ptr v = (mpz_ptr)omAlloc(sizeof(mpz_t));
227  mpz_init_set_ui(v, r->mod2mMask);
228  mpz_add_ui(v, v, 1); /* now: v = 2^m */
229  mpz_ptr v0 = (mpz_ptr)omAlloc(sizeof(mpz_t));
230  mpz_init(v0);
231  mpz_ptr v1 = (mpz_ptr)omAlloc(sizeof(mpz_t));
232  mpz_init(v1);
233  mpz_ptr v2 = (mpz_ptr)omAlloc(sizeof(mpz_t));
234  mpz_init_set_ui(v2, 1);
235  mpz_ptr q = (mpz_ptr)omAlloc(sizeof(mpz_t));
236  mpz_init(q);
237  mpz_ptr rr = (mpz_ptr)omAlloc(sizeof(mpz_t));
238  mpz_init(rr);
239 
240  while (mpz_sgn1(v) != 0) /* i.e., while v != 0 */
241  {
242  mpz_div(q, u, v);
243  mpz_mod(rr, u, v);
244  mpz_set(u, v);
245  mpz_set(v, rr);
246  mpz_set(u0, u2);
247  mpz_set(v0, v2);
248  mpz_mul(u2, u2, q); mpz_sub(u2, u1, u2); /* u2 = u1 - q * u2 */
249  mpz_mul(v2, v2, q); mpz_sub(v2, v1, v2); /* v2 = v1 - q * v2 */
250  mpz_set(u1, u0);
251  mpz_set(v1, v0);
252  }
253 
254  while (mpz_sgn1(u1) < 0) /* i.e., while u1 < 0 */
255  {
256  /* we add 2^m = (2^m - 1) + 1 to u1: */
257  mpz_add_ui(u1, u1, r->mod2mMask);
258  mpz_add_ui(u1, u1, 1);
259  }
260  s = mpz_get_ui(u1); /* now: 0 <= s <= 2^m - 1 */
261 
262  mpz_clear(u); omFreeBinAddr((ADDRESS)u);
263  mpz_clear(u0); omFreeBinAddr((ADDRESS)u0);
264  mpz_clear(u1); omFreeBinAddr((ADDRESS)u1);
265  mpz_clear(u2); omFreeBinAddr((ADDRESS)u2);
266  mpz_clear(v); omFreeBinAddr((ADDRESS)v);
267  mpz_clear(v0); omFreeBinAddr((ADDRESS)v0);
268  mpz_clear(v1); omFreeBinAddr((ADDRESS)v1);
269  mpz_clear(v2); omFreeBinAddr((ADDRESS)v2);
270  mpz_clear(q); omFreeBinAddr((ADDRESS)q);
271  mpz_clear(rr); omFreeBinAddr((ADDRESS)rr);
272 }
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
#define mpz_sgn1(A)
Definition: si_gmp.h:18

Variable Documentation

◆ gmp_nrz_bin

EXTERN_VAR omBin gmp_nrz_bin

Definition at line 73 of file rmodulo2m.cc.