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

◆ nr2mNegM

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

Definition at line 70 of file rmodulo2m.cc.

Function Documentation

◆ InvMod()

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

Definition at line 274 of file rmodulo2m.cc.

275{
276 assume((unsigned long)a % 2 != 0);
277 unsigned long s;
278 specialXGCD(s, a, r);
279 return s;
280}
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:216

◆ nr2mAdd()

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

Definition at line 376 of file rmodulo2m.cc.

377{
378 number n=nr2mAddM(a, b, r);
379 n_Test(n,r);
380 return n;
381}
CanonicalForm b
Definition: cfModGcd.cc:4103
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:709
static number nr2mAddM(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:51

◆ nr2mAddM()

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

Definition at line 51 of file rmodulo2m.cc.

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

◆ 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:119
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omFreeBinAddr(addr)
Definition: omAllocDecl.h:258
#define NULL
Definition: omList.c:12

◆ nr2mCoeffIsEqual()

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

Definition at line 85 of file rmodulo2m.cc.

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

◆ nr2mCoeffName()

static char * nr2mCoeffName ( const coeffs  cf)
static

Definition at line 75 of file rmodulo2m.cc.

76{
77 STATIC_VAR char n2mCoeffName_buf[37];
78 if (cf->modExponent>32) /* for 32/64bit arch.*/
79 snprintf(n2mCoeffName_buf,36,"ZZ/(bigint(2)^%lu)",cf->modExponent);
80 else
81 snprintf(n2mCoeffName_buf,36,"ZZ/(2^%lu)",cf->modExponent);
82 return n2mCoeffName_buf;
83}
CanonicalForm cf
Definition: cfModGcd.cc:4083
#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 26 of file rmodulo2m.cc.

27{
28 if ((((long)a<0L) || ((long)a>(long)r->mod2mMask))
29 && (r->mod2mMask!= ~0UL))
30 {
31 Print("wrong mod 2^n number %ld (m:%ld) at %s,%d\n",(long)a,(long)r->mod2mMask,f,l);
32 return FALSE;
33 }
34 return TRUE;
35}
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 429 of file rmodulo2m.cc.

430{
431 if ((unsigned long)a == 0) return (number)0;
432 else if ((unsigned long)b % 2 == 0)
433 {
434 if ((unsigned long)b != 0)
435 {
436 while (((unsigned long)b % 2 == 0) && ((unsigned long)a % 2 == 0))
437 {
438 a = (number)((unsigned long)a / 2);
439 b = (number)((unsigned long)b / 2);
440 }
441 }
442 if ((long)b==0L)
443 {
445 return (number)0L;
446 }
447 else if ((unsigned long)b % 2 == 0)
448 {
449 WerrorS("Division not possible, even by cancelling zero divisors.");
450 WerrorS("Result is integer division without remainder.");
451 return (number) ((unsigned long) a / (unsigned long) b);
452 }
453 }
454 number n=nr2mMult(a, nr2mInversM(b,r),r);
455 n_Test(n,r);
456 return n;
457}
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:282
static number nr2mMult(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:145

◆ nr2mDivBy()

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

Definition at line 462 of file rmodulo2m.cc.

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

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

425{
426 return (a == b);
427}

◆ nr2mExtGcd()

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

Definition at line 305 of file rmodulo2m.cc.

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

◆ nr2mGcd()

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

Definition at line 192 of file rmodulo2m.cc.

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

◆ nr2mGetUnit()

static number nr2mGetUnit ( number  k,
const  coeffs 
)
static

Definition at line 401 of file rmodulo2m.cc.

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

◆ nr2mGreater()

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

Definition at line 490 of file rmodulo2m.cc.

491{
492 return nr2mDivBy(a, b,r);
493}
static BOOLEAN nr2mDivBy(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:462

◆ nr2mGreaterZero()

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

Definition at line 135 of file rmodulo2m.cc.

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

◆ nr2mInit()

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

Definition at line 349 of file rmodulo2m.cc.

350{
351 if (i == 0) return (number)(unsigned long)0;
352
353 long ii = i;
354 unsigned long j = (unsigned long)1;
355 if (ii < 0) { j = r->mod2mMask; ii = -ii; }
356 unsigned long k = (unsigned long)ii;
357 k = k & r->mod2mMask;
358 /* now we have: i = j * k mod 2^m */
359 return nr2mMult((number)j, (number)k, r);
360}
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:422
@ n_rep_int
(int), see modulop.h
Definition: coeffs.h:110
#define LDEBUG
Definition: mod2.h:307
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
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 void nr2mInpAdd(number &a, number b, const coeffs r)
Definition: rmodulo2m.cc:383
static number nr2mSub(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:389
static number nr2mLcm(number a, number b, const coeffs)
Definition: rmodulo2m.cc:169
static BOOLEAN nr2mIsOne(number a, const coeffs)
Definition: rmodulo2m.cc:414
static number nr2mAnn(number b, const coeffs r)
Definition: rmodulo2m.cc:599
static number nr2mInit(long i, const coeffs r)
Definition: rmodulo2m.cc:349
static number nr2mExtGcd(number a, number b, number *s, number *t, const coeffs r)
Definition: rmodulo2m.cc:305
static number nr2mGetUnit(number k, const coeffs)
Definition: rmodulo2m.cc:401
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:329
static int nr2mDivComp(number as, number bs, const coeffs)
Definition: rmodulo2m.cc:495
static long nr2mInt(number &n, const coeffs r)
Definition: rmodulo2m.cc:366
static BOOLEAN nr2mGreaterZero(number k, const coeffs r)
Definition: rmodulo2m.cc:135
static number nr2mNeg(number c, const coeffs r)
Definition: rmodulo2m.cc:620
EXTERN_VAR omBin gmp_nrz_bin
Definition: rmodulo2m.cc:73
static BOOLEAN nr2mDBTest(number a, const char *f, const int l, const coeffs r)
Definition: rmodulo2m.cc:26
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:85
static number nr2mAdd(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:376
static void nr2mInpMult(number &a, number b, const coeffs r)
Definition: rmodulo2m.cc:156
static char * nr2mCoeffName(const coeffs cf)
Definition: rmodulo2m.cc:75
static BOOLEAN nr2mEqual(number a, number b, const coeffs)
Definition: rmodulo2m.cc:424
static BOOLEAN nr2mGreater(number a, number b, const coeffs r)
Definition: rmodulo2m.cc:490
static BOOLEAN nr2mIsZero(number a, const coeffs)
Definition: rmodulo2m.cc:409
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:419
static coeffs nr2mQuot1(number c, const coeffs r)
Definition: rmodulo2m.cc:96

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

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

◆ nr2mInpAddM()

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

Definition at line 57 of file rmodulo2m.cc.

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

◆ nr2mInpMult()

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

Definition at line 156 of file rmodulo2m.cc.

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

◆ nr2mInpMultM()

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

Definition at line 45 of file rmodulo2m.cc.

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

◆ nr2mInt()

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

Definition at line 366 of file rmodulo2m.cc.

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

◆ nr2mInvers()

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

Definition at line 291 of file rmodulo2m.cc.

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

◆ nr2mInversM()

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

Definition at line 282 of file rmodulo2m.cc.

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

◆ nr2mIsMOne()

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

Definition at line 419 of file rmodulo2m.cc.

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

◆ nr2mIsOne()

static BOOLEAN nr2mIsOne ( number  a,
const  coeffs 
)
static

Definition at line 414 of file rmodulo2m.cc.

415{
416 return 1 == (unsigned long)a;
417}

◆ nr2mIsUnit()

static BOOLEAN nr2mIsUnit ( number  a,
const  coeffs 
)
static

Definition at line 396 of file rmodulo2m.cc.

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

◆ nr2mIsZero()

static BOOLEAN nr2mIsZero ( number  a,
const  coeffs 
)
static

Definition at line 409 of file rmodulo2m.cc.

410{
411 return 0 == (unsigned long)a;
412}

◆ nr2mLcm()

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

Definition at line 169 of file rmodulo2m.cc.

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

◆ 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:2819
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:4090

◆ nr2mMult()

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

Definition at line 145 of file rmodulo2m.cc.

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

◆ nr2mMultM()

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

Definition at line 39 of file rmodulo2m.cc.

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

◆ 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:70

◆ nr2mPower()

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

Definition at line 329 of file rmodulo2m.cc.

330{
331 if (i == 0)
332 {
333 *(unsigned long *)result = 1;
334 }
335 else if (i == 1)
336 {
337 *result = a;
338 }
339 else
340 {
341 nr2mPower(a, i-1, result, r);
342 *result = nr2mMultM(a, *result, r);
343 }
344}
return result
Definition: facAbsBiFact.cc:75

◆ nr2mQuot1()

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

Definition at line 96 of file rmodulo2m.cc.

97{
98 coeffs rr;
99 long ch = r->cfInt(c, r);
100 mpz_t a,b;
101 mpz_init_set(a, r->modNumber);
102 mpz_init_set_ui(b, ch);
103 mpz_ptr gcd;
104 gcd = (mpz_ptr) omAlloc(sizeof(mpz_t));
105 mpz_init(gcd);
106 mpz_gcd(gcd, a,b);
107 if(mpz_cmp_ui(gcd, 1) == 0)
108 {
109 WerrorS("constant in q-ideal is coprime to modulus in ground ring");
110 WerrorS("Unable to create qring!");
111 return NULL;
112 }
113 if(mpz_cmp_ui(gcd, 2) == 0)
114 {
115 rr = nInitChar(n_Zp, (void*)2);
116 }
117 else
118 {
119 int kNew = 1;
120 mpz_t baseTokNew;
121 mpz_init(baseTokNew);
122 mpz_set(baseTokNew, r->modBase);
123 while(mpz_cmp(gcd, baseTokNew) > 0)
124 {
125 kNew++;
126 mpz_mul(baseTokNew, baseTokNew, r->modBase);
127 }
128 mpz_clear(baseTokNew);
129 rr = nInitChar(n_Z2m, (void*)(long)kNew);
130 }
131 return(rr);
132}
@ 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:413
The main handler for Singular numbers which are suitable for Singular polynomials.
int gcd(int a, int b)
Definition: walkSupport.cc:836

◆ 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:813
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_PtoM(const coeffs r)
Definition: coeffs.h:724
static FORCE_INLINE BOOLEAN nCoeff_is_Q(const coeffs r)
Definition: coeffs.h:803
static FORCE_INLINE BOOLEAN nCoeff_is_Zn(const coeffs r)
Definition: coeffs.h:823
static FORCE_INLINE BOOLEAN nCoeff_is_Zp(const coeffs r)
Definition: coeffs.h:797
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_2toM(const coeffs r)
Definition: coeffs.h:721
@ n_rep_gap_rat
(number), see longrat.h
Definition: coeffs.h:111
@ n_rep_gap_gmp
(), see rinteger.h, new impl.
Definition: coeffs.h:112
@ n_rep_gmp
(mpz_ptr), see rmodulon,h
Definition: coeffs.h:115
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 389 of file rmodulo2m.cc.

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

◆ nr2mSubM()

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

Definition at line 63 of file rmodulo2m.cc.

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

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

217{
218 mpz_ptr u = (mpz_ptr)omAlloc(sizeof(mpz_t));
219 mpz_init_set_ui(u, a);
220 mpz_ptr u0 = (mpz_ptr)omAlloc(sizeof(mpz_t));
221 mpz_init(u0);
222 mpz_ptr u1 = (mpz_ptr)omAlloc(sizeof(mpz_t));
223 mpz_init_set_ui(u1, 1);
224 mpz_ptr u2 = (mpz_ptr)omAlloc(sizeof(mpz_t));
225 mpz_init(u2);
226 mpz_ptr v = (mpz_ptr)omAlloc(sizeof(mpz_t));
227 mpz_init_set_ui(v, r->mod2mMask);
228 mpz_add_ui(v, v, 1); /* now: v = 2^m */
229 mpz_ptr v0 = (mpz_ptr)omAlloc(sizeof(mpz_t));
230 mpz_init(v0);
231 mpz_ptr v1 = (mpz_ptr)omAlloc(sizeof(mpz_t));
232 mpz_init(v1);
233 mpz_ptr v2 = (mpz_ptr)omAlloc(sizeof(mpz_t));
234 mpz_init_set_ui(v2, 1);
235 mpz_ptr q = (mpz_ptr)omAlloc(sizeof(mpz_t));
236 mpz_init(q);
237 mpz_ptr rr = (mpz_ptr)omAlloc(sizeof(mpz_t));
238 mpz_init(rr);
239
240 while (mpz_sgn1(v) != 0) /* i.e., while v != 0 */
241 {
242 mpz_div(q, u, v);
243 mpz_mod(rr, u, v);
244 mpz_set(u, v);
245 mpz_set(v, rr);
246 mpz_set(u0, u2);
247 mpz_set(v0, v2);
248 mpz_mul(u2, u2, q); mpz_sub(u2, u1, u2); /* u2 = u1 - q * u2 */
249 mpz_mul(v2, v2, q); mpz_sub(v2, v1, v2); /* v2 = v1 - q * v2 */
250 mpz_set(u1, u0);
251 mpz_set(v1, v0);
252 }
253
254 while (mpz_sgn1(u1) < 0) /* i.e., while u1 < 0 */
255 {
256 /* we add 2^m = (2^m - 1) + 1 to u1: */
257 mpz_add_ui(u1, u1, r->mod2mMask);
258 mpz_add_ui(u1, u1, 1);
259 }
260 s = mpz_get_ui(u1); /* now: 0 <= s <= 2^m - 1 */
261
262 mpz_clear(u); omFreeBinAddr((ADDRESS)u);
263 mpz_clear(u0); omFreeBinAddr((ADDRESS)u0);
264 mpz_clear(u1); omFreeBinAddr((ADDRESS)u1);
265 mpz_clear(u2); omFreeBinAddr((ADDRESS)u2);
266 mpz_clear(v); omFreeBinAddr((ADDRESS)v);
267 mpz_clear(v0); omFreeBinAddr((ADDRESS)v0);
268 mpz_clear(v1); omFreeBinAddr((ADDRESS)v1);
269 mpz_clear(v2); omFreeBinAddr((ADDRESS)v2);
270 mpz_clear(q); omFreeBinAddr((ADDRESS)q);
271 mpz_clear(rr); omFreeBinAddr((ADDRESS)rr);
272}
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 73 of file rmodulo2m.cc.