My Project
Loading...
Searching...
No Matches
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)
 
#define nr2mEqualM(A, B)
 

Functions

static BOOLEAN nr2mDBTest (number a, const char *f, const int l, const coeffs r)
 
static number nr2mMultM (number a, number b, const coeffs r)
 
static void nr2mInpMultM (number &a, number b, const coeffs r)
 
static number nr2mAddM (number a, number b, const coeffs r)
 
static void nr2mInpAddM (number &a, number b, const coeffs r)
 
static number nr2mSubM (number a, number b, const coeffs r)
 
static char * nr2mCoeffName (const coeffs cf)
 
static BOOLEAN nr2mCoeffIsEqual (const coeffs r, n_coeffType n, void *p)
 
static coeffs nr2mQuot1 (number c, const coeffs r)
 
static BOOLEAN nr2mGreaterZero (number k, const coeffs r)
 
static number nr2mMult (number a, number b, const coeffs r)
 
static void nr2mInpMult (number &a, number b, const coeffs r)
 
static number nr2mAnn (number b, const coeffs r)
 
static number nr2mLcm (number a, number b, const coeffs)
 
static number nr2mGcd (number a, number b, const coeffs)
 
static void specialXGCD (unsigned long &s, unsigned long a, const coeffs r)
 
static unsigned long InvMod (unsigned long a, const coeffs r)
 
static number nr2mInversM (number c, const coeffs r)
 
static number nr2mInvers (number c, const coeffs r)
 
static number nr2mExtGcd (number a, number b, number *s, number *t, const coeffs r)
 
static void nr2mPower (number a, int i, number *result, const coeffs r)
 
static number nr2mInit (long i, const coeffs r)
 
static long nr2mInt (number &n, const coeffs r)
 
static number nr2mAdd (number a, number b, const coeffs r)
 
static void nr2mInpAdd (number &a, number b, const coeffs r)
 
static number nr2mSub (number a, number b, const coeffs r)
 
static BOOLEAN nr2mIsUnit (number a, const coeffs)
 
static number nr2mGetUnit (number k, const coeffs)
 
static BOOLEAN nr2mIsZero (number a, const coeffs)
 
static BOOLEAN nr2mIsOne (number a, const coeffs)
 
static BOOLEAN nr2mIsMOne (number a, const coeffs r)
 
static BOOLEAN nr2mEqual (number a, number b, const coeffs)
 
static number nr2mDiv (number a, number b, const coeffs r)
 
static BOOLEAN nr2mDivBy (number a, number b, const coeffs r)
 
static BOOLEAN nr2mGreater (number as, number bs, 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 )
Value:
((A)==(B))
b *CanonicalForm B
Definition facBivar.cc:52
#define A
Definition sirandom.c:24

Definition at line 69 of file rmodulo2m.cc.

◆ nr2mNegM

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

Definition at line 68 of file rmodulo2m.cc.

Function Documentation

◆ InvMod()

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

Definition at line 272 of file rmodulo2m.cc.

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

◆ nr2mAdd()

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

Definition at line 374 of file rmodulo2m.cc.

375{
376 number n=nr2mAddM(a, b, r);
377 n_Test(n,r);
378 return n;
379}
CanonicalForm b
Definition cfModGcd.cc:4111
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition coeffs.h:713
static number nr2mAddM(number a, number b, const coeffs r)
Definition rmodulo2m.cc:49

◆ nr2mAddM()

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

Definition at line 49 of file rmodulo2m.cc.

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

◆ nr2mAnn()

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

Definition at line 599 of file rmodulo2m.cc.

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

◆ nr2mCoeffIsEqual()

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

Definition at line 83 of file rmodulo2m.cc.

84{
85 if (n==n_Z2m)
86 {
87 int m=(int)(long)(p);
88 unsigned long mm=r->mod2mMask;
89 if (((mm+1)>>m)==1L) return TRUE;
90 }
91 return FALSE;
92}
#define TRUE
Definition auxiliary.h:101
#define FALSE
Definition auxiliary.h:97
int m
Definition cfEzgcd.cc:128
int p
Definition cfModGcd.cc:4086
@ n_Z2m
only used if HAVE_RINGS is defined
Definition coeffs.h:46

◆ nr2mCoeffName()

static char * nr2mCoeffName ( const coeffs cf)
static

Definition at line 73 of file rmodulo2m.cc.

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

◆ nr2mDBTest()

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

Definition at line 24 of file rmodulo2m.cc.

25{
26 if ((((long)a<0L) || ((long)a>(long)r->mod2mMask))
27 && (r->mod2mMask!= ~0UL))
28 {
29 Print("wrong mod 2^n number %ld (m:%ld) at %s,%d\n",(long)a,(long)r->mod2mMask,f,l);
30 return FALSE;
31 }
32 return TRUE;
33}
int l
Definition cfEzgcd.cc:100
FILE * f
Definition checklibs.c:9
#define Print
Definition emacs.cc:80

◆ nr2mDiv()

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

Definition at line 427 of file rmodulo2m.cc.

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

◆ nr2mDivBy()

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

Definition at line 460 of file rmodulo2m.cc.

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

◆ nr2mDivComp()

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

Definition at line 495 of file rmodulo2m.cc.

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

◆ nr2mEati()

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

Definition at line 759 of file rmodulo2m.cc.

760{
761
762 if (((*s) >= '0') && ((*s) <= '9'))
763 {
764 (*i) = 0;
765 do
766 {
767 (*i) *= 10;
768 (*i) += *s++ - '0';
769 if ((*i) >= (MAX_INT_VAL / 10)) (*i) = (*i) & r->mod2mMask;
770 }
771 while (((*s) >= '0') && ((*s) <= '9'));
772 (*i) = (*i) & r->mod2mMask;
773 }
774 else (*i) = 1;
775 return s;
776}
int i
Definition cfEzgcd.cc:132
const int MAX_INT_VAL
Definition mylimits.h:12

◆ nr2mEqual()

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

Definition at line 422 of file rmodulo2m.cc.

423{
424 return (a == b);
425}

◆ nr2mExtGcd()

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

Definition at line 303 of file rmodulo2m.cc.

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

◆ nr2mGcd()

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

Definition at line 190 of file rmodulo2m.cc.

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

◆ nr2mGetUnit()

static number nr2mGetUnit ( number k,
const coeffs  )
static

Definition at line 399 of file rmodulo2m.cc.

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

◆ nr2mGreater()

static BOOLEAN nr2mGreater ( number as,
number bs,
const coeffs r )
static

Definition at line 488 of file rmodulo2m.cc.

489{
490 unsigned long a = (unsigned long)as;
491 unsigned long b = (unsigned long)bs;
492 return (a > b);
493}

◆ nr2mGreaterZero()

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

Definition at line 133 of file rmodulo2m.cc.

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

◆ nr2mInit()

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

Definition at line 347 of file rmodulo2m.cc.

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

◆ nr2mInitChar()

BOOLEAN nr2mInitChar ( coeffs r,
void * p )

Definition at line 797 of file rmodulo2m.cc.

798{
799 assume( getCoeffType(r) == n_Z2m );
800 nr2mInitExp((int)(long)(p), r);
801
802 r->is_field=FALSE;
803 r->is_domain=FALSE;
804 r->rep=n_rep_int;
805
806 //r->cfKillChar = ndKillChar; /* dummy*/
807 r->nCoeffIsEqual = nr2mCoeffIsEqual;
808
809 r->modBase = (mpz_ptr) omAllocBin (gmp_nrz_bin);
810 mpz_init_set_si (r->modBase, 2L);
811 r->modNumber= (mpz_ptr) omAllocBin (gmp_nrz_bin);
812 mpz_init (r->modNumber);
813 mpz_pow_ui (r->modNumber, r->modBase, r->modExponent);
814
815 /* next cast may yield an overflow as mod2mMask is an unsigned long */
816 r->ch = (int)r->mod2mMask + 1;
817
818 r->cfInit = nr2mInit;
819 //r->cfCopy = ndCopy;
820 r->cfInt = nr2mInt;
821 r->cfAdd = nr2mAdd;
822 r->cfInpAdd = nr2mInpAdd;
823 r->cfSub = nr2mSub;
824 r->cfMult = nr2mMult;
825 r->cfInpMult = nr2mInpMult;
826 r->cfDiv = nr2mDiv;
827 r->cfAnn = nr2mAnn;
828 r->cfIntMod = nr2mMod;
829 r->cfExactDiv = nr2mDiv;
830 r->cfInpNeg = nr2mNeg;
831 r->cfInvers = nr2mInvers;
832 r->cfDivBy = nr2mDivBy;
833 r->cfDivComp = nr2mDivComp;
834 r->cfGreater = nr2mGreater;
835 r->cfEqual = nr2mEqual;
836 r->cfIsZero = nr2mIsZero;
837 r->cfIsOne = nr2mIsOne;
838 r->cfIsMOne = nr2mIsMOne;
839 r->cfGreaterZero = nr2mGreaterZero;
840 r->cfWriteLong = nr2mWrite;
841 r->cfRead = nr2mRead;
842 r->cfPower = nr2mPower;
843 r->cfSetMap = nr2mSetMap;
844// r->cfNormalize = ndNormalize; // default
845 r->cfLcm = nr2mLcm;
846 r->cfGcd = nr2mGcd;
847 r->cfIsUnit = nr2mIsUnit;
848 r->cfGetUnit = nr2mGetUnit;
849 r->cfExtGcd = nr2mExtGcd;
850 r->cfCoeffName = nr2mCoeffName;
851 r->cfQuot1 = nr2mQuot1;
852#ifdef LDEBUG
853 r->cfDBTest = nr2mDBTest;
854#endif
855 r->has_simple_Alloc=TRUE;
856 return FALSE;
857}
static FORCE_INLINE n_coeffType getCoeffType(const coeffs r)
Returns the type of coeffs domain.
Definition coeffs.h:429
@ n_rep_int
(int), see modulop.h
Definition coeffs.h:117
#define omAllocBin(bin)
VAR omBin gmp_nrz_bin
Definition rintegers.cc:23
static nMapFunc nr2mSetMap(const coeffs src, const coeffs dst)
Definition rmodulo2m.cc:686
static void nr2mWrite(number a, const coeffs r)
Definition rmodulo2m.cc:753
static BOOLEAN nr2mGreater(number as, number bs, const coeffs r)
Definition rmodulo2m.cc:488
static void nr2mInpAdd(number &a, number b, const coeffs r)
Definition rmodulo2m.cc:381
static number nr2mSub(number a, number b, const coeffs r)
Definition rmodulo2m.cc:387
static number nr2mLcm(number a, number b, const coeffs)
Definition rmodulo2m.cc:167
static BOOLEAN nr2mIsOne(number a, const coeffs)
Definition rmodulo2m.cc:412
static number nr2mAnn(number b, const coeffs r)
Definition rmodulo2m.cc:599
static number nr2mInit(long i, const coeffs r)
Definition rmodulo2m.cc:347
static number nr2mExtGcd(number a, number b, number *s, number *t, const coeffs r)
Definition rmodulo2m.cc:303
static number nr2mGetUnit(number k, const coeffs)
Definition rmodulo2m.cc:399
static void nr2mInitExp(int m, coeffs r)
Definition rmodulo2m.cc:746
static void nr2mPower(number a, int i, number *result, const coeffs r)
Definition rmodulo2m.cc:327
static int nr2mDivComp(number as, number bs, const coeffs)
Definition rmodulo2m.cc:495
static long nr2mInt(number &n, const coeffs r)
Definition rmodulo2m.cc:364
static BOOLEAN nr2mDivBy(number a, number b, const coeffs r)
Definition rmodulo2m.cc:460
static BOOLEAN nr2mGreaterZero(number k, const coeffs r)
Definition rmodulo2m.cc:133
static number nr2mNeg(number c, const coeffs r)
Definition rmodulo2m.cc:620
static BOOLEAN nr2mDBTest(number a, const char *f, const int l, const coeffs r)
Definition rmodulo2m.cc:24
static number nr2mMod(number a, number b, const coeffs r)
Definition rmodulo2m.cc:522
static BOOLEAN nr2mCoeffIsEqual(const coeffs r, n_coeffType n, void *p)
Definition rmodulo2m.cc:83
static number nr2mAdd(number a, number b, const coeffs r)
Definition rmodulo2m.cc:374
static void nr2mInpMult(number &a, number b, const coeffs r)
Definition rmodulo2m.cc:154
static char * nr2mCoeffName(const coeffs cf)
Definition rmodulo2m.cc:73
static BOOLEAN nr2mEqual(number a, number b, const coeffs)
Definition rmodulo2m.cc:422
static BOOLEAN nr2mIsZero(number a, const coeffs)
Definition rmodulo2m.cc:407
static const char * nr2mRead(const char *s, number *a, const coeffs r)
Definition rmodulo2m.cc:778
static BOOLEAN nr2mIsMOne(number a, const coeffs r)
Definition rmodulo2m.cc:417
static coeffs nr2mQuot1(number c, const coeffs r)
Definition rmodulo2m.cc:94

◆ nr2mInitExp()

static void nr2mInitExp ( int m,
coeffs r )
static

Definition at line 746 of file rmodulo2m.cc.

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

◆ nr2mInpAdd()

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

Definition at line 381 of file rmodulo2m.cc.

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

◆ nr2mInpAddM()

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

Definition at line 55 of file rmodulo2m.cc.

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

◆ nr2mInpMult()

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

Definition at line 154 of file rmodulo2m.cc.

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

◆ nr2mInpMultM()

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

Definition at line 43 of file rmodulo2m.cc.

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

◆ nr2mInt()

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

Definition at line 364 of file rmodulo2m.cc.

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

◆ nr2mInvers()

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

Definition at line 289 of file rmodulo2m.cc.

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

◆ nr2mInversM()

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

Definition at line 280 of file rmodulo2m.cc.

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

◆ nr2mIsMOne()

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

Definition at line 417 of file rmodulo2m.cc.

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

◆ nr2mIsOne()

static BOOLEAN nr2mIsOne ( number a,
const coeffs  )
static

Definition at line 412 of file rmodulo2m.cc.

413{
414 return 1 == (unsigned long)a;
415}

◆ nr2mIsUnit()

static BOOLEAN nr2mIsUnit ( number a,
const coeffs  )
static

Definition at line 394 of file rmodulo2m.cc.

395{
396 return ((unsigned long)a % 2 == 1);
397}

◆ nr2mIsZero()

static BOOLEAN nr2mIsZero ( number a,
const coeffs  )
static

Definition at line 407 of file rmodulo2m.cc.

408{
409 return 0 == (unsigned long)a;
410}

◆ nr2mLcm()

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

Definition at line 167 of file rmodulo2m.cc.

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

◆ nr2mMapGMP()

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

Definition at line 651 of file rmodulo2m.cc.

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

◆ nr2mMapMachineInt()

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

Definition at line 628 of file rmodulo2m.cc.

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

◆ nr2mMapProject()

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

Definition at line 634 of file rmodulo2m.cc.

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

◆ nr2mMapQ()

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

Definition at line 667 of file rmodulo2m.cc.

668{
669 mpz_ptr gmp = (mpz_ptr)omAllocBin(gmp_nrz_bin);
670 nlMPZ(gmp, from, src);
671 number res=nr2mMapGMP((number)gmp,src,dst);
672 mpz_clear(gmp); omFreeBinAddr((ADDRESS)gmp);
673 return res;
674}
void nlMPZ(mpz_t m, number &n, const coeffs r)
Definition longrat.cc:2811
static number nr2mMapGMP(number from, const coeffs, const coeffs dst)
Definition rmodulo2m.cc:651

◆ nr2mMapZ()

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

Definition at line 676 of file rmodulo2m.cc.

677{
678 if (SR_HDL(from) & SR_INT)
679 {
680 long f_i=SR_TO_INT(from);
681 return nr2mInit(f_i,dst);
682 }
683 return nr2mMapGMP(from,src,dst);
684}
#define SR_INT
Definition longrat.h:67
#define SR_TO_INT(SR)
Definition longrat.h:69
#define SR_HDL(A)
Definition tgb.cc:35

◆ nr2mMapZp()

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

Definition at line 640 of file rmodulo2m.cc.

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

◆ nr2mMod()

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

Definition at line 522 of file rmodulo2m.cc.

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

◆ nr2mMult()

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

Definition at line 143 of file rmodulo2m.cc.

144{
145 number n;
146 if (((unsigned long)a == 0) || ((unsigned long)b == 0))
147 return (number)0;
148 else
149 n=nr2mMultM(a, b, r);
150 n_Test(n,r);
151 return n;
152}
static number nr2mMultM(number a, number b, const coeffs r)
Definition rmodulo2m.cc:37

◆ nr2mMultM()

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

Definition at line 37 of file rmodulo2m.cc.

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

◆ nr2mNeg()

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

Definition at line 620 of file rmodulo2m.cc.

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

◆ nr2mPower()

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

Definition at line 327 of file rmodulo2m.cc.

328{
329 if (i == 0)
330 {
331 *(unsigned long *)result = 1;
332 }
333 else if (i == 1)
334 {
335 *result = a;
336 }
337 else
338 {
339 nr2mPower(a, i-1, result, r);
340 *result = nr2mMultM(a, *result, r);
341 }
342}
return result

◆ nr2mQuot1()

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

Definition at line 94 of file rmodulo2m.cc.

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

◆ nr2mRead()

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

Definition at line 778 of file rmodulo2m.cc.

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

◆ nr2mSetExp()

static void nr2mSetExp ( int m,
coeffs r )
static

Definition at line 728 of file rmodulo2m.cc.

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

◆ nr2mSetMap()

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

Definition at line 686 of file rmodulo2m.cc.

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

◆ nr2mSub()

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

Definition at line 387 of file rmodulo2m.cc.

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

◆ nr2mSubM()

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

Definition at line 61 of file rmodulo2m.cc.

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

◆ nr2mWrite()

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

Definition at line 753 of file rmodulo2m.cc.

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

◆ specialXGCD()

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

Definition at line 214 of file rmodulo2m.cc.

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

Variable Documentation

◆ gmp_nrz_bin

EXTERN_VAR omBin gmp_nrz_bin

Definition at line 71 of file rmodulo2m.cc.