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,
			r
	)		(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.

{
  assume((unsigned long)a % 2 != 0);
  unsigned long s;
  specialXGCD(s, a, r);
  return s;
}

nr2mAdd()

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

static

Definition at line 376 of file rmodulo2m.cc.

{
  number n=nr2mAddM(a, b, r);
  n_Test(n,r);
  return n;
}

nr2mAddM()

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

inlinestatic

Definition at line 51 of file rmodulo2m.cc.

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

nr2mAnn()

static number nr2mAnn ( number  b, const coeffs  r  )

static

Definition at line 599 of file rmodulo2m.cc.

{
  if ((unsigned long)b == 0)
    return NULL;
  if ((unsigned long)b == 1)
    return NULL;
  unsigned long c = r->mod2mMask + 1;
  if (c != 0) /* i.e., if no overflow */
    return (number)(c / (unsigned long)b);
  else
  {
    /* overflow: c = 2^32 resp. 2^64, depending on platform */
    mpz_ptr cc = (mpz_ptr)omAlloc(sizeof(mpz_t));
    mpz_init_set_ui(cc, r->mod2mMask); mpz_add_ui(cc, cc, 1);
    mpz_div_ui(cc, cc, (unsigned long)(unsigned long)b);
    unsigned long s = mpz_get_ui(cc);
    mpz_clear(cc); omFreeBinAddr((ADDRESS)cc);
    return (number)(unsigned long)s;
  }
}

nr2mCoeffIsEqual()

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

static

Definition at line 85 of file rmodulo2m.cc.

{
  if (n==n_Z2m)
  {
    int m=(int)(long)(p);
    unsigned long mm=r->mod2mMask;
    if (((mm+1)>>m)==1L) return TRUE;
  }
  return FALSE;
}

nr2mCoeffName()

static char * nr2mCoeffName ( const coeffs  cf )

static

Definition at line 75 of file rmodulo2m.cc.

{
  STATIC_VAR char n2mCoeffName_buf[37];
  if (cf->modExponent>32) /* for 32/64bit arch.*/
    snprintf(n2mCoeffName_buf,36,"ZZ/(bigint(2)^%lu)",cf->modExponent);
  else
    snprintf(n2mCoeffName_buf,36,"ZZ/(2^%lu)",cf->modExponent);
  return n2mCoeffName_buf;
}

nr2mDBTest()

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

static

Definition at line 26 of file rmodulo2m.cc.

{
  if ((((long)a<0L) || ((long)a>(long)r->mod2mMask))
  && (r->mod2mMask!= ~0UL))
  {
    Print("wrong mod 2^n number %ld (m:%ld) at %s,%d\n",(long)a,(long)r->mod2mMask,f,l);
    return FALSE;
  }
  return TRUE;
}

nr2mDiv()

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

static

Definition at line 429 of file rmodulo2m.cc.

{
  if ((unsigned long)a == 0) return (number)0;
  else if ((unsigned long)b % 2 == 0)
  {
    if ((unsigned long)b != 0)
    {
      while (((unsigned long)b % 2 == 0) && ((unsigned long)a % 2 == 0))
      {
        a = (number)((unsigned long)a / 2);
        b = (number)((unsigned long)b / 2);
      }
    }
    if ((long)b==0L)
    {
      WerrorS(nDivBy0);
      return (number)0L;
    }
    else if ((unsigned long)b % 2 == 0)
    {
      WerrorS("Division not possible, even by cancelling zero divisors.");
      WerrorS("Result is integer division without remainder.");
      return (number) ((unsigned long) a / (unsigned long) b);
    }
  }
  number n=nr2mMult(a, nr2mInversM(b,r),r);
  n_Test(n,r);
  return n;
}

nr2mDivBy()

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

static

Definition at line 462 of file rmodulo2m.cc.

{
  if (a == NULL)
  {
    unsigned long c = r->mod2mMask + 1;
    if (c != 0) /* i.e., if no overflow */
      return (c % (unsigned long)b) == 0;
    else
    {
      /* overflow: we need to check whether b
         is zero or a power of 2: */
      c = (unsigned long)b;
      while (c != 0)
      {
        if ((c % 2) != 0) return FALSE;
        c = c >> 1;
      }
      return TRUE;
    }
  }
  else
  {
    number n = nr2mGcd(a, b, r);
    n = nr2mDiv(b, n, r);
    return nr2mIsUnit(n, r);
  }
}

nr2mDivComp()

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

static

Definition at line 495 of file rmodulo2m.cc.

{
  unsigned long a = (unsigned long)as;
  unsigned long b = (unsigned long)bs;
  assume(a != 0 && b != 0);
  while (a % 2 == 0 && b % 2 == 0)
  {
    a = a / 2;
    b = b / 2;
  }
  if (a % 2 == 0)
  {
    return -1;
  }
  else
  {
    if (b % 2 == 1)
    {
      return 2;
    }
    else
    {
      return 1;
    }
  }
}

nr2mEati()

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

static

Definition at line 759 of file rmodulo2m.cc.

{
 
  if (((*s) >= '0') && ((*s) <= '9'))
  {
    (*i) = 0;
    do
    {
      (*i) *= 10;
      (*i) += *s++ - '0';
      if ((*i) >= (MAX_INT_VAL / 10)) (*i) = (*i) & r->mod2mMask;
    }
    while (((*s) >= '0') && ((*s) <= '9'));
    (*i) = (*i) & r->mod2mMask;
  }
  else (*i) = 1;
  return s;
}

nr2mEqual()

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

static

Definition at line 424 of file rmodulo2m.cc.

{
  return (a == b);
}

nr2mExtGcd()

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

static

Definition at line 305 of file rmodulo2m.cc.

{
  unsigned long res = 0;
  if ((unsigned long)a == 0 && (unsigned long)b == 0) return (number)1;
  while ((unsigned long)a % 2 == 0 && (unsigned long)b % 2 == 0)
  {
    a = (number)((unsigned long)a / 2);
    b = (number)((unsigned long)b / 2);
    res++;
  }
  if ((unsigned long)b % 2 == 0)
  {
    *t = NULL;
    *s = nr2mInvers(a,r);
    return (number)((1L << res)); // * (unsigned long) a);  // (2**res)*a    a is a unit
  }
  else
  {
    *s = NULL;
    *t = nr2mInvers(b,r);
    return (number)((1L << res)); // * (unsigned long) b);  // (2**res)*b    b is a unit
  }
}

nr2mGcd()

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

static

Definition at line 192 of file rmodulo2m.cc.

{
  unsigned long res = 0;
  if ((unsigned long)a == 0 && (unsigned long)b == 0) return (number)1;
  while ((unsigned long)a % 2 == 0 && (unsigned long)b % 2 == 0)
  {
    a = (number)((unsigned long)a / 2);
    b = (number)((unsigned long)b / 2);
    res++;
  }
//  if ((unsigned long)b % 2 == 0)
//  {
//    return (number)((1L << res)); // * (unsigned long) a);  // (2**res)*a    a is a unit
//  }
//  else
//  {
    return (number)((1L << res)); // * (unsigned long) b);  // (2**res)*b    b is a unit
//  }
}

nr2mGetUnit()

static number nr2mGetUnit ( number  k, const  coeffs  )

static

Definition at line 401 of file rmodulo2m.cc.

{
  if (k == NULL) return (number)1;
  unsigned long erg = (unsigned long)k;
  while (erg % 2 == 0) erg = erg / 2;
  return (number)erg;
}

nr2mGreater()

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

static

Definition at line 490 of file rmodulo2m.cc.

{
  return nr2mDivBy(a, b,r);
}

nr2mGreaterZero()

static BOOLEAN nr2mGreaterZero ( number  k, const coeffs  r  )

static

Definition at line 135 of file rmodulo2m.cc.

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

nr2mInit()

static number nr2mInit ( long  i, const coeffs  r  )

static

Definition at line 349 of file rmodulo2m.cc.

{
  if (i == 0) return (number)(unsigned long)0;
 
  long ii = i;
  unsigned long j = (unsigned long)1;
  if (ii < 0) { j = r->mod2mMask; ii = -ii; }
  unsigned long k = (unsigned long)ii;
  k = k & r->mod2mMask;
  /* now we have: i = j * k mod 2^m */
  return nr2mMult((number)j, (number)k, r);
}

nr2mInitChar()

BOOLEAN nr2mInitChar	(	coeffs	r,
		void *	p
	)

Definition at line 797 of file rmodulo2m.cc.

{
  assume( getCoeffType(r) == n_Z2m );
  nr2mInitExp((int)(long)(p), r);
 
  r->is_field=FALSE;
  r->is_domain=FALSE;
  r->rep=n_rep_int;
 
  //r->cfKillChar    = ndKillChar; /* dummy*/
  r->nCoeffIsEqual = nr2mCoeffIsEqual;
 
  r->modBase = (mpz_ptr) omAllocBin (gmp_nrz_bin);
  mpz_init_set_si (r->modBase, 2L);
  r->modNumber= (mpz_ptr) omAllocBin (gmp_nrz_bin);
  mpz_init (r->modNumber);
  mpz_pow_ui (r->modNumber, r->modBase, r->modExponent);
 
  /* next cast may yield an overflow as mod2mMask is an unsigned long */
  r->ch = (int)r->mod2mMask + 1;
 
  r->cfInit        = nr2mInit;
  //r->cfCopy        = ndCopy;
  r->cfInt         = nr2mInt;
  r->cfAdd         = nr2mAdd;
  r->cfInpAdd      = nr2mInpAdd;
  r->cfSub         = nr2mSub;
  r->cfMult        = nr2mMult;
  r->cfInpMult     = nr2mInpMult;
  r->cfDiv         = nr2mDiv;
  r->cfAnn         = nr2mAnn;
  r->cfIntMod      = nr2mMod;
  r->cfExactDiv    = nr2mDiv;
  r->cfInpNeg         = nr2mNeg;
  r->cfInvers      = nr2mInvers;
  r->cfDivBy       = nr2mDivBy;
  r->cfDivComp     = nr2mDivComp;
  r->cfGreater     = nr2mGreater;
  r->cfEqual       = nr2mEqual;
  r->cfIsZero      = nr2mIsZero;
  r->cfIsOne       = nr2mIsOne;
  r->cfIsMOne      = nr2mIsMOne;
  r->cfGreaterZero = nr2mGreaterZero;
  r->cfWriteLong       = nr2mWrite;
  r->cfRead        = nr2mRead;
  r->cfPower       = nr2mPower;
  r->cfSetMap      = nr2mSetMap;
//  r->cfNormalize   = ndNormalize; // default
  r->cfLcm         = nr2mLcm;
  r->cfGcd         = nr2mGcd;
  r->cfIsUnit      = nr2mIsUnit;
  r->cfGetUnit     = nr2mGetUnit;
  r->cfExtGcd      = nr2mExtGcd;
  r->cfCoeffName   = nr2mCoeffName;
  r->cfQuot1       = nr2mQuot1;
#ifdef LDEBUG
  r->cfDBTest      = nr2mDBTest;
#endif
  r->has_simple_Alloc=TRUE;
  return FALSE;
}

nr2mInitExp()

static void nr2mInitExp ( int  m, coeffs  r  )

static

Definition at line 746 of file rmodulo2m.cc.

{
  nr2mSetExp(m, r);
  if (m < 2)
    WarnS("nr2mInitExp unexpectedly called with m = 1 (we continue with Z/2^2");
}

nr2mInpAdd()

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

static

Definition at line 383 of file rmodulo2m.cc.

{
  nr2mInpAddM(a, b, r);
  n_Test(a,r);
}

nr2mInpAddM()

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

inlinestatic

Definition at line 57 of file rmodulo2m.cc.

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

nr2mInpMult()

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

static

Definition at line 156 of file rmodulo2m.cc.

{
  if (((unsigned long)a == 0) || ((unsigned long)b == 0))
  { a=(number)0;  return; }
  else
    nr2mInpMultM(a, b, r);
  n_Test(a,r);
}

nr2mInpMultM()

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

inlinestatic

Definition at line 45 of file rmodulo2m.cc.

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

nr2mInt()

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

static

Definition at line 366 of file rmodulo2m.cc.

{
  unsigned long nn = (unsigned long)n;
  unsigned long l = r->mod2mMask >> 1; l++; /* now: l = 2^(m-1) */
  if ((unsigned long)nn > l)
    return (long)((unsigned long)nn - r->mod2mMask - 1);
  else
    return (long)((unsigned long)nn);
}

nr2mInvers()

static number nr2mInvers ( number  c, const coeffs  r  )

static

Definition at line 291 of file rmodulo2m.cc.

{
  if ((unsigned long)c % 2 == 0)
  {
    WerrorS("division by zero divisor");
    return (number)0;
  }
  return nr2mInversM(c, r);
}

nr2mInversM()

static number nr2mInversM ( number  c, const coeffs  r  )

inlinestatic

Definition at line 282 of file rmodulo2m.cc.

{
  assume((unsigned long)c % 2 != 0);
  // Table !!!
  unsigned long inv;
  inv = InvMod((unsigned long)c,r);
  return (number)inv;
}

nr2mIsMOne()

static BOOLEAN nr2mIsMOne ( number  a, const coeffs  r  )

static

Definition at line 419 of file rmodulo2m.cc.

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

nr2mIsOne()

static BOOLEAN nr2mIsOne ( number  a, const  coeffs  )

static

Definition at line 414 of file rmodulo2m.cc.

{
  return 1 == (unsigned long)a;
}

nr2mIsUnit()

static BOOLEAN nr2mIsUnit ( number  a, const  coeffs  )

static

Definition at line 396 of file rmodulo2m.cc.

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

nr2mIsZero()

static BOOLEAN nr2mIsZero ( number  a, const  coeffs  )

static

Definition at line 409 of file rmodulo2m.cc.

{
  return 0 == (unsigned long)a;
}

nr2mLcm()

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

static

Definition at line 169 of file rmodulo2m.cc.

{
  unsigned long res = 0;
  if ((unsigned long)a == 0) a = (number) 1;
  if ((unsigned long)b == 0) b = (number) 1;
  while ((unsigned long)a % 2 == 0)
  {
    a = (number)((unsigned long)a / 2);
    if ((unsigned long)b % 2 == 0) b = (number)((unsigned long)b / 2);
    res++;
  }
  while ((unsigned long)b % 2 == 0)
  {
    b = (number)((unsigned long)b / 2);
    res++;
  }
  return (number)(1L << res);  // (2**res)
}

nr2mMapGMP()

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

static

Definition at line 651 of file rmodulo2m.cc.

{
  mpz_ptr erg = (mpz_ptr)omAllocBin(gmp_nrz_bin);
  mpz_init(erg);
  mpz_ptr k = (mpz_ptr)omAlloc(sizeof(mpz_t));
  mpz_init_set_ui(k, dst->mod2mMask);
 
  mpz_and(erg, (mpz_ptr)from, k);
  number res = (number) mpz_get_ui(erg);
 
  mpz_clear(erg); omFreeBinAddr((ADDRESS)erg);
  mpz_clear(k);   omFreeBinAddr((ADDRESS)k);
 
  return (number)res;
}

nr2mMapMachineInt()

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

static

Definition at line 628 of file rmodulo2m.cc.

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

nr2mMapProject()

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

static

Definition at line 634 of file rmodulo2m.cc.

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

nr2mMapQ()

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

static

Definition at line 667 of file rmodulo2m.cc.

{
  mpz_ptr gmp = (mpz_ptr)omAllocBin(gmp_nrz_bin);
  nlMPZ(gmp, from, src);
  number res=nr2mMapGMP((number)gmp,src,dst);
  mpz_clear(gmp); omFreeBinAddr((ADDRESS)gmp);
  return res;
}

nr2mMapZ()

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

static

Definition at line 676 of file rmodulo2m.cc.

{
  if (SR_HDL(from) & SR_INT)
  {
    long f_i=SR_TO_INT(from);
    return nr2mInit(f_i,dst);
  }
  return nr2mMapGMP(from,src,dst);
}

nr2mMapZp()

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

Definition at line 640 of file rmodulo2m.cc.

{
  unsigned long j = (unsigned long)1;
  long ii = (long)from;
  if (ii < 0) { j = dst->mod2mMask; ii = -ii; }
  unsigned long i = (unsigned long)ii;
  i = i & dst->mod2mMask;
  /* now we have: from = j * i mod 2^m */
  return nr2mMult((number)i, (number)j, dst);
}

nr2mMod()

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

static

Definition at line 522 of file rmodulo2m.cc.

{
  /*
    We need to return the number rr which is uniquely determined by the
    following two properties:
      (1) 0 <= rr < |b| (with respect to '<' and '<=' performed in Z x Z)
      (2) There exists some k in the integers Z such that a = k * b + rr.
    Consider g := gcd(2^m, |b|). Note that then |b|/g is a unit in Z/2^m.
    Now, there are three cases:
      (a) g = 1
          Then |b| is a unit in Z/2^m, i.e. |b| (and also b) divides a.
          Thus rr = 0.
      (b) g <> 1 and g divides a
          Then a = (a/g) * (|b|/g)^(-1) * b (up to sign), i.e. again rr = 0.
      (c) g <> 1 and g does not divide a
          Let's denote the division with remainder of a by g as follows:
          a = s * g + t. Then t = a - s * g = a - s * (|b|/g)^(-1) * |b|
          fulfills (1) and (2), i.e. rr := t is the correct result. Hence
          in this third case, rr is the remainder of division of a by g in Z.
    This algorithm is the same as for the case Z/n, except that we may
    compute the gcd of |b| and 2^m "by hand": We just extract the highest
    power of 2 (<= 2^m) that is contained in b.
  */
  assume((unsigned long) b != 0);
  unsigned long g = 1;
  unsigned long b_div = (unsigned long) b;
 
  /*
   * b_div is unsigned, so that (b_div < 0) evaluates false at compile-time
   *
  if (b_div < 0) b_div = -b_div; // b_div now represents |b|, BUT b_div is unsigned!
  */
 
  unsigned long rr = 0;
  while ((g < r->mod2mMask ) && (b_div > 0) && (b_div % 2 == 0))
  {
    b_div = b_div >> 1;
    g = g << 1;
  } // g is now the gcd of 2^m and |b|
 
  if (g != 1) rr = (unsigned long)a % g;
  return (number)rr;
}

nr2mMult()

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

static

Definition at line 145 of file rmodulo2m.cc.

{
  number n;
  if (((unsigned long)a == 0) || ((unsigned long)b == 0))
    return (number)0;
  else
    n=nr2mMultM(a, b, r);
  n_Test(n,r);
  return n;
}

nr2mMultM()

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

inlinestatic

Definition at line 39 of file rmodulo2m.cc.

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

nr2mNeg()

static number nr2mNeg ( number  c, const coeffs  r  )

static

Definition at line 620 of file rmodulo2m.cc.

{
  if ((unsigned long)c == 0) return c;
  number n=nr2mNegM(c, r);
  n_Test(n,r);
  return n;
}

nr2mPower()

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

static

Definition at line 329 of file rmodulo2m.cc.

{
  if (i == 0)
  {
    *(unsigned long *)result = 1;
  }
  else if (i == 1)
  {
    *result = a;
  }
  else
  {
    nr2mPower(a, i-1, result, r);
    *result = nr2mMultM(a, *result, r);
  }
}

nr2mQuot1()

static coeffs nr2mQuot1 ( number  c, const coeffs  r  )

static

Definition at line 96 of file rmodulo2m.cc.

{
  coeffs rr;
  long ch = r->cfInt(c, r);
  mpz_t a,b;
  mpz_init_set(a, r->modNumber);
  mpz_init_set_ui(b, ch);
  mpz_ptr gcd;
  gcd = (mpz_ptr) omAlloc(sizeof(mpz_t));
  mpz_init(gcd);
  mpz_gcd(gcd, a,b);
  if(mpz_cmp_ui(gcd, 1) == 0)
  {
    WerrorS("constant in q-ideal is coprime to modulus in ground ring");
    WerrorS("Unable to create qring!");
    return NULL;
  }
  if(mpz_cmp_ui(gcd, 2) == 0)
  {
    rr = nInitChar(n_Zp, (void*)2);
  }
  else
  {
    int kNew = 1;
    mpz_t baseTokNew;
    mpz_init(baseTokNew);
    mpz_set(baseTokNew, r->modBase);
    while(mpz_cmp(gcd, baseTokNew) > 0)
    {
      kNew++;
      mpz_mul(baseTokNew, baseTokNew, r->modBase);
    }
    mpz_clear(baseTokNew);
    rr = nInitChar(n_Z2m, (void*)(long)kNew);
  }
  return(rr);
}

nr2mRead()

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

static

Definition at line 778 of file rmodulo2m.cc.

{
  int z;
  int n=1;
 
  s = nr2mEati(s, &z,r);
  if ((*s) == '/')
  {
    s++;
    s = nr2mEati(s, &n,r);
  }
  if (n == 1)
    *a = (number)(long)z;
  else
      *a = nr2mDiv((number)(long)z,(number)(long)n,r);
  return s;
}

nr2mSetExp()

static void nr2mSetExp ( int  m, coeffs  r  )

static

Definition at line 728 of file rmodulo2m.cc.

{
  if (m > 1)
  {
    /* we want mod2mMask to be the bit pattern
       '111..1' consisting of m one's: */
    r->modExponent= m;
    r->mod2mMask = 1;
    for (int i = 1; i < m; i++) r->mod2mMask = (r->mod2mMask << 1) + 1;
  }
  else
  {
    r->modExponent= 2;
    /* code unexpectedly called with m = 1; we continue with m = 2: */
    r->mod2mMask = 3; /* i.e., '11' in binary representation */
  }
}

nr2mSetMap()

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

static

Definition at line 686 of file rmodulo2m.cc.

{
  if ((src->rep==n_rep_int) && nCoeff_is_Ring_2toM(src)
     && (src->mod2mMask < dst->mod2mMask))
  { /* i.e. map an integer mod 2^s into Z mod 2^t, where t < s */
    return nr2mMapMachineInt;
  }
  if ((src->rep==n_rep_int) && nCoeff_is_Ring_2toM(src)
     && (src->mod2mMask > dst->mod2mMask))
  { /* i.e. map an integer mod 2^s into Z mod 2^t, where t > s */
    // to be done
    return nr2mMapProject;
  }
  if ((src->rep==n_rep_gmp) && nCoeff_is_Z(src))
  {
    return nr2mMapGMP;
  }
  if ((src->rep==n_rep_gap_gmp) /*&& nCoeff_is_Z(src)*/)
  {
    return nr2mMapZ;
  }
  if ((src->rep==n_rep_gap_rat) && (nCoeff_is_Q(src)||nCoeff_is_Z(src)))
  {
    return nr2mMapQ;
  }
  if ((src->rep==n_rep_int) && nCoeff_is_Zp(src) && (src->ch == 2))
  {
    return nr2mMapZp;
  }
  if ((src->rep==n_rep_gmp) &&
  (nCoeff_is_Ring_PtoM(src) || nCoeff_is_Zn(src)))
  {
    if (mpz_divisible_2exp_p(src->modNumber,dst->modExponent))
      return nr2mMapGMP;
  }
  return NULL;      // default
}

nr2mSub()

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

static

Definition at line 389 of file rmodulo2m.cc.

{
  number n=nr2mSubM(a, b, r);
  n_Test(n,r);
  return n;
}

nr2mSubM()

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

inlinestatic

Definition at line 63 of file rmodulo2m.cc.

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

nr2mWrite()

static void nr2mWrite ( number  a, const coeffs  r  )

static

Definition at line 753 of file rmodulo2m.cc.

{
  long i = nr2mInt(a, r);
  StringAppend("%ld", i);
}

specialXGCD()

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

static

Definition at line 216 of file rmodulo2m.cc.

{
  mpz_ptr u = (mpz_ptr)omAlloc(sizeof(mpz_t));
  mpz_init_set_ui(u, a);
  mpz_ptr u0 = (mpz_ptr)omAlloc(sizeof(mpz_t));
  mpz_init(u0);
  mpz_ptr u1 = (mpz_ptr)omAlloc(sizeof(mpz_t));
  mpz_init_set_ui(u1, 1);
  mpz_ptr u2 = (mpz_ptr)omAlloc(sizeof(mpz_t));
  mpz_init(u2);
  mpz_ptr v = (mpz_ptr)omAlloc(sizeof(mpz_t));
  mpz_init_set_ui(v, r->mod2mMask);
  mpz_add_ui(v, v, 1); /* now: v = 2^m */
  mpz_ptr v0 = (mpz_ptr)omAlloc(sizeof(mpz_t));
  mpz_init(v0);
  mpz_ptr v1 = (mpz_ptr)omAlloc(sizeof(mpz_t));
  mpz_init(v1);
  mpz_ptr v2 = (mpz_ptr)omAlloc(sizeof(mpz_t));
  mpz_init_set_ui(v2, 1);
  mpz_ptr q = (mpz_ptr)omAlloc(sizeof(mpz_t));
  mpz_init(q);
  mpz_ptr rr = (mpz_ptr)omAlloc(sizeof(mpz_t));
  mpz_init(rr);
 
  while (mpz_sgn1(v) != 0) /* i.e., while v != 0 */
  {
    mpz_div(q, u, v);
    mpz_mod(rr, u, v);
    mpz_set(u, v);
    mpz_set(v, rr);
    mpz_set(u0, u2);
    mpz_set(v0, v2);
    mpz_mul(u2, u2, q); mpz_sub(u2, u1, u2); /* u2 = u1 - q * u2 */
    mpz_mul(v2, v2, q); mpz_sub(v2, v1, v2); /* v2 = v1 - q * v2 */
    mpz_set(u1, u0);
    mpz_set(v1, v0);
  }
 
  while (mpz_sgn1(u1) < 0) /* i.e., while u1 < 0 */
  {
    /* we add 2^m = (2^m - 1) + 1 to u1: */
    mpz_add_ui(u1, u1, r->mod2mMask);
    mpz_add_ui(u1, u1, 1);
  }
  s = mpz_get_ui(u1); /* now: 0 <= s <= 2^m - 1 */
 
  mpz_clear(u);  omFreeBinAddr((ADDRESS)u);
  mpz_clear(u0); omFreeBinAddr((ADDRESS)u0);
  mpz_clear(u1); omFreeBinAddr((ADDRESS)u1);
  mpz_clear(u2); omFreeBinAddr((ADDRESS)u2);
  mpz_clear(v);  omFreeBinAddr((ADDRESS)v);
  mpz_clear(v0); omFreeBinAddr((ADDRESS)v0);
  mpz_clear(v1); omFreeBinAddr((ADDRESS)v1);
  mpz_clear(v2); omFreeBinAddr((ADDRESS)v2);
  mpz_clear(q); omFreeBinAddr((ADDRESS)q);
  mpz_clear(rr); omFreeBinAddr((ADDRESS)rr);
}

Variable Documentation

gmp_nrz_bin

EXTERN_VAR omBin gmp_nrz_bin

Definition at line 73 of file rmodulo2m.cc.