longrat.h File Reference

#include "misc/auxiliary.h"
#include "coeffs/si_gmp.h"
#include "coeffs/coeffs.h"
#include "factory/si_log2.h"

Go to the source code of this file.

Data Structures
struct	number
	'SR_INT' is the type of those integers small enough to fit into 29 bits. More...

Macros
#define	SR_HDL(A)   ((long)(A))
#define	SR_INT   1L
#define	INT_TO_SR(INT)   ((number) (((long)INT << 2) + SR_INT))
#define	SR_TO_INT(SR)   (((long)SR) >> 2)
#define	MP_SMALL   1

Functions
number	nlGetDenom (number &n, const coeffs r)
number	nlGetNumerator (number &n, const coeffs r)
BOOLEAN	nlInitChar (coeffs, void *)
static FORCE_INLINE int	nlQlogSize (number n, const coeffs r)
	only used by slimgb (tgb.cc)
static FORCE_INLINE BOOLEAN	nlIsInteger (number q, const coeffs r)
void	nlMPZ (mpz_t m, number &n, const coeffs r)
	get numerator as mpz_t
void	nlMPZ2 (mpz_t m, number &n, const coeffs r)
	get demoninator as mpz_t
number	nlModP (number q, const coeffs Q, const coeffs Zp)
void	nlNormalize (number &x, const coeffs r)
void	nlInpGcd (number &a, number b, const coeffs r)
void	nlDelete (number *a, const coeffs r)
number	nlInit2 (int i, int j, const coeffs r)
	create a rational i/j (implicitly) over Q NOTE: make sure to use correct Q in debug mode
number	nlInit2gmp (mpz_t i, mpz_t j, const coeffs r)
	create a rational i/j (implicitly) over Q NOTE: make sure to use correct Q in debug mode
number	nlChineseRemainderSym (number *x, number *q, int rl, BOOLEAN sym, CFArray &inv_cache, const coeffs CF)

---

Data Structure Documentation

snumber

struct snumber

'SR_INT' is the type of those integers small enough to fit into 29 bits.

Therefore the value range of this small integers is: $-2^{28}...2^{28}-1$.

Small integers are represented by an immediate integer handle, containing the value instead of pointing to it, which has the following form:

+-------+-------+-------+-------+- - - -+-------+-------+-------+
| guard | sign  | bit   | bit   |       | bit   | tag   | tag   |
| bit   | bit   | 27    | 26    |       | 0     | 0     | 1     |
+-------+-------+-------+-------+- - - -+-------+-------+-------+

Immediate integers handles carry the tag 'SR_INT', i.e. the last bit is 1. This distinguishes immediate integers from other handles which point to structures aligned on 4 byte boundaries and therefore have last bit zero. (The second bit is reserved as tag to allow extensions of this scheme.) Using immediates as pointers and dereferencing them gives address errors.

To aid overflow check the most significant two bits must always be equal, that is to say that the sign bit of immediate integers has a guard bit.

The macros 'INT_TO_SR' and 'SR_TO_INT' should be used to convert between a small integer value and its representation as immediate integer handle.

Large integers and rationals are represented by z and n where n may be undefined (if s==3) NULL represents only deleted values

Definition at line 48 of file longrat.h.

Data Fields
int	debug
mpz_t	n
BOOLEAN	s	parameter s in number: 0 (or FALSE): not normalised rational 1 (or TRUE): normalised rational 3 : integer with n==NULL
mpz_t	z

Macro Definition Documentation

INT_TO_SR

#define INT_TO_SR

(

INT

)

((number) (((long)INT << 2) + SR_INT))

Definition at line 68 of file longrat.h.

MP_SMALL

#define MP_SMALL   1

Definition at line 71 of file longrat.h.

SR_HDL

#define SR_HDL

(

A

)

((long)(A))

Definition at line 65 of file longrat.h.

SR_INT

#define SR_INT   1L

Definition at line 67 of file longrat.h.

SR_TO_INT

#define SR_TO_INT

(

SR

)

(((long)SR) >> 2)

Definition at line 69 of file longrat.h.

Function Documentation

nlChineseRemainderSym()

number nlChineseRemainderSym	(	number *	x,
		number *	q,
		int	rl,
		BOOLEAN	sym,
		CFArray &	inv_cache,
		const coeffs	CF
	)

Definition at line 3075 of file longrat.cc.

{
  setCharacteristic( 0 ); // only in char 0
  Off(SW_RATIONAL);
  CFArray X(rl), Q(rl);
  int i;
  for(i=rl-1;i>=0;i--)
  {
    X[i]=CF->convSingNFactoryN(x[i],FALSE,CF); // may be larger MAX_INT
    Q[i]=CF->convSingNFactoryN(q[i],FALSE,CF); // may be larger MAX_INT
  }
  CanonicalForm xnew,qnew;
  if (n_SwitchChinRem)
    chineseRemainder(X,Q,xnew,qnew);
  else
    chineseRemainderCached(X,Q,xnew,qnew,inv_cache);
  number n=CF->convFactoryNSingN(xnew,CF);
  if (sym)
  {
    number p=CF->convFactoryNSingN(qnew,CF);
    number p2;
    if (getCoeffType(CF) == n_Q) p2=nlIntDiv(p,nlInit(2, CF),CF);
    else                         p2=CF->cfDiv(p,CF->cfInit(2, CF),CF);
    if (CF->cfGreater(n,p2,CF))
    {
       number n2=CF->cfSub(n,p,CF);
       CF->cfDelete(&n,CF);
       n=n2;
    }
    CF->cfDelete(&p2,CF);
    CF->cfDelete(&p,CF);
  }
  CF->cfNormalize(n,CF);
  return n;
}

nlDelete()

void nlDelete	(	number *	a,
		const coeffs	r
	)

Definition at line 2637 of file longrat.cc.

{
  if (*a!=NULL)
  {
    nlTest(*a, r);
    if ((SR_HDL(*a) & SR_INT)==0)
    {
      _nlDelete_NoImm(a);
    }
    *a=NULL;
  }
}

nlGetDenom()

number nlGetDenom	(	number &	n,
		const coeffs	r
	)

Definition at line 1613 of file longrat.cc.

{
  if (!(SR_HDL(n) & SR_INT))
  {
    if (n->s==0)
    {
      nlNormalize(n,r);
    }
    if (!(SR_HDL(n) & SR_INT))
    {
      if (n->s!=3)
      {
        number u=ALLOC_RNUMBER();
        u->s=3;
#if defined(LDEBUG)
        u->debug=123456;
#endif
        mpz_init_set(u->z,n->n);
        u=nlShort3_noinline(u);
        return u;
      }
    }
  }
  return INT_TO_SR(1);
}

nlGetNumerator()

number nlGetNumerator	(	number &	n,
		const coeffs	r
	)

Definition at line 1642 of file longrat.cc.

{
  if (!(SR_HDL(n) & SR_INT))
  {
    if (n->s==0)
    {
      nlNormalize(n,r);
    }
    if (!(SR_HDL(n) & SR_INT))
    {
      number u=ALLOC_RNUMBER();
#if defined(LDEBUG)
      u->debug=123456;
#endif
      u->s=3;
      mpz_init_set(u->z,n->z);
      if (n->s!=3)
      {
        u=nlShort3_noinline(u);
      }
      return u;
    }
  }
  return n; // imm. int
}

nlInit2()

number nlInit2	(	int	i,
		int	j,
		const coeffs	r
	)

create a rational i/j (implicitly) over Q NOTE: make sure to use correct Q in debug mode

Definition at line 2515 of file longrat.cc.

{
  number z=ALLOC_RNUMBER();
#if defined(LDEBUG)
  z->debug=123456;
#endif
  mpz_init_set_si(z->z,(long)i);
  mpz_init_set_si(z->n,(long)j);
  z->s = 0;
  nlNormalize(z,r);
  return z;
}

nlInit2gmp()

number nlInit2gmp	(	mpz_t	i,
		mpz_t	j,
		const coeffs	r
	)

create a rational i/j (implicitly) over Q NOTE: make sure to use correct Q in debug mode

Definition at line 2528 of file longrat.cc.

{
  number z=ALLOC_RNUMBER();
#if defined(LDEBUG)
  z->debug=123456;
#endif
  mpz_init_set(z->z,i);
  mpz_init_set(z->n,j);
  z->s = 0;
  nlNormalize(z,r);
  return z;
}

nlInitChar()

BOOLEAN nlInitChar	(	coeffs	r,
		void *	p
	)

Definition at line 3559 of file longrat.cc.

{
  r->is_domain=TRUE;
  r->rep=n_rep_gap_rat;
 
  r->nCoeffIsEqual=nlCoeffIsEqual;
  //r->cfKillChar = ndKillChar; /* dummy */
  //r->cfCoeffString=nlCoeffString;
  r->cfCoeffName=nlCoeffName;
 
  r->cfInitMPZ = nlInitMPZ;
  r->cfMPZ  = nlMPZ;
 
  r->cfMult  = nlMult;
  r->cfSub   = nlSub;
  r->cfAdd   = nlAdd;
  r->cfExactDiv= nlExactDiv;
  if (p==NULL) /* Q */
  {
    r->is_field=TRUE;
    r->cfDiv   = nlDiv;
    //r->cfGcd  = ndGcd_dummy;
    r->cfSubringGcd  = nlGcd;
  }
  else /* Z: coeffs_BIGINT */
  {
    r->is_field=FALSE;
    r->cfDiv   = nlIntDiv;
    r->cfIntMod= nlIntMod;
    r->cfGcd  = nlGcd;
    r->cfDivBy=nlDivBy;
    r->cfDivComp = nlDivComp;
    r->cfIsUnit = nlIsUnit;
    r->cfGetUnit = nlGetUnit;
    r->cfQuot1 = nlQuot1;
    r->cfLcm = nlLcm;
    r->cfXExtGcd=nlXExtGcd;
    r->cfQuotRem=nlQuotRem;
  }
  r->cfInit = nlInit;
  r->cfSize  = nlSize;
  r->cfInt  = nlInt;
 
  r->cfChineseRemainder=nlChineseRemainderSym;
  r->cfFarey=nlFarey;
  r->cfInpNeg   = nlNeg;
  r->cfInvers= nlInvers;
  r->cfCopy  = nlCopy;
  r->cfRePart = nlCopy;
  //r->cfImPart = ndReturn0;
  r->cfWriteLong = nlWrite;
  r->cfRead = nlRead;
  r->cfNormalize=nlNormalize;
  r->cfGreater = nlGreater;
  r->cfEqual = nlEqual;
  r->cfIsZero = nlIsZero;
  r->cfIsOne = nlIsOne;
  r->cfIsMOne = nlIsMOne;
  r->cfGreaterZero = nlGreaterZero;
  r->cfPower = nlPower;
  r->cfGetDenom = nlGetDenom;
  r->cfGetNumerator = nlGetNumerator;
  r->cfExtGcd = nlExtGcd; // only for ring stuff and Z
  r->cfNormalizeHelper  = nlNormalizeHelper;
  r->cfDelete= nlDelete;
  r->cfSetMap = nlSetMap;
  //r->cfName = ndName;
  r->cfInpMult=nlInpMult;
  r->cfInpAdd=nlInpAdd;
  //r->cfCoeffWrite=nlCoeffWrite;
 
  r->cfClearContent = nlClearContent;
  r->cfClearDenominators = nlClearDenominators;
 
#ifdef LDEBUG
  // debug stuff
  r->cfDBTest=nlDBTest;
#endif
  r->convSingNFactoryN=nlConvSingNFactoryN;
  r->convFactoryNSingN=nlConvFactoryNSingN;
 
  r->cfRandom=nlRandom;
 
  // io via ssi
  r->cfWriteFd=nlWriteFd;
  r->cfWriteFd_S=nlWriteFd_S;
  r->cfReadFd=nlReadFd;
  r->cfReadFd_S=nlReadFd_S;
 
  //r->type = n_Q;
  r->ch = 0;
  r->has_simple_Alloc=FALSE;
  r->has_simple_Inverse=FALSE;
 
  // variables for this type of coeffs:
  // (none)
  return FALSE;
}

nlInpGcd()

void nlInpGcd	(	number &	a,
		number	b,
		const coeffs	r
	)

Definition at line 2913 of file longrat.cc.

{
  if ((SR_HDL(b)|SR_HDL(a))&SR_INT)
  {
    number n=nlGcd(a,b,r);
    nlDelete(&a,r);
    a=n;
  }
  else
  {
    mpz_gcd(a->z,a->z,b->z);
    a=nlShort3_noinline(a);
  }
}

nlIsInteger()

static FORCE_INLINE BOOLEAN nlIsInteger ( number  q, const coeffs  r  )

static

Definition at line 94 of file longrat.h.

{
  assume( nCoeff_is_Q (r) );
  n_Test(q, r);
 
  if (SR_HDL(q) & SR_INT)
    return TRUE; // immediate int
 
  return ( q->s == 3 );
}

nlModP()

number nlModP	(	number	q,
		const coeffs	Q,
		const coeffs	Zp
	)

Definition at line 1572 of file longrat.cc.

{
  const int p = n_GetChar(Zp);
  assume( p > 0 );
 
  const long P = p;
  assume( P > 0 );
 
  // embedded long within q => only long numerator has to be converted
  // to int (modulo char.)
  if (SR_HDL(q) & SR_INT)
  {
    long i = SR_TO_INT(q);
    return n_Init( i, Zp );
  }
 
  const unsigned long PP = p;
 
  // numerator modulo char. should fit into int
  number z = n_Init( static_cast<long>(mpz_fdiv_ui(q->z, PP)), Zp );
 
  // denominator != 1?
  if (q->s!=3)
  {
    // denominator modulo char. should fit into int
    number n = n_Init( static_cast<long>(mpz_fdiv_ui(q->n, PP)), Zp );
 
    number res = n_Div( z, n, Zp );
 
    n_Delete(&z, Zp);
    n_Delete(&n, Zp);
 
    return res;
  }
 
  return z;
}

nlMPZ()

void nlMPZ	(	mpz_t	m,
		number &	n,
		const coeffs	r
	)

get numerator as mpz_t

Definition at line 2790 of file longrat.cc.

{
  nlTest(n, r);
  nlNormalize(n, r);
  if (SR_HDL(n) & SR_INT) mpz_init_set_si(m, SR_TO_INT(n));     /* n fits in an int */
  else             mpz_init_set(m, (mpz_ptr)n->z);
}

nlMPZ2()

void nlMPZ2	(	mpz_t	m,
		number &	n,
		const coeffs	r
	)

get demoninator as mpz_t

Definition at line 2798 of file longrat.cc.

{
  nlTest(n, r);
  nlNormalize(n, r);
  if (SR_HDL(n) & SR_INT) mpz_init_set_si(m,1); /* small int*/
  else if (n->s==3)       mpz_init_set_si(m,1); /* large int*/
  else                    mpz_init_set(m, (mpz_ptr)n->n);
}

nlNormalize()

void nlNormalize	(	number &	x,
		const coeffs	r
	)

Definition at line 1481 of file longrat.cc.

{
  if ((SR_HDL(x) & SR_INT) ||(x==NULL))
    return;
  if (x->s==3)
  {
    x=nlShort3_noinline(x);
    nlTest(x,r);
    return;
  }
  else if (x->s==0)
  {
    if (mpz_cmp_si(x->n,1L)==0)
    {
      mpz_clear(x->n);
      x->s=3;
      x=nlShort3(x);
    }
    else
    {
      mpz_t gcd;
      mpz_init(gcd);
      mpz_gcd(gcd,x->z,x->n);
      x->s=1;
      if (mpz_cmp_si(gcd,1L)!=0)
      {
        mpz_divexact(x->z,x->z,gcd);
        mpz_divexact(x->n,x->n,gcd);
        if (mpz_cmp_si(x->n,1L)==0)
        {
          mpz_clear(x->n);
          x->s=3;
          x=nlShort3_noinline(x);
        }
      }
      mpz_clear(gcd);
    }
  }
  nlTest(x, r);
}

nlQlogSize()

static FORCE_INLINE int nlQlogSize ( number  n, const coeffs  r  )

static

only used by slimgb (tgb.cc)

Definition at line 76 of file longrat.h.

{
  assume( nCoeff_is_Q (r) );
 
  if(SR_HDL(n)&SR_INT)
  {
    if (SR_HDL(n)==SR_INT) return 0;
    long i = SR_TO_INT (n);
    unsigned long v;
    v = ABS(i);
    return SI_LOG2_LONG(v) + 1;
  }
  //assume denominator is 0
  number nn=(number) n;
  return mpz_sizeinbase (nn->z, 2);
}