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

Go to the source code of this file.

Macros

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

Functions

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

Variables

EXTERN_VAR omBin gmp_nrz_bin
 

Macro Definition Documentation

◆ nr2mEqualM

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

Definition at line 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 262 of file rmodulo2m.cc.

263 {
264  assume((unsigned long)a % 2 != 0);
265  unsigned long s;
266  specialXGCD(s, a, r);
267  return s;
268 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
#define assume(x)
Definition: mod2.h:390
static void specialXGCD(unsigned long &s, unsigned long a, const coeffs r)
Definition: rmodulo2m.cc:204

◆ nr2mAdd()

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

Definition at line 364 of file rmodulo2m.cc.

365 {
366  number n=nr2mAddM(a, b, r);
367  n_Test(n,r);
368  return n;
369 }
CanonicalForm b
Definition: cfModGcd.cc:4044
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:738
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 }
CanonicalForm b
Definition: cfModGcd.cc:4044

◆ nr2mAnn()

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

Definition at line 576 of file rmodulo2m.cc.

577 {
578  if ((unsigned long)b == 0)
579  return NULL;
580  if ((unsigned long)b == 1)
581  return NULL;
582  unsigned long c = r->mod2mMask + 1;
583  if (c != 0) /* i.e., if no overflow */
584  return (number)(c / (unsigned long)b);
585  else
586  {
587  /* overflow: c = 2^32 resp. 2^64, depending on platform */
588  mpz_ptr cc = (mpz_ptr)omAlloc(sizeof(mpz_t));
589  mpz_init_set_ui(cc, r->mod2mMask); mpz_add_ui(cc, cc, 1);
590  mpz_div_ui(cc, cc, (unsigned long)(unsigned long)b);
591  unsigned long s = mpz_get_ui(cc);
592  mpz_clear(cc); omFree((ADDRESS)cc);
593  return (number)(unsigned long)s;
594  }
595 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
void * ADDRESS
Definition: auxiliary.h:135
#define omAlloc(size)
Definition: omAllocDecl.h:210
CanonicalForm b
Definition: cfModGcd.cc:4044
#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 77 of file rmodulo2m.cc.

78 {
79  if (n==n_Z2m)
80  {
81  int m=(int)(long)(p);
82  unsigned long mm=r->mod2mMask;
83  if (((mm+1)>>m)==1L) return TRUE;
84  }
85  return FALSE;
86 }
only used if HAVE_RINGS is defined
Definition: coeffs.h:47
#define FALSE
Definition: auxiliary.h:96
#define TRUE
Definition: auxiliary.h:100
int m
Definition: cfEzgcd.cc:121
int p
Definition: cfModGcd.cc:4019

◆ 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 }
#define STATIC_VAR
Definition: globaldefs.h:7

◆ nr2mCoeffString()

static char* nr2mCoeffString ( const coeffs  r)
static

Definition at line 88 of file rmodulo2m.cc.

89 {
90  return omStrDup(nr2mCoeffName(r));
91 }
static char * nr2mCoeffName(const coeffs cf)
Definition: rmodulo2m.cc:62
#define omStrDup(s)
Definition: omAllocDecl.h:263

◆ nr2mCoeffWrite()

static void nr2mCoeffWrite ( const coeffs  r,
BOOLEAN   
)
static

Definition at line 72 of file rmodulo2m.cc.

73 {
75 }
static char * nr2mCoeffName(const coeffs cf)
Definition: rmodulo2m.cc:62
void PrintS(const char *s)
Definition: reporter.cc:284

◆ 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 }
#define Print
Definition: emacs.cc:80
#define FALSE
Definition: auxiliary.h:96
#define TRUE
Definition: auxiliary.h:100
FILE * f
Definition: checklibs.c:9
int l
Definition: cfEzgcd.cc:93

◆ nr2mDiv()

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

Definition at line 411 of file rmodulo2m.cc.

412 {
413  if ((unsigned long)a == 0) return (number)0;
414  else if ((unsigned long)b % 2 == 0)
415  {
416  if ((unsigned long)b != 0)
417  {
418  while (((unsigned long)b % 2 == 0) && ((unsigned long)a % 2 == 0))
419  {
420  a = (number)((unsigned long)a / 2);
421  b = (number)((unsigned long)b / 2);
422  }
423  }
424  if ((unsigned long)b % 2 == 0)
425  {
426  WerrorS("Division not possible, even by cancelling zero divisors.");
427  WerrorS("Result is integer division without remainder.");
428  return (number) ((unsigned long) a / (unsigned long) b);
429  }
430  }
431  number n=(number)nr2mMult(a, nr2mInversM(b,r),r);
432  n_Test(n,r);
433  return n;
434 }
void WerrorS(const char *s)
Definition: feFopen.cc:24
CanonicalForm b
Definition: cfModGcd.cc:4044
static number nr2mInversM(number c, const coeffs r)
Definition: rmodulo2m.cc:270
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:738
static number nr2mMult(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:142

◆ nr2mDivBy()

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

Definition at line 439 of file rmodulo2m.cc.

440 {
441  if (a == NULL)
442  {
443  unsigned long c = r->mod2mMask + 1;
444  if (c != 0) /* i.e., if no overflow */
445  return (c % (unsigned long)b) == 0;
446  else
447  {
448  /* overflow: we need to check whether b
449  is zero or a power of 2: */
450  c = (unsigned long)b;
451  while (c != 0)
452  {
453  if ((c % 2) != 0) return FALSE;
454  c = c >> 1;
455  }
456  return TRUE;
457  }
458  }
459  else
460  {
461  number n = nr2mGcd(a, b, r);
462  n = nr2mDiv(b, n, r);
463  return nr2mIsUnit(n, r);
464  }
465 }
#define FALSE
Definition: auxiliary.h:96
static number nr2mDiv(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:411
#define TRUE
Definition: auxiliary.h:100
CanonicalForm b
Definition: cfModGcd.cc:4044
#define NULL
Definition: omList.c:12
static BOOLEAN nr2mIsUnit(number a, const coeffs)
Definition: rmodulo2m.cc:378
static number nr2mGcd(number a, number b, const coeffs)
Definition: rmodulo2m.cc:180

◆ nr2mDivComp()

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

Definition at line 472 of file rmodulo2m.cc.

473 {
474  unsigned long a = (unsigned long)as;
475  unsigned long b = (unsigned long)bs;
476  assume(a != 0 && b != 0);
477  while (a % 2 == 0 && b % 2 == 0)
478  {
479  a = a / 2;
480  b = b / 2;
481  }
482  if (a % 2 == 0)
483  {
484  return -1;
485  }
486  else
487  {
488  if (b % 2 == 1)
489  {
490  return 2;
491  }
492  else
493  {
494  return 1;
495  }
496  }
497 }
CanonicalForm b
Definition: cfModGcd.cc:4044
#define assume(x)
Definition: mod2.h:390

◆ nr2mEati()

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

Definition at line 742 of file rmodulo2m.cc.

743 {
744 
745  if (((*s) >= '0') && ((*s) <= '9'))
746  {
747  (*i) = 0;
748  do
749  {
750  (*i) *= 10;
751  (*i) += *s++ - '0';
752  if ((*i) >= (MAX_INT_VAL / 10)) (*i) = (*i) & r->mod2mMask;
753  }
754  while (((*s) >= '0') && ((*s) <= '9'));
755  (*i) = (*i) & r->mod2mMask;
756  }
757  else (*i) = 1;
758  return s;
759 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
const int MAX_INT_VAL
Definition: mylimits.h:12
int i
Definition: cfEzgcd.cc:125

◆ nr2mEqual()

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

Definition at line 406 of file rmodulo2m.cc.

407 {
408  return (a == b);
409 }
CanonicalForm b
Definition: cfModGcd.cc:4044

◆ nr2mExtGcd()

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

Definition at line 293 of file rmodulo2m.cc.

294 {
295  unsigned long res = 0;
296  if ((unsigned long)a == 0 && (unsigned long)b == 0) return (number)1;
297  while ((unsigned long)a % 2 == 0 && (unsigned long)b % 2 == 0)
298  {
299  a = (number)((unsigned long)a / 2);
300  b = (number)((unsigned long)b / 2);
301  res++;
302  }
303  if ((unsigned long)b % 2 == 0)
304  {
305  *t = NULL;
306  *s = nr2mInvers(a,r);
307  return (number)((1L << res)); // * (unsigned long) a); // (2**res)*a a is a unit
308  }
309  else
310  {
311  *s = NULL;
312  *t = nr2mInvers(b,r);
313  return (number)((1L << res)); // * (unsigned long) b); // (2**res)*b b is a unit
314  }
315 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
CanonicalForm b
Definition: cfModGcd.cc:4044
CanonicalForm res
Definition: facAbsFact.cc:64
#define NULL
Definition: omList.c:12
static number nr2mInvers(number c, const coeffs r)
Definition: rmodulo2m.cc:279

◆ nr2mGcd()

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

Definition at line 180 of file rmodulo2m.cc.

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

◆ nr2mGetUnit()

static number nr2mGetUnit ( number  k,
const coeffs   
)
static

Definition at line 383 of file rmodulo2m.cc.

384 {
385  if (k == NULL) return (number)1;
386  unsigned long erg = (unsigned long)k;
387  while (erg % 2 == 0) erg = erg / 2;
388  return (number)erg;
389 }
int k
Definition: cfEzgcd.cc:92
#define NULL
Definition: omList.c:12

◆ nr2mGreater()

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

Definition at line 467 of file rmodulo2m.cc.

468 {
469  return nr2mDivBy(a, b,r);
470 }
static BOOLEAN nr2mDivBy(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:439
CanonicalForm b
Definition: cfModGcd.cc:4044

◆ nr2mGreaterZero()

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

Definition at line 132 of file rmodulo2m.cc.

133 {
134  if ((unsigned long)k == 0) return FALSE;
135  if ((unsigned long)k > ((r->mod2mMask >> 1) + 1)) return FALSE;
136  return TRUE;
137 }
#define FALSE
Definition: auxiliary.h:96
#define TRUE
Definition: auxiliary.h:100
int k
Definition: cfEzgcd.cc:92

◆ nr2mInit()

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

Definition at line 337 of file rmodulo2m.cc.

338 {
339  if (i == 0) return (number)(unsigned long)i;
340 
341  long ii = i;
342  unsigned long j = (unsigned long)1;
343  if (ii < 0) { j = r->mod2mMask; ii = -ii; }
344  unsigned long k = (unsigned long)ii;
345  k = k & r->mod2mMask;
346  /* now we have: i = j * k mod 2^m */
347  return (number)nr2mMult((number)j, (number)k, r);
348 }
int j
Definition: facHensel.cc:105
int k
Definition: cfEzgcd.cc:92
int i
Definition: cfEzgcd.cc:125
static number nr2mMult(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:142

◆ nr2mInitChar()

BOOLEAN nr2mInitChar ( coeffs  r,
void *  p 
)

Definition at line 780 of file rmodulo2m.cc.

781 {
782  assume( getCoeffType(r) == n_Z2m );
783  nr2mInitExp((int)(long)(p), r);
784 
785  r->is_field=FALSE;
786  r->is_domain=FALSE;
787  r->rep=n_rep_int;
788 
789  //r->cfKillChar = ndKillChar; /* dummy*/
790  r->nCoeffIsEqual = nr2mCoeffIsEqual;
791  r->cfCoeffString = nr2mCoeffString;
792 
793  r->modBase = (mpz_ptr) omAllocBin (gmp_nrz_bin);
794  mpz_init_set_si (r->modBase, 2L);
795  r->modNumber= (mpz_ptr) omAllocBin (gmp_nrz_bin);
796  mpz_init (r->modNumber);
797  mpz_pow_ui (r->modNumber, r->modBase, r->modExponent);
798 
799  /* next cast may yield an overflow as mod2mMask is an unsigned long */
800  r->ch = (int)r->mod2mMask + 1;
801 
802  r->cfInit = nr2mInit;
803  //r->cfCopy = ndCopy;
804  r->cfInt = nr2mInt;
805  r->cfAdd = nr2mAdd;
806  r->cfSub = nr2mSub;
807  r->cfMult = nr2mMult;
808  r->cfDiv = nr2mDiv;
809  r->cfAnn = nr2mAnn;
810  r->cfIntMod = nr2mMod;
811  r->cfExactDiv = nr2mDiv;
812  r->cfInpNeg = nr2mNeg;
813  r->cfInvers = nr2mInvers;
814  r->cfDivBy = nr2mDivBy;
815  r->cfDivComp = nr2mDivComp;
816  r->cfGreater = nr2mGreater;
817  r->cfEqual = nr2mEqual;
818  r->cfIsZero = nr2mIsZero;
819  r->cfIsOne = nr2mIsOne;
820  r->cfIsMOne = nr2mIsMOne;
821  r->cfGreaterZero = nr2mGreaterZero;
822  r->cfWriteLong = nr2mWrite;
823  r->cfRead = nr2mRead;
824  r->cfPower = nr2mPower;
825  r->cfSetMap = nr2mSetMap;
826 // r->cfNormalize = ndNormalize; // default
827  r->cfLcm = nr2mLcm;
828  r->cfGcd = nr2mGcd;
829  r->cfIsUnit = nr2mIsUnit;
830  r->cfGetUnit = nr2mGetUnit;
831  r->cfExtGcd = nr2mExtGcd;
832  r->cfCoeffWrite = nr2mCoeffWrite;
833  r->cfCoeffName = nr2mCoeffName;
834  r->cfQuot1 = nr2mQuot1;
835 #ifdef LDEBUG
836  r->cfDBTest = nr2mDBTest;
837 #endif
838  r->has_simple_Alloc=TRUE;
839  return FALSE;
840 }
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
static BOOLEAN nr2mGreater(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:467
static char * nr2mCoeffName(const coeffs cf)
Definition: rmodulo2m.cc:62
static number nr2mLcm(number a, number b, const coeffs)
Definition: rmodulo2m.cc:157
static number nr2mAnn(number b, const coeffs r)
Definition: rmodulo2m.cc:576
static BOOLEAN nr2mDivBy(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:439
static void nr2mWrite(number a, const coeffs r)
Definition: rmodulo2m.cc:736
only used if HAVE_RINGS is defined
Definition: coeffs.h:47
#define FALSE
Definition: auxiliary.h:96
static long nr2mInt(number &n, const coeffs r)
Definition: rmodulo2m.cc:354
static number nr2mDiv(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:411
#define TRUE
Definition: auxiliary.h:100
static number nr2mGetUnit(number k, const coeffs)
Definition: rmodulo2m.cc:383
static BOOLEAN nr2mIsZero(number a, const coeffs)
Definition: rmodulo2m.cc:391
static BOOLEAN nr2mCoeffIsEqual(const coeffs r, n_coeffType n, void *p)
Definition: rmodulo2m.cc:77
static number nr2mNeg(number c, const coeffs r)
Definition: rmodulo2m.cc:597
static BOOLEAN nr2mIsOne(number a, const coeffs)
Definition: rmodulo2m.cc:396
#define LDEBUG
Definition: mod2.h:308
static const char * nr2mRead(const char *s, number *a, const coeffs r)
Definition: rmodulo2m.cc:761
#define assume(x)
Definition: mod2.h:390
BOOLEAN nr2mDBTest(number a, const char *f, const int l, const coeffs r)
Definition: rmodulo2m.cc:26
static coeffs nr2mQuot1(number c, const coeffs r)
Definition: rmodulo2m.cc:93
static char * nr2mCoeffString(const coeffs r)
Definition: rmodulo2m.cc:88
static int nr2mDivComp(number as, number bs, const coeffs)
Definition: rmodulo2m.cc:472
static void nr2mInitExp(int m, coeffs r)
Definition: rmodulo2m.cc:729
static BOOLEAN nr2mGreaterZero(number k, const coeffs r)
Definition: rmodulo2m.cc:132
static FORCE_INLINE n_coeffType getCoeffType(const coeffs r)
Returns the type of coeffs domain.
Definition: coeffs.h:421
static number nr2mMult(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:142
static number nr2mExtGcd(number a, number b, number *s, number *t, const coeffs r)
Definition: rmodulo2m.cc:293
static BOOLEAN nr2mIsMOne(number a, const coeffs r)
Definition: rmodulo2m.cc:401
static BOOLEAN nr2mEqual(number a, number b, const coeffs)
Definition: rmodulo2m.cc:406
static number nr2mInvers(number c, const coeffs r)
Definition: rmodulo2m.cc:279
static number nr2mSub(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:371
static BOOLEAN nr2mIsUnit(number a, const coeffs)
Definition: rmodulo2m.cc:378
EXTERN_VAR omBin gmp_nrz_bin
Definition: rmodulo2m.cc:60
static void nr2mCoeffWrite(const coeffs r, BOOLEAN)
Definition: rmodulo2m.cc:72
static number nr2mInit(long i, const coeffs r)
Definition: rmodulo2m.cc:337
(int), see modulop.h
Definition: coeffs.h:110
int p
Definition: cfModGcd.cc:4019
static number nr2mGcd(number a, number b, const coeffs)
Definition: rmodulo2m.cc:180
static number nr2mAdd(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:364
static void nr2mPower(number a, int i, number *result, const coeffs r)
Definition: rmodulo2m.cc:317
static nMapFunc nr2mSetMap(const coeffs src, const coeffs dst)
Definition: rmodulo2m.cc:664
static number nr2mMod(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:499

◆ nr2mInitExp()

static void nr2mInitExp ( int  m,
coeffs  r 
)
static

Definition at line 729 of file rmodulo2m.cc.

730 {
731  nr2mSetExp(m, r);
732  if (m < 2)
733  WarnS("nr2mInitExp unexpectedly called with m = 1 (we continue with Z/2^2");
734 }
static void nr2mSetExp(int m, coeffs r)
Definition: rmodulo2m.cc:711
#define WarnS
Definition: emacs.cc:78
int m
Definition: cfEzgcd.cc:121

◆ nr2mInt()

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

Definition at line 354 of file rmodulo2m.cc.

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

◆ nr2mInvers()

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

Definition at line 279 of file rmodulo2m.cc.

280 {
281  if ((unsigned long)c % 2 == 0)
282  {
283  WerrorS("division by zero divisor");
284  return (number)0;
285  }
286  return nr2mInversM(c, r);
287 }
void WerrorS(const char *s)
Definition: feFopen.cc:24
static number nr2mInversM(number c, const coeffs r)
Definition: rmodulo2m.cc:270

◆ nr2mInversM()

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

Definition at line 270 of file rmodulo2m.cc.

271 {
272  assume((unsigned long)c % 2 != 0);
273  // Table !!!
274  unsigned long inv;
275  inv = InvMod((unsigned long)c,r);
276  return (number)inv;
277 }
static unsigned long InvMod(unsigned long a, const coeffs r)
Definition: rmodulo2m.cc:262
#define assume(x)
Definition: mod2.h:390

◆ nr2mIsMOne()

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

Definition at line 401 of file rmodulo2m.cc.

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

◆ nr2mIsOne()

static BOOLEAN nr2mIsOne ( number  a,
const coeffs   
)
static

Definition at line 396 of file rmodulo2m.cc.

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

◆ nr2mIsUnit()

static BOOLEAN nr2mIsUnit ( number  a,
const coeffs   
)
static

Definition at line 378 of file rmodulo2m.cc.

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

◆ nr2mIsZero()

static BOOLEAN nr2mIsZero ( number  a,
const coeffs   
)
static

Definition at line 391 of file rmodulo2m.cc.

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

◆ nr2mLcm()

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

Definition at line 157 of file rmodulo2m.cc.

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

◆ nr2mMapGMP()

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

Definition at line 628 of file rmodulo2m.cc.

629 {
630  mpz_ptr erg = (mpz_ptr)omAllocBin(gmp_nrz_bin);
631  mpz_init(erg);
632  mpz_ptr k = (mpz_ptr)omAlloc(sizeof(mpz_t));
633  mpz_init_set_ui(k, dst->mod2mMask);
634 
635  mpz_and(erg, (mpz_ptr)from, k);
636  number res = (number) mpz_get_ui(erg);
637 
638  mpz_clear(erg); omFree((ADDRESS)erg);
639  mpz_clear(k); omFree((ADDRESS)k);
640 
641  return (number)res;
642 }
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
void * ADDRESS
Definition: auxiliary.h:135
int k
Definition: cfEzgcd.cc:92
#define omAlloc(size)
Definition: omAllocDecl.h:210
CanonicalForm res
Definition: facAbsFact.cc:64
#define omFree(addr)
Definition: omAllocDecl.h:261
EXTERN_VAR omBin gmp_nrz_bin
Definition: rmodulo2m.cc:60

◆ nr2mMapMachineInt()

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

Definition at line 605 of file rmodulo2m.cc.

606 {
607  unsigned long i = ((unsigned long)from) % (dst->mod2mMask + 1) ;
608  return (number)i;
609 }
int i
Definition: cfEzgcd.cc:125

◆ nr2mMapProject()

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

Definition at line 611 of file rmodulo2m.cc.

612 {
613  unsigned long i = ((unsigned long)from) % (dst->mod2mMask + 1);
614  return (number)i;
615 }
int i
Definition: cfEzgcd.cc:125

◆ nr2mMapQ()

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

Definition at line 644 of file rmodulo2m.cc.

645 {
646  mpz_ptr gmp = (mpz_ptr)omAllocBin(gmp_nrz_bin);
647  mpz_init(gmp);
648  nlGMP(from, gmp, src); // FIXME? TODO? // extern void nlGMP(number &i, number n, const coeffs r); // to be replaced with n_MPZ(erg, from, src); // ?
649  number res=nr2mMapGMP((number)gmp,src,dst);
650  mpz_clear(gmp); omFree((ADDRESS)gmp);
651  return res;
652 }
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
static number nr2mMapGMP(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:628
void * ADDRESS
Definition: auxiliary.h:135
CanonicalForm res
Definition: facAbsFact.cc:64
#define omFree(addr)
Definition: omAllocDecl.h:261
void nlGMP(number &i, mpz_t n, const coeffs r)
Definition: longrat.cc:1477
EXTERN_VAR omBin gmp_nrz_bin
Definition: rmodulo2m.cc:60

◆ nr2mMapZ()

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

Definition at line 654 of file rmodulo2m.cc.

655 {
656  if (SR_HDL(from) & SR_INT)
657  {
658  long f_i=SR_TO_INT(from);
659  return nr2mInit(f_i,dst);
660  }
661  return nr2mMapGMP(from,src,dst);
662 }
static number nr2mMapGMP(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:628
#define SR_TO_INT(SR)
Definition: longrat.h:68
#define SR_INT
Definition: longrat.h:66
static number nr2mInit(long i, const coeffs r)
Definition: rmodulo2m.cc:337
#define SR_HDL(A)
Definition: tgb.cc:35

◆ nr2mMapZp()

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

Definition at line 617 of file rmodulo2m.cc.

618 {
619  unsigned long j = (unsigned long)1;
620  long ii = (long)from;
621  if (ii < 0) { j = dst->mod2mMask; ii = -ii; }
622  unsigned long i = (unsigned long)ii;
623  i = i & dst->mod2mMask;
624  /* now we have: from = j * i mod 2^m */
625  return (number)nr2mMult((number)i, (number)j, dst);
626 }
int j
Definition: facHensel.cc:105
int i
Definition: cfEzgcd.cc:125
static number nr2mMult(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:142

◆ nr2mMod()

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

Definition at line 499 of file rmodulo2m.cc.

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

◆ nr2mMult()

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

Definition at line 142 of file rmodulo2m.cc.

143 {
144  number n;
145  if (((unsigned long)a == 0) || ((unsigned long)b == 0))
146  return (number)0;
147  else
148  n=nr2mMultM(a, b, r);
149  n_Test(n,r);
150  return n;
151 }
static number nr2mMultM(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:38
CanonicalForm b
Definition: cfModGcd.cc:4044
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:738

◆ 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 }
CanonicalForm b
Definition: cfModGcd.cc:4044

◆ nr2mNeg()

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

Definition at line 597 of file rmodulo2m.cc.

598 {
599  if ((unsigned long)c == 0) return c;
600  number n=nr2mNegM(c, r);
601  n_Test(n,r);
602  return n;
603 }
#define nr2mNegM(A, r)
Definition: rmodulo2m.cc:57
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:738

◆ nr2mPower()

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

Definition at line 317 of file rmodulo2m.cc.

318 {
319  if (i == 0)
320  {
321  *(unsigned long *)result = 1;
322  }
323  else if (i == 1)
324  {
325  *result = a;
326  }
327  else
328  {
329  nr2mPower(a, i-1, result, r);
330  *result = nr2mMultM(a, *result, r);
331  }
332 }
static number nr2mMultM(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:38
int i
Definition: cfEzgcd.cc:125
static void nr2mPower(number a, int i, number *result, const coeffs r)
Definition: rmodulo2m.cc:317
return result
Definition: facAbsBiFact.cc:76

◆ nr2mQuot1()

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

Definition at line 93 of file rmodulo2m.cc.

94 {
95  coeffs rr;
96  long ch = r->cfInt(c, r);
97  mpz_t a,b;
98  mpz_init_set(a, r->modNumber);
99  mpz_init_set_ui(b, ch);
100  mpz_ptr gcd;
101  gcd = (mpz_ptr) omAlloc(sizeof(mpz_t));
102  mpz_init(gcd);
103  mpz_gcd(gcd, a,b);
104  if(mpz_cmp_ui(gcd, 1) == 0)
105  {
106  WerrorS("constant in q-ideal is coprime to modulus in ground ring");
107  WerrorS("Unable to create qring!");
108  return NULL;
109  }
110  if(mpz_cmp_ui(gcd, 2) == 0)
111  {
112  rr = nInitChar(n_Zp, (void*)2);
113  }
114  else
115  {
116  int kNew = 1;
117  mpz_t baseTokNew;
118  mpz_init(baseTokNew);
119  mpz_set(baseTokNew, r->modBase);
120  while(mpz_cmp(gcd, baseTokNew) > 0)
121  {
122  kNew++;
123  mpz_mul(baseTokNew, baseTokNew, r->modBase);
124  }
125  mpz_clear(baseTokNew);
126  rr = nInitChar(n_Z2m, (void*)(long)kNew);
127  }
128  return(rr);
129 }
only used if HAVE_RINGS is defined
Definition: coeffs.h:47
{p < 2^31}
Definition: coeffs.h:30
void WerrorS(const char *s)
Definition: feFopen.cc:24
#define omAlloc(size)
Definition: omAllocDecl.h:210
CanonicalForm b
Definition: cfModGcd.cc:4044
The main handler for Singular numbers which are suitable for Singular polynomials.
#define NULL
Definition: omList.c:12
int gcd(int a, int b)
Definition: walkSupport.cc:836
coeffs nInitChar(n_coeffType t, void *parameter)
one-time initialisations for new coeffs in case of an error return NULL
Definition: numbers.cc:349

◆ nr2mRead()

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

Definition at line 761 of file rmodulo2m.cc.

762 {
763  int z;
764  int n=1;
765 
766  s = nr2mEati(s, &z,r);
767  if ((*s) == '/')
768  {
769  s++;
770  s = nr2mEati(s, &n,r);
771  }
772  if (n == 1)
773  *a = (number)(long)z;
774  else
775  *a = nr2mDiv((number)(long)z,(number)(long)n,r);
776  return s;
777 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
static number nr2mDiv(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:411
static const char * nr2mEati(const char *s, int *i, const coeffs r)
Definition: rmodulo2m.cc:742

◆ nr2mSetExp()

static void nr2mSetExp ( int  m,
coeffs  r 
)
static

Definition at line 711 of file rmodulo2m.cc.

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

◆ nr2mSetMap()

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

Definition at line 664 of file rmodulo2m.cc.

665 {
666  if ((src->rep==n_rep_int) && nCoeff_is_Ring_2toM(src)
667  && (src->mod2mMask == dst->mod2mMask))
668  {
669  return ndCopyMap;
670  }
671  if ((src->rep==n_rep_int) && nCoeff_is_Ring_2toM(src)
672  && (src->mod2mMask < dst->mod2mMask))
673  { /* i.e. map an integer mod 2^s into Z mod 2^t, where t < s */
674  return nr2mMapMachineInt;
675  }
676  if ((src->rep==n_rep_int) && nCoeff_is_Ring_2toM(src)
677  && (src->mod2mMask > dst->mod2mMask))
678  { /* i.e. map an integer mod 2^s into Z mod 2^t, where t > s */
679  // to be done
680  return nr2mMapProject;
681  }
682  if ((src->rep==n_rep_gmp) && nCoeff_is_Z(src))
683  {
684  return nr2mMapGMP;
685  }
686  if ((src->rep==n_rep_gap_gmp) /*&& nCoeff_is_Z(src)*/)
687  {
688  return nr2mMapZ;
689  }
690  if ((src->rep==n_rep_gap_rat) && (nCoeff_is_Q(src)||nCoeff_is_Z(src)))
691  {
692  return nr2mMapQ;
693  }
694  if ((src->rep==n_rep_int) && nCoeff_is_Zp(src) && (src->ch == 2))
695  {
696  return nr2mMapZp;
697  }
698  if ((src->rep==n_rep_gmp) &&
699  (nCoeff_is_Ring_PtoM(src) || nCoeff_is_Zn(src)))
700  {
701  if (mpz_divisible_2exp_p(src->modNumber,dst->modExponent))
702  return nr2mMapGMP;
703  }
704  return NULL; // default
705 }
static FORCE_INLINE BOOLEAN nCoeff_is_Zp(const coeffs r)
Definition: coeffs.h:822
number ndCopyMap(number a, const coeffs aRing, const coeffs r)
Definition: numbers.cc:251
static number nr2mMapGMP(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:628
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_2toM(const coeffs r)
Definition: coeffs.h:746
(), see rinteger.h, new impl.
Definition: coeffs.h:112
number nr2mMapZp(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:617
static number nr2mMapMachineInt(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:605
static FORCE_INLINE BOOLEAN nCoeff_is_Q(const coeffs r)
Definition: coeffs.h:828
static FORCE_INLINE BOOLEAN nCoeff_is_Z(const coeffs r)
Definition: coeffs.h:838
static number nr2mMapProject(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:611
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_PtoM(const coeffs r)
Definition: coeffs.h:749
(mpz_ptr), see rmodulon,h
Definition: coeffs.h:115
(number), see longrat.h
Definition: coeffs.h:111
#define NULL
Definition: omList.c:12
static number nr2mMapQ(number from, const coeffs src, const coeffs dst)
Definition: rmodulo2m.cc:644
(int), see modulop.h
Definition: coeffs.h:110
static number nr2mMapZ(number from, const coeffs src, const coeffs dst)
Definition: rmodulo2m.cc:654
static FORCE_INLINE BOOLEAN nCoeff_is_Zn(const coeffs r)
Definition: coeffs.h:848

◆ nr2mSub()

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

Definition at line 371 of file rmodulo2m.cc.

372 {
373  number n=nr2mSubM(a, b, r);
374  n_Test(n,r);
375  return n;
376 }
CanonicalForm b
Definition: cfModGcd.cc:4044
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:738
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 }
CanonicalForm b
Definition: cfModGcd.cc:4044

◆ nr2mWrite()

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

Definition at line 736 of file rmodulo2m.cc.

737 {
738  long i = nr2mInt(a, r);
739  StringAppend("%ld", i);
740 }
static long nr2mInt(number &n, const coeffs r)
Definition: rmodulo2m.cc:354
#define StringAppend
Definition: emacs.cc:79
int i
Definition: cfEzgcd.cc:125

◆ specialXGCD()

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

Definition at line 204 of file rmodulo2m.cc.

205 {
206  mpz_ptr u = (mpz_ptr)omAlloc(sizeof(mpz_t));
207  mpz_init_set_ui(u, a);
208  mpz_ptr u0 = (mpz_ptr)omAlloc(sizeof(mpz_t));
209  mpz_init(u0);
210  mpz_ptr u1 = (mpz_ptr)omAlloc(sizeof(mpz_t));
211  mpz_init_set_ui(u1, 1);
212  mpz_ptr u2 = (mpz_ptr)omAlloc(sizeof(mpz_t));
213  mpz_init(u2);
214  mpz_ptr v = (mpz_ptr)omAlloc(sizeof(mpz_t));
215  mpz_init_set_ui(v, r->mod2mMask);
216  mpz_add_ui(v, v, 1); /* now: v = 2^m */
217  mpz_ptr v0 = (mpz_ptr)omAlloc(sizeof(mpz_t));
218  mpz_init(v0);
219  mpz_ptr v1 = (mpz_ptr)omAlloc(sizeof(mpz_t));
220  mpz_init(v1);
221  mpz_ptr v2 = (mpz_ptr)omAlloc(sizeof(mpz_t));
222  mpz_init_set_ui(v2, 1);
223  mpz_ptr q = (mpz_ptr)omAlloc(sizeof(mpz_t));
224  mpz_init(q);
225  mpz_ptr rr = (mpz_ptr)omAlloc(sizeof(mpz_t));
226  mpz_init(rr);
227 
228  while (mpz_sgn1(v) != 0) /* i.e., while v != 0 */
229  {
230  mpz_div(q, u, v);
231  mpz_mod(rr, u, v);
232  mpz_set(u, v);
233  mpz_set(v, rr);
234  mpz_set(u0, u2);
235  mpz_set(v0, v2);
236  mpz_mul(u2, u2, q); mpz_sub(u2, u1, u2); /* u2 = u1 - q * u2 */
237  mpz_mul(v2, v2, q); mpz_sub(v2, v1, v2); /* v2 = v1 - q * v2 */
238  mpz_set(u1, u0);
239  mpz_set(v1, v0);
240  }
241 
242  while (mpz_sgn1(u1) < 0) /* i.e., while u1 < 0 */
243  {
244  /* we add 2^m = (2^m - 1) + 1 to u1: */
245  mpz_add_ui(u1, u1, r->mod2mMask);
246  mpz_add_ui(u1, u1, 1);
247  }
248  s = mpz_get_ui(u1); /* now: 0 <= s <= 2^m - 1 */
249 
250  mpz_clear(u); omFree((ADDRESS)u);
251  mpz_clear(u0); omFree((ADDRESS)u0);
252  mpz_clear(u1); omFree((ADDRESS)u1);
253  mpz_clear(u2); omFree((ADDRESS)u2);
254  mpz_clear(v); omFree((ADDRESS)v);
255  mpz_clear(v0); omFree((ADDRESS)v0);
256  mpz_clear(v1); omFree((ADDRESS)v1);
257  mpz_clear(v2); omFree((ADDRESS)v2);
258  mpz_clear(q); omFree((ADDRESS)q);
259  mpz_clear(rr); omFree((ADDRESS)rr);
260 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
#define mpz_sgn1(A)
Definition: si_gmp.h:13
void * ADDRESS
Definition: auxiliary.h:135
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omFree(addr)
Definition: omAllocDecl.h:261
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37

Variable Documentation

◆ gmp_nrz_bin

EXTERN_VAR omBin gmp_nrz_bin

Definition at line 60 of file rmodulo2m.cc.