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

Go to the source code of this file.

Macros

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

Functions

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

Variables

EXTERN_VAR omBin gmp_nrz_bin
 

Macro Definition Documentation

◆ nr2mEqualM

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

Definition at line 58 of file rmodulo2m.cc.

◆ nr2mNegM

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

Definition at line 57 of file rmodulo2m.cc.

Function Documentation

◆ InvMod()

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

Definition at line 252 of file rmodulo2m.cc.

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

◆ nr2mAdd()

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

Definition at line 354 of file rmodulo2m.cc.

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

◆ nr2mAddM()

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

Definition at line 44 of file rmodulo2m.cc.

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

◆ nr2mAnn()

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

Definition at line 571 of file rmodulo2m.cc.

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

◆ nr2mCoeffIsEqual()

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

Definition at line 72 of file rmodulo2m.cc.

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

◆ nr2mCoeffName()

static char * nr2mCoeffName ( const coeffs  cf)
static

Definition at line 62 of file rmodulo2m.cc.

63{
64 STATIC_VAR char n2mCoeffName_buf[30];
65 if (cf->modExponent>32) /* for 32/64bit arch.*/
66 snprintf(n2mCoeffName_buf,21,"ZZ/(bigint(2)^%lu)",cf->modExponent);
67 else
68 snprintf(n2mCoeffName_buf,21,"ZZ/(2^%lu)",cf->modExponent);
69 return n2mCoeffName_buf;
70}
CanonicalForm cf
Definition: cfModGcd.cc:4085
#define STATIC_VAR
Definition: globaldefs.h:7

◆ nr2mDBTest()

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

Definition at line 26 of file rmodulo2m.cc.

27{
28 if (((long)a<0L) || ((long)a>(long)r->mod2mMask))
29 {
30 Print("wrong mod 2^n number %ld at %s,%d\n",(long)a,f,l);
31 return FALSE;
32 }
33 return TRUE;
34}
int l
Definition: cfEzgcd.cc:100
f
Definition: cfModGcd.cc:4083
#define Print
Definition: emacs.cc:80

◆ nr2mDiv()

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

Definition at line 401 of file rmodulo2m.cc.

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

◆ nr2mDivBy()

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

Definition at line 434 of file rmodulo2m.cc.

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

◆ nr2mDivComp()

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

Definition at line 467 of file rmodulo2m.cc.

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

◆ nr2mEati()

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

Definition at line 731 of file rmodulo2m.cc.

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

◆ nr2mEqual()

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

Definition at line 396 of file rmodulo2m.cc.

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

◆ nr2mExtGcd()

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

Definition at line 283 of file rmodulo2m.cc.

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

◆ nr2mGcd()

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

Definition at line 170 of file rmodulo2m.cc.

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

◆ nr2mGetUnit()

static number nr2mGetUnit ( number  k,
const  coeffs 
)
static

Definition at line 373 of file rmodulo2m.cc.

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

◆ nr2mGreater()

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

Definition at line 462 of file rmodulo2m.cc.

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

◆ nr2mGreaterZero()

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

Definition at line 122 of file rmodulo2m.cc.

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

◆ nr2mInit()

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

Definition at line 327 of file rmodulo2m.cc.

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

◆ nr2mInitChar()

BOOLEAN nr2mInitChar ( coeffs  r,
void *  p 
)

Definition at line 769 of file rmodulo2m.cc.

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

◆ nr2mInitExp()

static void nr2mInitExp ( int  m,
coeffs  r 
)
static

Definition at line 718 of file rmodulo2m.cc.

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

◆ nr2mInt()

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

Definition at line 344 of file rmodulo2m.cc.

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

◆ nr2mInvers()

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

Definition at line 269 of file rmodulo2m.cc.

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

◆ nr2mInversM()

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

Definition at line 260 of file rmodulo2m.cc.

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

◆ nr2mIsMOne()

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

Definition at line 391 of file rmodulo2m.cc.

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

◆ nr2mIsOne()

static BOOLEAN nr2mIsOne ( number  a,
const  coeffs 
)
static

Definition at line 386 of file rmodulo2m.cc.

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

◆ nr2mIsUnit()

static BOOLEAN nr2mIsUnit ( number  a,
const  coeffs 
)
static

Definition at line 368 of file rmodulo2m.cc.

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

◆ nr2mIsZero()

static BOOLEAN nr2mIsZero ( number  a,
const  coeffs 
)
static

Definition at line 381 of file rmodulo2m.cc.

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

◆ nr2mLcm()

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

Definition at line 147 of file rmodulo2m.cc.

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

◆ nr2mMapGMP()

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

Definition at line 623 of file rmodulo2m.cc.

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

◆ nr2mMapMachineInt()

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

Definition at line 600 of file rmodulo2m.cc.

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

◆ nr2mMapProject()

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

Definition at line 606 of file rmodulo2m.cc.

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

◆ nr2mMapQ()

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

Definition at line 639 of file rmodulo2m.cc.

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

◆ nr2mMapZ()

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

Definition at line 648 of file rmodulo2m.cc.

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

◆ nr2mMapZp()

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

Definition at line 612 of file rmodulo2m.cc.

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

◆ nr2mMod()

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

Definition at line 494 of file rmodulo2m.cc.

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

◆ nr2mMult()

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

Definition at line 132 of file rmodulo2m.cc.

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

◆ nr2mMultM()

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

Definition at line 38 of file rmodulo2m.cc.

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

◆ nr2mNeg()

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

Definition at line 592 of file rmodulo2m.cc.

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

◆ nr2mPower()

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

Definition at line 307 of file rmodulo2m.cc.

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

◆ nr2mQuot1()

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

Definition at line 83 of file rmodulo2m.cc.

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

◆ nr2mRead()

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

Definition at line 750 of file rmodulo2m.cc.

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

◆ nr2mSetExp()

static void nr2mSetExp ( int  m,
coeffs  r 
)
static

Definition at line 700 of file rmodulo2m.cc.

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

◆ nr2mSetMap()

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

Definition at line 658 of file rmodulo2m.cc.

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

◆ nr2mSub()

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

Definition at line 361 of file rmodulo2m.cc.

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

◆ nr2mSubM()

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

Definition at line 50 of file rmodulo2m.cc.

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

◆ nr2mWrite()

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

Definition at line 725 of file rmodulo2m.cc.

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

◆ specialXGCD()

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

Definition at line 194 of file rmodulo2m.cc.

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

Variable Documentation

◆ gmp_nrz_bin

EXTERN_VAR omBin gmp_nrz_bin

Definition at line 60 of file rmodulo2m.cc.