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

Go to the source code of this file.

Macros

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

Functions

number nr2mCopy (number a, const coeffs r)
 
BOOLEAN nr2mGreaterZero (number k, const coeffs r)
 
number nr2mMult (number a, number b, const coeffs r)
 
number nr2mInit (long i, const coeffs r)
 
long nr2mInt (number &n, const coeffs r)
 
number nr2mAdd (number a, number b, const coeffs r)
 
number nr2mSub (number a, number b, const coeffs r)
 
void nr2mPower (number a, int i, number *result, const coeffs r)
 
BOOLEAN nr2mIsZero (number a, const coeffs r)
 
BOOLEAN nr2mIsOne (number a, const coeffs r)
 
BOOLEAN nr2mIsMOne (number a, const coeffs r)
 
BOOLEAN nr2mIsUnit (number a, const coeffs r)
 
number nr2mGetUnit (number a, const coeffs r)
 
number nr2mDiv (number a, number b, const coeffs r)
 
number nr2mIntDiv (number a, number b, const coeffs r)
 
number nr2mMod (number a, number b, const coeffs r)
 
number nr2mNeg (number c, const coeffs r)
 
number nr2mInvers (number c, const coeffs r)
 
BOOLEAN nr2mGreater (number a, number b, const coeffs r)
 
BOOLEAN nr2mDivBy (number a, number b, const coeffs r)
 
int nr2mDivComp (number a, number b, const coeffs r)
 
BOOLEAN nr2mEqual (number a, number b, const coeffs r)
 
number nr2mLcm (number a, number b, const coeffs r)
 
number nr2mGcd (number a, number b, const coeffs r)
 
number nr2mExtGcd (number a, number b, number *s, number *t, const coeffs r)
 
nMapFunc nr2mSetMap (const coeffs src, const coeffs dst)
 
void nr2mWrite (number a, const coeffs r)
 
const char * nr2mRead (const char *s, number *a, const coeffs r)
 
char * nr2mName (number n, const coeffs r)
 
void nr2mCoeffWrite (const coeffs r, BOOLEAN details)
 
coeffs nr2mQuot1 (number c, const coeffs r)
 
BOOLEAN nr2mDBTest (number a, const char *f, const int l, const coeffs r)
 
void nr2mSetExp (int c, const coeffs r)
 
void nr2mInitExp (int c, const coeffs r)
 
number nr2mMapQ (number from, const coeffs src, const coeffs dst)
 
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)
 
BOOLEAN nr2mCoeffIsEqual (const coeffs r, n_coeffType n, void *p)
 
static char * nr2mCoeffString (const coeffs r)
 
static number nr2mAnn (number b, const coeffs r)
 
BOOLEAN nr2mInitChar (coeffs r, void *p)
 
void specialXGCD (unsigned long &s, unsigned long a, const coeffs r)
 
unsigned long InvMod (unsigned long a, const coeffs r)
 
number nr2mInversM (number c, const coeffs r)
 
number nr2mMapMachineInt (number from, const coeffs, const coeffs dst)
 
number nr2mMapProject (number from, const coeffs, const coeffs dst)
 
number nr2mMapZp (number from, const coeffs, const coeffs dst)
 
number nr2mMapGMP (number from, const coeffs, const coeffs dst)
 
number nr2mMapZ (number from, const coeffs src, const coeffs dst)
 
static const char * nr2mEati (const char *s, int *i, const coeffs r)
 

Variables

omBin gmp_nrz_bin
 

Macro Definition Documentation

§ nr2mEqualM

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

Definition at line 86 of file rmodulo2m.cc.

§ nr2mNegM

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

Definition at line 85 of file rmodulo2m.cc.

Function Documentation

§ InvMod()

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

Definition at line 531 of file rmodulo2m.cc.

532 {
533  assume((unsigned long)a % 2 != 0);
534  unsigned long s;
535  specialXGCD(s, a, r);
536  return s;
537 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
const poly a
Definition: syzextra.cc:212
#define assume(x)
Definition: mod2.h:403
void specialXGCD(unsigned long &s, unsigned long a, const coeffs r)
Definition: rmodulo2m.cc:473

§ nr2mAdd()

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

Definition at line 355 of file rmodulo2m.cc.

356 {
357  return nr2mAddM(a, b, r);
358 }
const poly a
Definition: syzextra.cc:212
static number nr2mAddM(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:72
const poly b
Definition: syzextra.cc:213

§ nr2mAddM()

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

Definition at line 72 of file rmodulo2m.cc.

73 {
74  return (number)
75  ((((unsigned long) a) + ((unsigned long) b)) & ((unsigned long)r->mod2mMask));
76 }
const poly a
Definition: syzextra.cc:212
const poly b
Definition: syzextra.cc:213

§ nr2mAnn()

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

Definition at line 646 of file rmodulo2m.cc.

647 {
648  if ((unsigned long)b == 0)
649  return NULL;
650  if ((unsigned long)b == 1)
651  return NULL;
652  unsigned long c = r->mod2mMask + 1;
653  if (c != 0) /* i.e., if no overflow */
654  return (number)(c / (unsigned long)b);
655  else
656  {
657  /* overflow: c = 2^32 resp. 2^64, depending on platform */
658  mpz_ptr cc = (mpz_ptr)omAlloc(sizeof(mpz_t));
659  mpz_init_set_ui(cc, r->mod2mMask); mpz_add_ui(cc, cc, 1);
660  mpz_div_ui(cc, cc, (unsigned long)(unsigned long)b);
661  unsigned long s = mpz_get_ui(cc);
662  mpz_clear(cc); omFree((ADDRESS)cc);
663  return (number)(unsigned long)s;
664  }
665 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
void * ADDRESS
Definition: auxiliary.h:118
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omFree(addr)
Definition: omAllocDecl.h:261
#define NULL
Definition: omList.c:10
const poly b
Definition: syzextra.cc:213

§ nr2mCoeffIsEqual()

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

Definition at line 96 of file rmodulo2m.cc.

97 {
98  if (n==n_Z2m)
99  {
100  int m=(int)(long)(p);
101  unsigned long mm=r->mod2mMask;
102  if (((mm+1)>>m)==1L) return TRUE;
103  }
104  return FALSE;
105 }
only used if HAVE_RINGS is defined
Definition: coeffs.h:46
#define FALSE
Definition: auxiliary.h:97
return P p
Definition: myNF.cc:203
#define TRUE
Definition: auxiliary.h:101
int m
Definition: cfEzgcd.cc:119

§ nr2mCoeffString()

static char* nr2mCoeffString ( const coeffs  r)
static

Definition at line 107 of file rmodulo2m.cc.

108 {
109  // r->modExponent <=bitsize(long)
110  char* s = (char*) omAlloc(11+11);
111 #ifdef SINGULAR_4_1
112  sprintf(s,"ZZ/(2^%lu)",r->modExponent);
113 #else
114  sprintf(s,"integer,2,%lu",r->modExponent);
115 #endif
116  return s;
117 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
#define omAlloc(size)
Definition: omAllocDecl.h:210

§ nr2mCoeffWrite()

void nr2mCoeffWrite ( const coeffs  r,
BOOLEAN  details 
)

Definition at line 90 of file rmodulo2m.cc.

91 {
92  PrintS("// coeff. ring is : ");
93  Print("Z/2^%lu\n", r->modExponent);
94 }
#define Print
Definition: emacs.cc:83
void PrintS(const char *s)
Definition: reporter.cc:284

§ nr2mCopy()

number nr2mCopy ( number  a,
const coeffs  r 
)

§ nr2mDBTest()

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

Definition at line 815 of file rmodulo2m.cc.

816 {
817  //if ((unsigned long)a < 0) return FALSE; // is unsigned!
818  if (((unsigned long)a & r->mod2mMask) != (unsigned long)a) return FALSE;
819  return TRUE;
820 }
const poly a
Definition: syzextra.cc:212
#define FALSE
Definition: auxiliary.h:97
#define TRUE
Definition: auxiliary.h:101

§ nr2mDiv()

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

Definition at line 549 of file rmodulo2m.cc.

550 {
551  if ((unsigned long)a == 0) return (number)0;
552  else if ((unsigned long)b % 2 == 0)
553  {
554  if ((unsigned long)b != 0)
555  {
556  while (((unsigned long)b % 2 == 0) && ((unsigned long)a % 2 == 0))
557  {
558  a = (number)((unsigned long)a / 2);
559  b = (number)((unsigned long)b / 2);
560  }
561  }
562  if ((unsigned long)b % 2 == 0)
563  {
564  WerrorS("Division not possible, even by cancelling zero divisors.");
565  WerrorS("Result is integer division without remainder.");
566  return (number) ((unsigned long) a / (unsigned long) b);
567  }
568  }
569  return (number)nr2mMult(a, nr2mInversM(b,r),r);
570 }
const poly a
Definition: syzextra.cc:212
number nr2mMult(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:226
void WerrorS(const char *s)
Definition: feFopen.cc:24
number nr2mInversM(number c, const coeffs r)
Definition: rmodulo2m.cc:540
const poly b
Definition: syzextra.cc:213

§ nr2mDivBy()

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

Definition at line 406 of file rmodulo2m.cc.

407 {
408  if (a == NULL)
409  {
410  unsigned long c = r->mod2mMask + 1;
411  if (c != 0) /* i.e., if no overflow */
412  return (c % (unsigned long)b) == 0;
413  else
414  {
415  /* overflow: we need to check whether b
416  is zero or a power of 2: */
417  c = (unsigned long)b;
418  while (c != 0)
419  {
420  if ((c % 2) != 0) return FALSE;
421  c = c >> 1;
422  }
423  return TRUE;
424  }
425  }
426  else
427  {
428  number n = nr2mGcd(a, b, r);
429  n = nr2mDiv(b, n, r);
430  return nr2mIsUnit(n, r);
431  }
432 }
number nr2mGcd(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:260
const poly a
Definition: syzextra.cc:212
#define FALSE
Definition: auxiliary.h:97
#define TRUE
Definition: auxiliary.h:101
number nr2mDiv(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:549
#define NULL
Definition: omList.c:10
BOOLEAN nr2mIsUnit(number a, const coeffs r)
Definition: rmodulo2m.cc:365
const poly b
Definition: syzextra.cc:213

§ nr2mDivComp()

int nr2mDivComp ( number  a,
number  b,
const coeffs  r 
)

Definition at line 434 of file rmodulo2m.cc.

435 {
436  unsigned long a = (unsigned long)as;
437  unsigned long b = (unsigned long)bs;
438  assume(a != 0 && b != 0);
439  while (a % 2 == 0 && b % 2 == 0)
440  {
441  a = a / 2;
442  b = b / 2;
443  }
444  if (a % 2 == 0)
445  {
446  return -1;
447  }
448  else
449  {
450  if (b % 2 == 1)
451  {
452  return 2;
453  }
454  else
455  {
456  return 1;
457  }
458  }
459 }
const poly a
Definition: syzextra.cc:212
#define assume(x)
Definition: mod2.h:403
const poly b
Definition: syzextra.cc:213

§ nr2mEati()

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

Definition at line 829 of file rmodulo2m.cc.

830 {
831 
832  if (((*s) >= '0') && ((*s) <= '9'))
833  {
834  (*i) = 0;
835  do
836  {
837  (*i) *= 10;
838  (*i) += *s++ - '0';
839  if ((*i) >= (MAX_INT_VAL / 10)) (*i) = (*i) & r->mod2mMask;
840  }
841  while (((*s) >= '0') && ((*s) <= '9'));
842  (*i) = (*i) & r->mod2mMask;
843  }
844  else (*i) = 1;
845  return s;
846 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
const int MAX_INT_VAL
Definition: mylimits.h:12
int i
Definition: cfEzgcd.cc:123

§ nr2mEqual()

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

Definition at line 393 of file rmodulo2m.cc.

394 {
395  return (a == b);
396 }
const poly a
Definition: syzextra.cc:212
const poly b
Definition: syzextra.cc:213

§ nr2mExtGcd()

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

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 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
const poly a
Definition: syzextra.cc:212
number nr2mInvers(number c, const coeffs r)
Definition: rmodulo2m.cc:667
poly res
Definition: myNF.cc:322
#define NULL
Definition: omList.c:10
const poly b
Definition: syzextra.cc:213

§ nr2mGcd()

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

Definition at line 260 of file rmodulo2m.cc.

261 {
262  unsigned long res = 0;
263  if ((unsigned long)a == 0 && (unsigned long)b == 0) return (number)1;
264  while ((unsigned long)a % 2 == 0 && (unsigned long)b % 2 == 0)
265  {
266  a = (number)((unsigned long)a / 2);
267  b = (number)((unsigned long)b / 2);
268  res++;
269  }
270 // if ((unsigned long)b % 2 == 0)
271 // {
272 // return (number)((1L << res)); // * (unsigned long) a); // (2**res)*a a is a unit
273 // }
274 // else
275 // {
276  return (number)((1L << res)); // * (unsigned long) b); // (2**res)*b b is a unit
277 // }
278 }
const poly a
Definition: syzextra.cc:212
poly res
Definition: myNF.cc:322
const poly b
Definition: syzextra.cc:213

§ nr2mGetUnit()

number nr2mGetUnit ( number  a,
const coeffs  r 
)

Definition at line 370 of file rmodulo2m.cc.

371 {
372  if (k == NULL) return (number)1;
373  unsigned long erg = (unsigned long)k;
374  while (erg % 2 == 0) erg = erg / 2;
375  return (number)erg;
376 }
int k
Definition: cfEzgcd.cc:93
#define NULL
Definition: omList.c:10

§ nr2mGreater()

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

Definition at line 398 of file rmodulo2m.cc.

399 {
400  return nr2mDivBy(a, b,r);
401 }
const poly a
Definition: syzextra.cc:212
BOOLEAN nr2mDivBy(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:406
const poly b
Definition: syzextra.cc:213

§ nr2mGreaterZero()

BOOLEAN nr2mGreaterZero ( number  k,
const coeffs  r 
)

Definition at line 462 of file rmodulo2m.cc.

463 {
464  if ((unsigned long)k == 0) return FALSE;
465  if ((unsigned long)k > ((r->mod2mMask >> 1) + 1)) return FALSE;
466  return TRUE;
467 }
#define FALSE
Definition: auxiliary.h:97
#define TRUE
Definition: auxiliary.h:101
int k
Definition: cfEzgcd.cc:93

§ nr2mInit()

number nr2mInit ( long  i,
const coeffs  r 
)

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 }
number nr2mMult(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:226
int k
Definition: cfEzgcd.cc:93
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123

§ nr2mInitChar()

BOOLEAN nr2mInitChar ( coeffs  r,
void *  p 
)

Definition at line 162 of file rmodulo2m.cc.

163 {
164  assume( getCoeffType(r) == n_Z2m );
165  nr2mInitExp((int)(long)(p), r);
166 
167  r->is_field=FALSE;
168  r->is_domain=FALSE;
169  r->rep=n_rep_int;
170 
171  //r->cfKillChar = ndKillChar; /* dummy*/
172  r->nCoeffIsEqual = nr2mCoeffIsEqual;
173  r->cfCoeffString = nr2mCoeffString;
174 
175  r->modBase = (mpz_ptr) omAllocBin (gmp_nrz_bin);
176  mpz_init_set_si (r->modBase, 2L);
177  r->modNumber= (mpz_ptr) omAllocBin (gmp_nrz_bin);
178  mpz_init (r->modNumber);
179  mpz_pow_ui (r->modNumber, r->modBase, r->modExponent);
180 
181  /* next cast may yield an overflow as mod2mMask is an unsigned long */
182  r->ch = (int)r->mod2mMask + 1;
183 
184  r->cfInit = nr2mInit;
185  //r->cfCopy = ndCopy;
186  r->cfInt = nr2mInt;
187  r->cfAdd = nr2mAdd;
188  r->cfSub = nr2mSub;
189  r->cfMult = nr2mMult;
190  r->cfDiv = nr2mDiv;
191  r->cfAnn = nr2mAnn;
192  r->cfIntMod = nr2mMod;
193  r->cfExactDiv = nr2mDiv;
194  r->cfInpNeg = nr2mNeg;
195  r->cfInvers = nr2mInvers;
196  r->cfDivBy = nr2mDivBy;
197  r->cfDivComp = nr2mDivComp;
198  r->cfGreater = nr2mGreater;
199  r->cfEqual = nr2mEqual;
200  r->cfIsZero = nr2mIsZero;
201  r->cfIsOne = nr2mIsOne;
202  r->cfIsMOne = nr2mIsMOne;
203  r->cfGreaterZero = nr2mGreaterZero;
204  r->cfWriteLong = nr2mWrite;
205  r->cfRead = nr2mRead;
206  r->cfPower = nr2mPower;
207  r->cfSetMap = nr2mSetMap;
208 // r->cfNormalize = ndNormalize; // default
209  r->cfLcm = nr2mLcm;
210  r->cfGcd = nr2mGcd;
211  r->cfIsUnit = nr2mIsUnit;
212  r->cfGetUnit = nr2mGetUnit;
213  r->cfExtGcd = nr2mExtGcd;
214  r->cfCoeffWrite = nr2mCoeffWrite;
215  r->cfQuot1 = nr2mQuot1;
216 #ifdef LDEBUG
217  r->cfDBTest = nr2mDBTest;
218 #endif
219  r->has_simple_Alloc=TRUE;
220  return FALSE;
221 }
void nr2mInitExp(int c, const coeffs r)
Definition: rmodulo2m.cc:807
number nr2mGcd(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:260
long nr2mInt(number &n, const coeffs r)
Definition: rmodulo2m.cc:345
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
number nr2mLcm(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:237
nMapFunc nr2mSetMap(const coeffs src, const coeffs dst)
Definition: rmodulo2m.cc:742
number nr2mInit(long i, const coeffs r)
Definition: rmodulo2m.cc:328
number nr2mAdd(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:355
number nr2mSub(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:360
static number nr2mAnn(number b, const coeffs r)
Definition: rmodulo2m.cc:646
number nr2mMult(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:226
const char * nr2mRead(const char *s, number *a, const coeffs r)
Definition: rmodulo2m.cc:848
only used if HAVE_RINGS is defined
Definition: coeffs.h:46
#define FALSE
Definition: auxiliary.h:97
return P p
Definition: myNF.cc:203
BOOLEAN nr2mGreaterZero(number k, const coeffs r)
Definition: rmodulo2m.cc:462
number nr2mGetUnit(number a, const coeffs r)
Definition: rmodulo2m.cc:370
#define TRUE
Definition: auxiliary.h:101
number nr2mMod(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:572
BOOLEAN nr2mIsMOne(number a, const coeffs r)
Definition: rmodulo2m.cc:388
number nr2mDiv(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:549
BOOLEAN nr2mGreater(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:398
void nr2mWrite(number a, const coeffs r)
Definition: rmodulo2m.cc:823
coeffs nr2mQuot1(number c, const coeffs r)
Definition: rmodulo2m.cc:119
number nr2mInvers(number c, const coeffs r)
Definition: rmodulo2m.cc:667
number nr2mNeg(number c, const coeffs r)
Definition: rmodulo2m.cc:677
#define LDEBUG
Definition: mod2.h:321
int nr2mDivComp(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:434
#define assume(x)
Definition: mod2.h:403
BOOLEAN nr2mDBTest(number a, const char *f, const int l, const coeffs r)
Definition: rmodulo2m.cc:815
static char * nr2mCoeffString(const coeffs r)
Definition: rmodulo2m.cc:107
static FORCE_INLINE n_coeffType getCoeffType(const coeffs r)
Returns the type of coeffs domain.
Definition: coeffs.h:425
BOOLEAN nr2mDivBy(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:406
BOOLEAN nr2mIsUnit(number a, const coeffs r)
Definition: rmodulo2m.cc:365
BOOLEAN nr2mIsZero(number a, const coeffs r)
Definition: rmodulo2m.cc:378
number nr2mExtGcd(number a, number b, number *s, number *t, const coeffs r)
Definition: rmodulo2m.cc:284
void nr2mCoeffWrite(const coeffs r, BOOLEAN details)
Definition: rmodulo2m.cc:90
omBin gmp_nrz_bin
Definition: rintegers.cc:76
(int), see modulop.h
Definition: coeffs.h:110
BOOLEAN nr2mEqual(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:393
BOOLEAN nr2mIsOne(number a, const coeffs r)
Definition: rmodulo2m.cc:383
void nr2mPower(number a, int i, number *result, const coeffs r)
Definition: rmodulo2m.cc:308
BOOLEAN nr2mCoeffIsEqual(const coeffs r, n_coeffType n, void *p)
Definition: rmodulo2m.cc:96

§ nr2mInitExp()

void nr2mInitExp ( int  c,
const coeffs  r 
)

Definition at line 807 of file rmodulo2m.cc.

808 {
809  nr2mSetExp(m, r);
810  if (m < 2)
811  WarnS("nr2mInitExp unexpectedly called with m = 1 (we continue with Z/2^2");
812 }
#define WarnS
Definition: emacs.cc:81
int m
Definition: cfEzgcd.cc:119
void nr2mSetExp(int c, const coeffs r)
Definition: rmodulo2m.cc:789

§ nr2mInt()

long nr2mInt ( number &  n,
const coeffs  r 
)

Definition at line 345 of file rmodulo2m.cc.

346 {
347  unsigned long nn = (unsigned long)(unsigned long)n & r->mod2mMask;
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 }
int l
Definition: cfEzgcd.cc:94

§ nr2mIntDiv()

number nr2mIntDiv ( number  a,
number  b,
const coeffs  r 
)

Definition at line 616 of file rmodulo2m.cc.

617 {
618  if ((unsigned long)a == 0)
619  {
620  if ((unsigned long)b == 0)
621  return (number)1;
622  if ((unsigned long)b == 1)
623  return (number)0;
624  unsigned long c = r->mod2mMask + 1;
625  if (c != 0) /* i.e., if no overflow */
626  return (number)(c / (unsigned long)b);
627  else
628  {
629  /* overflow: c = 2^32 resp. 2^64, depending on platform */
630  mpz_ptr cc = (mpz_ptr)omAlloc(sizeof(mpz_t));
631  mpz_init_set_ui(cc, r->mod2mMask); mpz_add_ui(cc, cc, 1);
632  mpz_div_ui(cc, cc, (unsigned long)(unsigned long)b);
633  unsigned long s = mpz_get_ui(cc);
634  mpz_clear(cc); omFree((ADDRESS)cc);
635  return (number)(unsigned long)s;
636  }
637  }
638  else
639  {
640  if ((unsigned long)b == 0)
641  return (number)0;
642  return (number)((unsigned long) a / (unsigned long) b);
643  }
644 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
const poly a
Definition: syzextra.cc:212
void * ADDRESS
Definition: auxiliary.h:118
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omFree(addr)
Definition: omAllocDecl.h:261
const poly b
Definition: syzextra.cc:213

§ nr2mInvers()

number nr2mInvers ( number  c,
const coeffs  r 
)

Definition at line 667 of file rmodulo2m.cc.

668 {
669  if ((unsigned long)c % 2 == 0)
670  {
671  WerrorS("division by zero divisor");
672  return (number)0;
673  }
674  return nr2mInversM(c, r);
675 }
void WerrorS(const char *s)
Definition: feFopen.cc:24
number nr2mInversM(number c, const coeffs r)
Definition: rmodulo2m.cc:540

§ nr2mInversM()

number nr2mInversM ( number  c,
const coeffs  r 
)
inline

Definition at line 540 of file rmodulo2m.cc.

541 {
542  assume((unsigned long)c % 2 != 0);
543  // Table !!!
544  unsigned long inv;
545  inv = InvMod((unsigned long)c,r);
546  return (number)inv;
547 }
#define assume(x)
Definition: mod2.h:403
unsigned long InvMod(unsigned long a, const coeffs r)
Definition: rmodulo2m.cc:531

§ nr2mIsMOne()

BOOLEAN nr2mIsMOne ( number  a,
const coeffs  r 
)

Definition at line 388 of file rmodulo2m.cc.

389 {
390  return ((r->mod2mMask == (unsigned long)a) &&(1L!=(long)a))/*for char 2^1*/;
391 }
const poly a
Definition: syzextra.cc:212

§ nr2mIsOne()

BOOLEAN nr2mIsOne ( number  a,
const coeffs  r 
)

Definition at line 383 of file rmodulo2m.cc.

384 {
385  return 1 == (unsigned long)a;
386 }
const poly a
Definition: syzextra.cc:212

§ nr2mIsUnit()

BOOLEAN nr2mIsUnit ( number  a,
const coeffs  r 
)

Definition at line 365 of file rmodulo2m.cc.

366 {
367  return ((unsigned long)a % 2 == 1);
368 }
const poly a
Definition: syzextra.cc:212

§ nr2mIsZero()

BOOLEAN nr2mIsZero ( number  a,
const coeffs  r 
)

Definition at line 378 of file rmodulo2m.cc.

379 {
380  return 0 == (unsigned long)a;
381 }
const poly a
Definition: syzextra.cc:212

§ nr2mLcm()

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

Definition at line 237 of file rmodulo2m.cc.

238 {
239  unsigned long res = 0;
240  if ((unsigned long)a == 0) a = (number) 1;
241  if ((unsigned long)b == 0) b = (number) 1;
242  while ((unsigned long)a % 2 == 0)
243  {
244  a = (number)((unsigned long)a / 2);
245  if ((unsigned long)b % 2 == 0) b = (number)((unsigned long)b / 2);
246  res++;
247  }
248  while ((unsigned long)b % 2 == 0)
249  {
250  b = (number)((unsigned long)b / 2);
251  res++;
252  }
253  return (number)(1L << res); // (2**res)
254 }
const poly a
Definition: syzextra.cc:212
poly res
Definition: myNF.cc:322
const poly b
Definition: syzextra.cc:213

§ nr2mMapGMP()

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

Definition at line 706 of file rmodulo2m.cc.

707 {
708  mpz_ptr erg = (mpz_ptr)omAllocBin(gmp_nrz_bin);
709  mpz_init(erg);
710  mpz_ptr k = (mpz_ptr)omAlloc(sizeof(mpz_t));
711  mpz_init_set_ui(k, dst->mod2mMask);
712 
713  mpz_and(erg, (mpz_ptr)from, k);
714  number res = (number) mpz_get_ui(erg);
715 
716  mpz_clear(erg); omFree((ADDRESS)erg);
717  mpz_clear(k); omFree((ADDRESS)k);
718 
719  return (number)res;
720 }
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
void * ADDRESS
Definition: auxiliary.h:118
int k
Definition: cfEzgcd.cc:93
#define omAlloc(size)
Definition: omAllocDecl.h:210
poly res
Definition: myNF.cc:322
#define omFree(addr)
Definition: omAllocDecl.h:261
omBin gmp_nrz_bin
Definition: rintegers.cc:76

§ nr2mMapMachineInt()

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

Definition at line 683 of file rmodulo2m.cc.

684 {
685  unsigned long i = ((unsigned long)from) % dst->mod2mMask ;
686  return (number)i;
687 }
int i
Definition: cfEzgcd.cc:123

§ nr2mMapProject()

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

Definition at line 689 of file rmodulo2m.cc.

690 {
691  unsigned long i = ((unsigned long)from) % (dst->mod2mMask + 1);
692  return (number)i;
693 }
int i
Definition: cfEzgcd.cc:123

§ nr2mMapQ()

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

Definition at line 722 of file rmodulo2m.cc.

723 {
724  mpz_ptr gmp = (mpz_ptr)omAllocBin(gmp_nrz_bin);
725  mpz_init(gmp);
726  nlGMP(from, (number)gmp, src); // FIXME? TODO? // extern void nlGMP(number &i, number n, const coeffs r); // to be replaced with n_MPZ(erg, from, src); // ?
727  number res=nr2mMapGMP((number)gmp,src,dst);
728  mpz_clear(gmp); omFree((ADDRESS)gmp);
729  return res;
730 }
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
void * ADDRESS
Definition: auxiliary.h:118
void nlGMP(number &i, number n, const coeffs r)
Definition: longrat.cc:1465
poly res
Definition: myNF.cc:322
#define omFree(addr)
Definition: omAllocDecl.h:261
number nr2mMapGMP(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:706
omBin gmp_nrz_bin
Definition: rintegers.cc:76

§ nr2mMapZ()

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

Definition at line 732 of file rmodulo2m.cc.

733 {
734  if (SR_HDL(from) & SR_INT)
735  {
736  long f_i=SR_TO_INT(from);
737  return nr2mInit(f_i,dst);
738  }
739  return nr2mMapGMP(from,src,dst);
740 }
number nr2mInit(long i, const coeffs r)
Definition: rmodulo2m.cc:328
#define SR_TO_INT(SR)
Definition: longrat.h:70
#define SR_INT
Definition: longrat.h:68
number nr2mMapGMP(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:706
#define SR_HDL(A)
Definition: tgb.cc:35

§ nr2mMapZp()

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

Definition at line 695 of file rmodulo2m.cc.

696 {
697  unsigned long j = (unsigned long)1;
698  long ii = (long)from;
699  if (ii < 0) { j = dst->mod2mMask; ii = -ii; }
700  unsigned long i = (unsigned long)ii;
701  i = i & dst->mod2mMask;
702  /* now we have: from = j * i mod 2^m */
703  return (number)nr2mMult((number)i, (number)j, dst);
704 }
number nr2mMult(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:226
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123

§ nr2mMod()

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

Definition at line 572 of file rmodulo2m.cc.

573 {
574  /*
575  We need to return the number rr which is uniquely determined by the
576  following two properties:
577  (1) 0 <= rr < |b| (with respect to '<' and '<=' performed in Z x Z)
578  (2) There exists some k in the integers Z such that a = k * b + rr.
579  Consider g := gcd(2^m, |b|). Note that then |b|/g is a unit in Z/2^m.
580  Now, there are three cases:
581  (a) g = 1
582  Then |b| is a unit in Z/2^m, i.e. |b| (and also b) divides a.
583  Thus rr = 0.
584  (b) g <> 1 and g divides a
585  Then a = (a/g) * (|b|/g)^(-1) * b (up to sign), i.e. again rr = 0.
586  (c) g <> 1 and g does not divide a
587  Let's denote the division with remainder of a by g as follows:
588  a = s * g + t. Then t = a - s * g = a - s * (|b|/g)^(-1) * |b|
589  fulfills (1) and (2), i.e. rr := t is the correct result. Hence
590  in this third case, rr is the remainder of division of a by g in Z.
591  This algorithm is the same as for the case Z/n, except that we may
592  compute the gcd of |b| and 2^m "by hand": We just extract the highest
593  power of 2 (<= 2^m) that is contained in b.
594  */
595  assume((unsigned long) b != 0);
596  unsigned long g = 1;
597  unsigned long b_div = (unsigned long) b;
598 
599  /*
600  * b_div is unsigned, so that (b_div < 0) evaluates false at compile-time
601  *
602  if (b_div < 0) b_div = -b_div; // b_div now represents |b|, BUT b_div is unsigned!
603  */
604 
605  unsigned long rr = 0;
606  while ((g < r->mod2mMask ) && (b_div > 0) && (b_div % 2 == 0))
607  {
608  b_div = b_div >> 1;
609  g = g << 1;
610  } // g is now the gcd of 2^m and |b|
611 
612  if (g != 1) rr = (unsigned long)a % g;
613  return (number)rr;
614 }
const poly a
Definition: syzextra.cc:212
g
Definition: cfModGcd.cc:4031
#define assume(x)
Definition: mod2.h:403
const poly b
Definition: syzextra.cc:213

§ nr2mMult()

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

Definition at line 226 of file rmodulo2m.cc.

227 {
228  if (((unsigned long)a == 0) || ((unsigned long)b == 0))
229  return (number)0;
230  else
231  return nr2mMultM(a, b, r);
232 }
static number nr2mMultM(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:66
const poly a
Definition: syzextra.cc:212
const poly b
Definition: syzextra.cc:213

§ nr2mMultM()

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

Definition at line 66 of file rmodulo2m.cc.

67 {
68  return (number)
69  ((((unsigned long) a) * ((unsigned long) b)) & ((unsigned long)r->mod2mMask));
70 }
const poly a
Definition: syzextra.cc:212
const poly b
Definition: syzextra.cc:213

§ nr2mName()

char* nr2mName ( number  n,
const coeffs  r 
)

§ nr2mNeg()

number nr2mNeg ( number  c,
const coeffs  r 
)

Definition at line 677 of file rmodulo2m.cc.

678 {
679  if ((unsigned long)c == 0) return c;
680  return nr2mNegM(c, r);
681 }
#define nr2mNegM(A, r)
Definition: rmodulo2m.cc:85

§ nr2mPower()

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

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 }
static number nr2mMultM(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:66
const poly a
Definition: syzextra.cc:212
int i
Definition: cfEzgcd.cc:123
void nr2mPower(number a, int i, number *result, const coeffs r)
Definition: rmodulo2m.cc:308
return result
Definition: facAbsBiFact.cc:76

§ nr2mQuot1()

coeffs nr2mQuot1 ( number  c,
const coeffs  r 
)

Definition at line 119 of file rmodulo2m.cc.

120 {
121  coeffs rr;
122  long ch = r->cfInt(c, r);
123  mpz_t a,b;
124  mpz_init_set(a, r->modNumber);
125  mpz_init_set_ui(b, ch);
126  mpz_ptr gcd;
127  gcd = (mpz_ptr) omAlloc(sizeof(mpz_t));
128  mpz_init(gcd);
129  mpz_gcd(gcd, a,b);
130  if(mpz_cmp_ui(gcd, 1) == 0)
131  {
132  WerrorS("constant in q-ideal is coprime to modulus in ground ring");
133  WerrorS("Unable to create qring!");
134  return NULL;
135  }
136  if(mpz_cmp_ui(gcd, 2) == 0)
137  {
138  rr = nInitChar(n_Zp, (void*)2);
139  }
140  else
141  {
142  ZnmInfo info;
143  info.base = r->modBase;
144  int kNew = 1;
145  mpz_t baseTokNew;
146  mpz_init(baseTokNew);
147  mpz_set(baseTokNew, r->modBase);
148  while(mpz_cmp(gcd, baseTokNew) > 0)
149  {
150  kNew++;
151  mpz_mul(baseTokNew, baseTokNew, r->modBase);
152  }
153  info.exp = kNew;
154  mpz_clear(baseTokNew);
155  rr = nInitChar(n_Z2m, (void*)(long)kNew);
156  }
157  return(rr);
158 }
mpz_ptr base
Definition: rmodulon.h:19
const poly a
Definition: syzextra.cc:212
only used if HAVE_RINGS is defined
Definition: coeffs.h:46
{p < 2^31}
Definition: coeffs.h:30
void WerrorS(const char *s)
Definition: feFopen.cc:24
#define omAlloc(size)
Definition: omAllocDecl.h:210
The main handler for Singular numbers which are suitable for Singular polynomials.
const ExtensionInfo & info
< [in] sqrfree poly
unsigned long exp
Definition: rmodulon.h:19
#define NULL
Definition: omList.c:10
int gcd(int a, int b)
Definition: walkSupport.cc:839
const poly b
Definition: syzextra.cc:213
coeffs nInitChar(n_coeffType t, void *parameter)
one-time initialisations for new coeffs in case of an error return NULL
Definition: numbers.cc:329

§ nr2mRead()

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

Definition at line 848 of file rmodulo2m.cc.

849 {
850  int z;
851  int n=1;
852 
853  s = nr2mEati(s, &z,r);
854  if ((*s) == '/')
855  {
856  s++;
857  s = nr2mEati(s, &n,r);
858  }
859  if (n == 1)
860  *a = (number)(long)z;
861  else
862  *a = nr2mDiv((number)(long)z,(number)(long)n,r);
863  return s;
864 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
const poly a
Definition: syzextra.cc:212
number nr2mDiv(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:549
static const char * nr2mEati(const char *s, int *i, const coeffs r)
Definition: rmodulo2m.cc:829

§ nr2mSetExp()

void nr2mSetExp ( int  c,
const coeffs  r 
)

Definition at line 789 of file rmodulo2m.cc.

790 {
791  if (m > 1)
792  {
793  /* we want mod2mMask to be the bit pattern
794  '111..1' consisting of m one's: */
795  r->modExponent= m;
796  r->mod2mMask = 1;
797  for (int i = 1; i < m; i++) r->mod2mMask = (r->mod2mMask << 1) + 1;
798  }
799  else
800  {
801  r->modExponent= 2;
802  /* code unexpectedly called with m = 1; we continue with m = 2: */
803  r->mod2mMask = 3; /* i.e., '11' in binary representation */
804  }
805 }
int m
Definition: cfEzgcd.cc:119
int i
Definition: cfEzgcd.cc:123

§ nr2mSetMap()

nMapFunc nr2mSetMap ( const coeffs  src,
const coeffs  dst 
)

Definition at line 742 of file rmodulo2m.cc.

743 {
744  if ((src->rep==n_rep_int) && nCoeff_is_Ring_2toM(src)
745  && (src->mod2mMask == dst->mod2mMask))
746  {
747  return ndCopyMap;
748  }
749  if ((src->rep==n_rep_int) && nCoeff_is_Ring_2toM(src)
750  && (src->mod2mMask < dst->mod2mMask))
751  { /* i.e. map an integer mod 2^s into Z mod 2^t, where t < s */
752  return nr2mMapMachineInt;
753  }
754  if ((src->rep==n_rep_int) && nCoeff_is_Ring_2toM(src)
755  && (src->mod2mMask > dst->mod2mMask))
756  { /* i.e. map an integer mod 2^s into Z mod 2^t, where t > s */
757  // to be done
758  return nr2mMapProject;
759  }
760  if ((src->rep==n_rep_gmp) && nCoeff_is_Ring_Z(src))
761  {
762  return nr2mMapGMP;
763  }
764  if ((src->rep==n_rep_gap_gmp) /*&& nCoeff_is_Ring_Z(src)*/)
765  {
766  return nr2mMapZ;
767  }
768  if ((src->rep==n_rep_gap_rat) && (nCoeff_is_Q(src)||nCoeff_is_Ring_Z(src)))
769  {
770  return nr2mMapQ;
771  }
772  if ((src->rep==n_rep_int) && nCoeff_is_Zp(src) && (src->ch == 2))
773  {
774  return nr2mMapZp;
775  }
776  if ((src->rep==n_rep_gmp) &&
778  {
779  if (mpz_divisible_2exp_p(src->modNumber,dst->modExponent))
780  return nr2mMapGMP;
781  }
782  return NULL; // default
783 }
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_ModN(const coeffs r)
Definition: coeffs.h:753
number nr2mMapZ(number from, const coeffs src, const coeffs dst)
Definition: rmodulo2m.cc:732
static FORCE_INLINE BOOLEAN nCoeff_is_Zp(const coeffs r)
Definition: coeffs.h:834
number ndCopyMap(number a, const coeffs aRing, const coeffs r)
Definition: numbers.cc:239
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_Z(const coeffs r)
Definition: coeffs.h:759
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_2toM(const coeffs r)
Definition: coeffs.h:750
(), see rinteger.h, new impl.
Definition: coeffs.h:112
number nr2mMapZp(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:695
static FORCE_INLINE BOOLEAN nCoeff_is_Q(const coeffs r)
Definition: coeffs.h:840
number nr2mMapMachineInt(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:683
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_PtoM(const coeffs r)
Definition: coeffs.h:756
number nr2mMapProject(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:689
(mpz_ptr), see rmodulon,h
Definition: coeffs.h:115
(number), see longrat.h
Definition: coeffs.h:111
#define NULL
Definition: omList.c:10
number nr2mMapGMP(number from, const coeffs, const coeffs dst)
Definition: rmodulo2m.cc:706
number nr2mMapQ(number from, const coeffs src, const coeffs dst)
Definition: rmodulo2m.cc:722
(int), see modulop.h
Definition: coeffs.h:110

§ nr2mSub()

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

Definition at line 360 of file rmodulo2m.cc.

361 {
362  return nr2mSubM(a, b, r);
363 }
const poly a
Definition: syzextra.cc:212
static number nr2mSubM(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:78
const poly b
Definition: syzextra.cc:213

§ nr2mSubM()

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

Definition at line 78 of file rmodulo2m.cc.

79 {
80  return (number)((unsigned long)a < (unsigned long)b ?
81  r->mod2mMask - (unsigned long)b + (unsigned long)a + 1:
82  (unsigned long)a - (unsigned long)b);
83 }
const poly a
Definition: syzextra.cc:212
const poly b
Definition: syzextra.cc:213

§ nr2mWrite()

void nr2mWrite ( number  a,
const coeffs  r 
)

Definition at line 823 of file rmodulo2m.cc.

824 {
825  long i = nr2mInt(a, r);
826  StringAppend("%ld", i);
827 }
long nr2mInt(number &n, const coeffs r)
Definition: rmodulo2m.cc:345
const poly a
Definition: syzextra.cc:212
#define StringAppend
Definition: emacs.cc:82
int i
Definition: cfEzgcd.cc:123

§ specialXGCD()

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

Definition at line 473 of file rmodulo2m.cc.

474 {
475  mpz_ptr u = (mpz_ptr)omAlloc(sizeof(mpz_t));
476  mpz_init_set_ui(u, a);
477  mpz_ptr u0 = (mpz_ptr)omAlloc(sizeof(mpz_t));
478  mpz_init(u0);
479  mpz_ptr u1 = (mpz_ptr)omAlloc(sizeof(mpz_t));
480  mpz_init_set_ui(u1, 1);
481  mpz_ptr u2 = (mpz_ptr)omAlloc(sizeof(mpz_t));
482  mpz_init(u2);
483  mpz_ptr v = (mpz_ptr)omAlloc(sizeof(mpz_t));
484  mpz_init_set_ui(v, r->mod2mMask);
485  mpz_add_ui(v, v, 1); /* now: v = 2^m */
486  mpz_ptr v0 = (mpz_ptr)omAlloc(sizeof(mpz_t));
487  mpz_init(v0);
488  mpz_ptr v1 = (mpz_ptr)omAlloc(sizeof(mpz_t));
489  mpz_init(v1);
490  mpz_ptr v2 = (mpz_ptr)omAlloc(sizeof(mpz_t));
491  mpz_init_set_ui(v2, 1);
492  mpz_ptr q = (mpz_ptr)omAlloc(sizeof(mpz_t));
493  mpz_init(q);
494  mpz_ptr rr = (mpz_ptr)omAlloc(sizeof(mpz_t));
495  mpz_init(rr);
496 
497  while (mpz_cmp_ui(v, 0) != 0) /* i.e., while v != 0 */
498  {
499  mpz_div(q, u, v);
500  mpz_mod(rr, u, v);
501  mpz_set(u, v);
502  mpz_set(v, rr);
503  mpz_set(u0, u2);
504  mpz_set(v0, v2);
505  mpz_mul(u2, u2, q); mpz_sub(u2, u1, u2); /* u2 = u1 - q * u2 */
506  mpz_mul(v2, v2, q); mpz_sub(v2, v1, v2); /* v2 = v1 - q * v2 */
507  mpz_set(u1, u0);
508  mpz_set(v1, v0);
509  }
510 
511  while (mpz_cmp_ui(u1, 0) < 0) /* i.e., while u1 < 0 */
512  {
513  /* we add 2^m = (2^m - 1) + 1 to u1: */
514  mpz_add_ui(u1, u1, r->mod2mMask);
515  mpz_add_ui(u1, u1, 1);
516  }
517  s = mpz_get_ui(u1); /* now: 0 <= s <= 2^m - 1 */
518 
519  mpz_clear(u); omFree((ADDRESS)u);
520  mpz_clear(u0); omFree((ADDRESS)u0);
521  mpz_clear(u1); omFree((ADDRESS)u1);
522  mpz_clear(u2); omFree((ADDRESS)u2);
523  mpz_clear(v); omFree((ADDRESS)v);
524  mpz_clear(v0); omFree((ADDRESS)v0);
525  mpz_clear(v1); omFree((ADDRESS)v1);
526  mpz_clear(v2); omFree((ADDRESS)v2);
527  mpz_clear(q); omFree((ADDRESS)q);
528  mpz_clear(rr); omFree((ADDRESS)rr);
529 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
const poly a
Definition: syzextra.cc:212
void * ADDRESS
Definition: auxiliary.h:118
#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

omBin gmp_nrz_bin

Definition at line 76 of file rintegers.cc.