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

Go to the source code of this file.

Macros

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

Functions

static BOOLEAN nr2mDBTest (number a, const char *f, const int l, const coeffs r)
 
static number nr2mMultM (number a, number b, const coeffs r)
 
static void nr2mInpMultM (number &a, number b, const coeffs r)
 
static number nr2mAddM (number a, number b, const coeffs r)
 
static void nr2mInpAddM (number &a, number b, const coeffs r)
 
static number nr2mSubM (number a, number b, const coeffs r)
 
static charnr2mCoeffName (const coeffs cf)
 
static BOOLEAN nr2mCoeffIsEqual (const coeffs r, n_coeffType n, void *p)
 
static coeffs nr2mQuot1 (number c, const coeffs r)
 
static BOOLEAN nr2mGreaterZero (number k, const coeffs r)
 
static number nr2mMult (number a, number b, const coeffs r)
 
static void nr2mInpMult (number &a, number b, const coeffs r)
 
static number nr2mAnn (number b, const coeffs r)
 
static number nr2mLcm (number a, number b, const coeffs)
 
static number nr2mGcd (number a, number b, const coeffs)
 
static void specialXGCD (unsigned long &s, unsigned long a, const coeffs r)
 
static unsigned long InvMod (unsigned long a, const coeffs r)
 
static number nr2mInversM (number c, const coeffs r)
 
static number nr2mInvers (number c, const coeffs r)
 
static number nr2mExtGcd (number a, number b, number *s, number *t, const coeffs r)
 
static void nr2mPower (number a, int i, number *result, const coeffs r)
 
static number nr2mInit (long i, const coeffs r)
 
static long nr2mInt (number &n, const coeffs r)
 
static number nr2mAdd (number a, number b, const coeffs r)
 
static void nr2mInpAdd (number &a, number b, const coeffs r)
 
static number nr2mSub (number a, number b, const coeffs r)
 
static BOOLEAN nr2mIsUnit (number a, const coeffs)
 
static number nr2mGetUnit (number k, const coeffs)
 
static BOOLEAN nr2mIsZero (number a, const coeffs)
 
static BOOLEAN nr2mIsOne (number a, const coeffs)
 
static BOOLEAN nr2mIsMOne (number a, const coeffs r)
 
static BOOLEAN nr2mEqual (number a, number b, const coeffs)
 
static number nr2mDiv (number a, number b, const coeffs r)
 
static BOOLEAN nr2mDivBy (number a, number b, const coeffs r)
 
static BOOLEAN nr2mGreater (number a, number b, const coeffs r)
 
static int nr2mDivComp (number as, number bs, const coeffs)
 
static number nr2mMod (number a, number b, const coeffs r)
 
static number nr2mNeg (number c, const coeffs r)
 
static number nr2mMapMachineInt (number from, const coeffs, const coeffs dst)
 
static number nr2mMapProject (number from, const coeffs, const coeffs dst)
 
number nr2mMapZp (number from, const coeffs, const coeffs dst)
 
static number nr2mMapGMP (number from, const coeffs, const coeffs dst)
 
static number nr2mMapQ (number from, const coeffs src, const coeffs dst)
 
static number nr2mMapZ (number from, const coeffs src, const coeffs dst)
 
static nMapFunc nr2mSetMap (const coeffs src, const coeffs dst)
 
static void nr2mSetExp (int m, coeffs r)
 
static void nr2mInitExp (int m, coeffs r)
 
static void nr2mWrite (number a, const coeffs r)
 
static const charnr2mEati (const char *s, int *i, const coeffs r)
 
static const charnr2mRead (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 69 of file rmodulo2m.cc.

◆ nr2mNegM

#define nr2mNegM ( A,
r )   (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:387
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 597 of file rmodulo2m.cc.

598{
599 if ((unsigned long)b == 0)
600 return NULL;
601 if ((unsigned long)b == 1)
602 return NULL;
603 unsigned long c = r->mod2mMask + 1;
604 if (c != 0) /* i.e., if no overflow */
605 return (number)(c / (unsigned long)b);
606 else
607 {
608 /* overflow: c = 2^32 resp. 2^64, depending on platform */
609 mpz_ptr cc = (mpz_ptr)omAlloc(sizeof(mpz_t));
610 mpz_init_set_ui(cc, r->mod2mMask); mpz_add_ui(cc, cc, 1);
611 mpz_div_ui(cc, cc, (unsigned long)(unsigned long)b);
612 unsigned long s = mpz_get_ui(cc);
614 return (number)(unsigned long)s;
615 }
616}
#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:100
#define FALSE
Definition auxiliary.h:96
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{
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 493 of file rmodulo2m.cc.

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

◆ nr2mEati()

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

Definition at line 757 of file rmodulo2m.cc.

758{
759
760 if (((*s) >= '0') && ((*s) <= '9'))
761 {
762 (*i) = 0;
763 do
764 {
765 (*i) *= 10;
766 (*i) += *s++ - '0';
767 if ((*i) >= (MAX_INT_VAL / 10)) (*i) = (*i) & r->mod2mMask;
768 }
769 while (((*s) >= '0') && ((*s) <= '9'));
770 (*i) = (*i) & r->mod2mMask;
771 }
772 else (*i) = 1;
773 return s;
774}
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 a,
number b,
const coeffs r )
static

Definition at line 488 of file rmodulo2m.cc.

489{
490 return nr2mDivBy(a, b,r);
491}
static BOOLEAN nr2mDivBy(number a, number b, const coeffs r)
Definition rmodulo2m.cc:460

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

796{
797 assume( getCoeffType(r) == n_Z2m );
798 nr2mInitExp((int)(long)(p), r);
799
800 r->is_field=FALSE;
801 r->is_domain=FALSE;
802 r->rep=n_rep_int;
803
804 //r->cfKillChar = ndKillChar; /* dummy*/
805 r->nCoeffIsEqual = nr2mCoeffIsEqual;
806
807 r->modBase = (mpz_ptr) omAllocBin (gmp_nrz_bin);
808 mpz_init_set_si (r->modBase, 2L);
809 r->modNumber= (mpz_ptr) omAllocBin (gmp_nrz_bin);
810 mpz_init (r->modNumber);
811 mpz_pow_ui (r->modNumber, r->modBase, r->modExponent);
812
813 /* next cast may yield an overflow as mod2mMask is an unsigned long */
814 r->ch = (int)r->mod2mMask + 1;
815
816 r->cfInit = nr2mInit;
817 //r->cfCopy = ndCopy;
818 r->cfInt = nr2mInt;
819 r->cfAdd = nr2mAdd;
820 r->cfInpAdd = nr2mInpAdd;
821 r->cfSub = nr2mSub;
822 r->cfMult = nr2mMult;
823 r->cfInpMult = nr2mInpMult;
824 r->cfDiv = nr2mDiv;
825 r->cfAnn = nr2mAnn;
826 r->cfIntMod = nr2mMod;
827 r->cfExactDiv = nr2mDiv;
828 r->cfInpNeg = nr2mNeg;
829 r->cfInvers = nr2mInvers;
830 r->cfDivBy = nr2mDivBy;
831 r->cfDivComp = nr2mDivComp;
832 r->cfGreater = nr2mGreater;
833 r->cfEqual = nr2mEqual;
834 r->cfIsZero = nr2mIsZero;
835 r->cfIsOne = nr2mIsOne;
836 r->cfIsMOne = nr2mIsMOne;
837 r->cfGreaterZero = nr2mGreaterZero;
838 r->cfWriteLong = nr2mWrite;
839 r->cfRead = nr2mRead;
840 r->cfPower = nr2mPower;
841 r->cfSetMap = nr2mSetMap;
842// r->cfNormalize = ndNormalize; // default
843 r->cfLcm = nr2mLcm;
844 r->cfGcd = nr2mGcd;
845 r->cfIsUnit = nr2mIsUnit;
846 r->cfGetUnit = nr2mGetUnit;
847 r->cfExtGcd = nr2mExtGcd;
848 r->cfCoeffName = nr2mCoeffName;
849 r->cfQuot1 = nr2mQuot1;
850#ifdef LDEBUG
851 r->cfDBTest = nr2mDBTest;
852#endif
853 r->has_simple_Alloc=TRUE;
854 return FALSE;
855}
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)
static nMapFunc nr2mSetMap(const coeffs src, const coeffs dst)
Definition rmodulo2m.cc:684
static void nr2mWrite(number a, const coeffs r)
Definition rmodulo2m.cc:751
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:597
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:744
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:493
static long nr2mInt(number &n, const coeffs r)
Definition rmodulo2m.cc:364
static BOOLEAN nr2mGreaterZero(number k, const coeffs r)
Definition rmodulo2m.cc:133
static number nr2mNeg(number c, const coeffs r)
Definition rmodulo2m.cc:618
EXTERN_VAR omBin gmp_nrz_bin
Definition rmodulo2m.cc:71
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:520
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 nr2mGreater(number a, number b, const coeffs r)
Definition rmodulo2m.cc:488
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:776
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 744 of file rmodulo2m.cc.

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

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

650{
652 mpz_init(erg);
653 mpz_ptr k = (mpz_ptr)omAlloc(sizeof(mpz_t));
654 mpz_init_set_ui(k, dst->mod2mMask);
655
656 mpz_and(erg, (mpz_ptr)from, k);
658
661
662 return (number)res;
663}

◆ nr2mMapMachineInt()

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

Definition at line 626 of file rmodulo2m.cc.

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

◆ nr2mMapProject()

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

Definition at line 632 of file rmodulo2m.cc.

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

◆ nr2mMapQ()

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

Definition at line 665 of file rmodulo2m.cc.

666{
668 nlMPZ(gmp, from, src);
671 return res;
672}
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:649

◆ nr2mMapZ()

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

Definition at line 674 of file rmodulo2m.cc.

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

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

◆ nr2mMod()

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

Definition at line 520 of file rmodulo2m.cc.

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

619{
620 if ((unsigned long)c == 0) return c;
621 number n=nr2mNegM(c, r);
622 n_Test(n,r);
623 return n;
624}
#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;
120 mpz_set(baseTokNew, r->modBase);
121 while(mpz_cmp(gcd, baseTokNew) > 0)
122 {
123 kNew++;
124 mpz_mul(baseTokNew, baseTokNew, r->modBase);
125 }
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 776 of file rmodulo2m.cc.

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

◆ nr2mSetExp()

static void nr2mSetExp ( int m,
coeffs r )
static

Definition at line 726 of file rmodulo2m.cc.

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

◆ nr2mSetMap()

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

Definition at line 684 of file rmodulo2m.cc.

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

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

752{
753 long i = nr2mInt(a, r);
754 StringAppend("%ld", i);
755}
#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));
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));
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
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.