algext.cc File Reference

#include "misc/auxiliary.h"
#include "reporter/reporter.h"
#include "coeffs/coeffs.h"
#include "coeffs/numbers.h"
#include "coeffs/longrat.h"
#include "polys/monomials/ring.h"
#include "polys/monomials/p_polys.h"
#include "polys/simpleideals.h"
#include "polys/PolyEnumerator.h"
#include "factory/factory.h"
#include "polys/clapconv.h"
#include "polys/clapsing.h"
#include "polys/prCopy.h"
#include "polys/ext_fields/algext.h"
#include "polys/ext_fields/transext.h"

Go to the source code of this file.

Macros
#define	TRANSEXT_PRIVATES   1
	ABSTRACT: numbers in an algebraic extension field K[a] / < f(a) > Assuming that we have a coeffs object cf, then these numbers are polynomials in the polynomial ring K[a] represented by cf->extRing. More...
#define	naTest(a)   naDBTest(a,__FILE__,__LINE__,cf)
#define	naRing   cf->extRing
#define	naCoeffs   cf->extRing->cf
#define	naMinpoly   naRing->qideal->m[0]
#define	n2pTest(a)   n2pDBTest(a,__FILE__,__LINE__,cf)
	ABSTRACT: numbers as polys in the ring K[a] Assuming that we have a coeffs object cf, then these numbers are polynomials in the polynomial ring K[a] represented by cf->extRing. More...
#define	n2pRing   cf->extRing
#define	n2pCoeffs   cf->extRing->cf

Functions
BOOLEAN	naDBTest (number a, const char *f, const int l, const coeffs r)
BOOLEAN	naGreaterZero (number a, const coeffs cf)
	forward declarations More...
BOOLEAN	naGreater (number a, number b, const coeffs cf)
BOOLEAN	naEqual (number a, number b, const coeffs cf)
BOOLEAN	naIsOne (number a, const coeffs cf)
BOOLEAN	naIsMOne (number a, const coeffs cf)
number	naInit (long i, const coeffs cf)
number	naNeg (number a, const coeffs cf)
	this is in-place, modifies a More...
number	naInvers (number a, const coeffs cf)
number	naAdd (number a, number b, const coeffs cf)
number	naSub (number a, number b, const coeffs cf)
number	naMult (number a, number b, const coeffs cf)
number	naDiv (number a, number b, const coeffs cf)
void	naPower (number a, int exp, number *b, const coeffs cf)
number	naCopy (number a, const coeffs cf)
void	naWriteLong (number a, const coeffs cf)
void	naWriteShort (number a, const coeffs cf)
number	naGetDenom (number &a, const coeffs cf)
number	naGetNumerator (number &a, const coeffs cf)
number	naGcd (number a, number b, const coeffs cf)
void	naDelete (number *a, const coeffs cf)
void	naCoeffWrite (const coeffs cf, BOOLEAN details)
const char *	naRead (const char *s, number *a, const coeffs cf)
static BOOLEAN	naCoeffIsEqual (const coeffs cf, n_coeffType n, void *param)
static void	p_Monic (poly p, const ring r)
	returns NULL if p == NULL, otherwise makes p monic by dividing by its leading coefficient (only done if this is not already 1); this assumes that we are over a ground field so that division is well-defined; modifies p More...
static poly	p_GcdHelper (poly &p, poly &q, const ring r)
	see p_Gcd; additional assumption: deg(p) >= deg(q); must destroy p and q (unless one of them is returned) More...
static poly	p_Gcd (const poly p, const poly q, const ring r)
static poly	p_ExtGcdHelper (poly &p, poly &pFactor, poly &q, poly &qFactor, ring r)
poly	p_ExtGcd (poly p, poly &pFactor, poly q, poly &qFactor, ring r)
	assumes that p and q are univariate polynomials in r, mentioning the same variable; assumes a global monomial ordering in r; assumes that not both p and q are NULL; returns the gcd of p and q; moreover, afterwards pFactor and qFactor contain appropriate factors such that gcd(p, q) = p * pFactor + q * qFactor; leaves p and q unmodified More...
void	heuristicReduce (poly &p, poly reducer, const coeffs cf)
void	definiteReduce (poly &p, poly reducer, const coeffs cf)
static coeffs	nCoeff_bottom (const coeffs r, int &height)
BOOLEAN	naIsZero (number a, const coeffs cf)
static number	naInitMPZ (mpz_t m, const coeffs r)
long	naInt (number &a, const coeffs cf)
number	napNormalizeHelper (number b, const coeffs cf)
number	naLcmContent (number a, number b, const coeffs cf)
int	naSize (number a, const coeffs cf)
void	naNormalize (number &a, const coeffs cf)
number	naConvFactoryNSingN (const CanonicalForm n, const coeffs cf)
CanonicalForm	naConvSingNFactoryN (number n, BOOLEAN, const coeffs cf)
number	naMap00 (number a, const coeffs src, const coeffs dst)
number	naMapZ0 (number a, const coeffs src, const coeffs dst)
number	naMapP0 (number a, const coeffs src, const coeffs dst)
number	naCopyTrans2AlgExt (number a, const coeffs src, const coeffs dst)
number	naMap0P (number a, const coeffs src, const coeffs dst)
number	naMapPP (number a, const coeffs src, const coeffs dst)
number	naMapUP (number a, const coeffs src, const coeffs dst)
number	naGenMap (number a, const coeffs cf, const coeffs dst)
number	naGenTrans2AlgExt (number a, const coeffs cf, const coeffs dst)
nMapFunc	naSetMap (const coeffs src, const coeffs dst)
	Get a mapping function from src into the domain of this type (n_algExt) More...
int	naParDeg (number a, const coeffs cf)
number	naParameter (const int iParameter, const coeffs cf)
	return the specified parameter as a number in the given alg. field More...
int	naIsParam (number m, const coeffs cf)
	if m == var(i)/1 => return i, More...
static void	naClearContent (ICoeffsEnumerator &numberCollectionEnumerator, number &c, const coeffs cf)
void	naClearDenominators (ICoeffsEnumerator &numberCollectionEnumerator, number &c, const coeffs cf)
void	naKillChar (coeffs cf)
char *	naCoeffName (const coeffs r)
number	naChineseRemainder (number *x, number *q, int rl, BOOLEAN, CFArray &inv_cache, const coeffs cf)
number	naFarey (number p, number n, const coeffs cf)
BOOLEAN	naInitChar (coeffs cf, void *infoStruct)
	Initialize the coeffs object. More...
BOOLEAN	n2pDBTest (number a, const char *f, const int l, const coeffs r)
void	n2pNormalize (number &a, const coeffs cf)
number	n2pMult (number a, number b, const coeffs cf)
number	n2pDiv (number a, number b, const coeffs cf)
void	n2pPower (number a, int exp, number *b, const coeffs cf)
const char *	n2pRead (const char *s, number *a, const coeffs cf)
static BOOLEAN	n2pCoeffIsEqual (const coeffs cf, n_coeffType n, void *param)
char *	n2pCoeffName (const coeffs cf)
void	n2pCoeffWrite (const coeffs cf, BOOLEAN details)
number	n2pInvers (number a, const coeffs cf)
BOOLEAN	n2pInitChar (coeffs cf, void *infoStruct)

Macro Definition Documentation

n2pCoeffs

#define n2pCoeffs   cf->extRing->cf

Definition at line 1508 of file algext.cc.

n2pRing

#define n2pRing   cf->extRing

Definition at line 1502 of file algext.cc.

n2pTest

#define n2pTest

(

a

)

n2pDBTest(a,__FILE__,__LINE__,cf)

ABSTRACT: numbers as polys in the ring K[a] Assuming that we have a coeffs object cf, then these numbers are polynomials in the polynomial ring K[a] represented by cf->extRing.

IMPORTANT ASSUMPTIONS: 1.) So far we assume that cf->extRing is a valid polynomial ring

Definition at line 1495 of file algext.cc.

naCoeffs

#define naCoeffs   cf->extRing->cf

Definition at line 67 of file algext.cc.

naMinpoly

#define naMinpoly   naRing->qideal->m[0]

Definition at line 70 of file algext.cc.

naRing

#define naRing   cf->extRing

Definition at line 61 of file algext.cc.

naTest

#define naTest

(

a

)

naDBTest(a,__FILE__,__LINE__,cf)

Definition at line 54 of file algext.cc.

TRANSEXT_PRIVATES

#define TRANSEXT_PRIVATES   1

ABSTRACT: numbers in an algebraic extension field K[a] / < f(a) > Assuming that we have a coeffs object cf, then these numbers are polynomials in the polynomial ring K[a] represented by cf->extRing.

IMPORTANT ASSUMPTIONS: 1.) So far we assume that cf->extRing is a valid polynomial ring in exactly one variable, i.e., K[a], where K is allowed 0* to be any field (representable in SINGULAR and which may itself be some extension field, thus allowing for extension towers). 2.) Moreover, this implementation assumes that cf->extRing->qideal is not NULL but an ideal with at least one non-zero generator which may be accessed by cf->extRing->qideal->m[0] and which represents the minimal polynomial f(a) of the extension variable 'a' in K[a]. 3.) As soon as an std method for polynomial rings becomes availabe, all reduction steps modulo f(a) should be replaced by a call to std. Moreover, in this situation one can finally move from K[a] / < f(a) > to K[a_1, ..., a_s] / I, with I some zero-dimensional ideal in K[a_1, ..., a_s] given by a lex Gröbner basis. The code in algext.h and algext.cc is then capable of computing in K[a_1, ..., a_s] / I.

Definition at line 50 of file algext.cc.

Function Documentation

definiteReduce()

void definiteReduce	(	poly &	p,
		poly	reducer,
		const coeffs	cf
	)

Definition at line 735 of file algext.cc.

{
  #ifdef LDEBUG
  p_Test((poly)p, naRing);
  p_Test((poly)reducer, naRing);
  #endif
  if ((p!=NULL) && (p_GetExp(p,1,naRing)>=p_GetExp(reducer,1,naRing)))
  {
    p_PolyDiv(p, reducer, FALSE, naRing);
  }
}

heuristicReduce()

void heuristicReduce	(	poly &	p,
		poly	reducer,
		const coeffs	cf
	)

Definition at line 565 of file algext.cc.

{
  #ifdef LDEBUG
  p_Test((poly)p, naRing);
  p_Test((poly)reducer, naRing);
  #endif
  if (p_Totaldegree(p, naRing) > 10 * p_Totaldegree(reducer, naRing))
    definiteReduce(p, reducer, cf);
}

n2pCoeffIsEqual()

static BOOLEAN n2pCoeffIsEqual ( const coeffs  cf, n_coeffType  n, void *  param  )

static

Definition at line 1558 of file algext.cc.

{
  if (n_polyExt != n) return FALSE;
  AlgExtInfo *e = (AlgExtInfo *)param;
  /* for extension coefficient fields we expect the underlying
     polynomial rings to be IDENTICAL, i.e. the SAME OBJECT;
     this expectation is based on the assumption that we have properly
     registered cf and perform reference counting rather than creating
     multiple copies of the same coefficient field/domain/ring */
  if (n2pRing == e->r)
    return TRUE;
  // NOTE: Q(a)[x] && Q(a)[y] should better share the _same_ Q(a)...
  if( rEqual(n2pRing, e->r, TRUE) ) // also checks the equality of qideals
  {
    rDelete(e->r);
    return TRUE;
  }
  return FALSE;
}

n2pCoeffName()

char * n2pCoeffName

(

const coeffs

cf

)

Definition at line 1578 of file algext.cc.

{
  const char* const* p=n_ParameterNames(cf);
  int l=0;
  int i;
  for(i=0; i<rVar(n2pRing);i++)
  {
    l+=(strlen(p[i])+1);
  }
  char *cf_s=nCoeffName(n2pRing->cf);
  STATIC_VAR char s[200];
  s[0]='\0';
  snprintf(s,strlen(cf_s)+2,"%s",cf_s);
  char tt[2];
  tt[0]='[';
  tt[1]='\0';
  strcat(s,tt);
  tt[0]=',';
  for(i=0; i<rVar(n2pRing);i++)
  {
    strcat(s,p[i]);
    if (i+1!=rVar(n2pRing)) strcat(s,tt);
    else { tt[0]=']'; strcat(s,tt); }
  }
  return s;
}

n2pCoeffWrite()

void n2pCoeffWrite	(	const coeffs	cf,
		BOOLEAN	details
	)

Definition at line 1605 of file algext.cc.

{
  assume( cf != NULL );
 
  const ring A = cf->extRing;
 
  assume( A != NULL );
  PrintS("// polynomial ring as coefficient ring :\n");
  rWrite(A);
  PrintLn();
}

n2pDBTest()

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

Definition at line 1511 of file algext.cc.

{
  if (a == NULL) return TRUE;
  return p_Test((poly)a, n2pRing);
}

n2pDiv()

number n2pDiv	(	number	a,
		number	b,
		const coeffs	cf
	)

Definition at line 1533 of file algext.cc.

{
  n2pTest(a); n2pTest(b);
  if (b == NULL) WerrorS(nDivBy0);
  if (a == NULL) return NULL;
  poly p=singclap_pdivide((poly)a,(poly)b,n2pRing);
  return (number)p;
}

n2pInitChar()

BOOLEAN n2pInitChar	(	coeffs	cf,
		void *	infoStruct
	)

first check whether cf->extRing != NULL and delete old ring???

Definition at line 1633 of file algext.cc.

{
  assume( infoStruct != NULL );
 
  AlgExtInfo *e = (AlgExtInfo *)infoStruct;
  /// first check whether cf->extRing != NULL and delete old ring???
 
  assume(e->r                     != NULL);      // extRing;
  assume(e->r->cf                 != NULL);      // extRing->cf;
 
  assume( cf != NULL );
 
  rIncRefCnt(e->r); // increase the ref.counter for the ground poly. ring!
  const ring R = e->r; // no copy!
  cf->extRing  = R;
 
  /* propagate characteristic up so that it becomes
     directly accessible in cf: */
  cf->ch = R->cf->ch;
  cf->is_field=FALSE;
  cf->is_domain=TRUE;
 
  cf->cfCoeffName    = n2pCoeffName;
 
  cf->cfGreaterZero  = naGreaterZero;
  cf->cfGreater      = naGreater;
  cf->cfEqual        = naEqual;
  cf->cfIsZero       = naIsZero;
  cf->cfIsOne        = naIsOne;
  cf->cfIsMOne       = naIsMOne;
  cf->cfInit         = naInit;
  cf->cfInitMPZ      = naInitMPZ;
  cf->cfFarey        = naFarey;
  cf->cfChineseRemainder= naChineseRemainder;
  cf->cfInt          = naInt;
  cf->cfInpNeg       = naNeg;
  cf->cfAdd          = naAdd;
  cf->cfSub          = naSub;
  cf->cfMult         = n2pMult;
  cf->cfDiv          = n2pDiv;
  cf->cfPower        = n2pPower;
  cf->cfCopy         = naCopy;
 
  cf->cfWriteLong        = naWriteLong;
 
  if( rCanShortOut(n2pRing) )
    cf->cfWriteShort = naWriteShort;
  else
    cf->cfWriteShort = naWriteLong;
 
  cf->cfRead         = n2pRead;
  cf->cfDelete       = naDelete;
  cf->cfSetMap       = naSetMap;
  cf->cfGetDenom     = naGetDenom;
  cf->cfGetNumerator = naGetNumerator;
  cf->cfRePart       = naCopy;
  cf->cfCoeffWrite   = n2pCoeffWrite;
  cf->cfNormalize    = n2pNormalize;
  cf->cfKillChar     = naKillChar;
#ifdef LDEBUG
  cf->cfDBTest       = naDBTest;
#endif
  cf->cfGcd          = naGcd;
  cf->cfNormalizeHelper          = naLcmContent;
  cf->cfSize         = naSize;
  cf->nCoeffIsEqual  = n2pCoeffIsEqual;
  cf->cfInvers       = n2pInvers;
  cf->convFactoryNSingN=naConvFactoryNSingN;
  cf->convSingNFactoryN=naConvSingNFactoryN;
  cf->cfParDeg = naParDeg;
 
  cf->iNumberOfParameters = rVar(R);
  cf->pParameterNames = (const char**)R->names;
  cf->cfParameter = naParameter;
  cf->has_simple_Inverse=FALSE;
  /* cf->has_simple_Alloc= FALSE; */
 
  if( nCoeff_is_Q(R->cf) )
  {
    cf->cfClearContent = naClearContent;
    cf->cfClearDenominators = naClearDenominators;
  }
 
  return FALSE;
}

n2pInvers()

number n2pInvers	(	number	a,
		const coeffs	cf
	)

Definition at line 1617 of file algext.cc.

{
  poly aa=(poly)a;
  if(p_IsConstant(aa, n2pRing))
  {
    poly p=p_Init(n2pRing);
    p_SetCoeff0(p,n_Invers(pGetCoeff(aa),n2pCoeffs),n2pRing);
    return (number)p;
  }
  else
  {
    WerrorS("not invertible");
    return NULL;
  }
}

n2pMult()

number n2pMult	(	number	a,
		number	b,
		const coeffs	cf
	)

Definition at line 1525 of file algext.cc.

{
  n2pTest(a); n2pTest(b);
  if ((a == NULL)||(b == NULL)) return NULL;
  poly aTimesB = pp_Mult_qq((poly)a, (poly)b, n2pRing);
  return (number)aTimesB;
}

n2pNormalize()

void n2pNormalize	(	number &	a,
		const coeffs	cf
	)

Definition at line 1518 of file algext.cc.

{
  poly aa=(poly)a;
  p_Normalize(aa,n2pRing);
}

n2pPower()

void n2pPower	(	number	a,
		int	exp,
		number *	b,
		const coeffs	cf
	)

Definition at line 1542 of file algext.cc.

{
  n2pTest(a);
 
  *b= (number)p_Power((poly)a,exp,n2pRing);
}

n2pRead()

const char * n2pRead	(	const char *	s,
		number *	a,
		const coeffs	cf
	)

Definition at line 1549 of file algext.cc.

{
  poly aAsPoly;
  const char * result = p_Read(s, aAsPoly, n2pRing);
  *a = (number)aAsPoly;
  return result;
}

naAdd()

number naAdd	(	number	a,
		number	b,
		const coeffs	cf
	)

Definition at line 442 of file algext.cc.

{
  naTest(a); naTest(b);
  if (a == NULL) return naCopy(b, cf);
  if (b == NULL) return naCopy(a, cf);
  poly aPlusB = p_Add_q(p_Copy((poly)a, naRing),
                        p_Copy((poly)b, naRing), naRing);
  //definiteReduce(aPlusB, naMinpoly, cf);
  return (number)aPlusB;
}

naChineseRemainder()

number naChineseRemainder	(	number *	x,
		number *	q,
		int	rl,
		BOOLEAN	,
		CFArray &	inv_cache,
		const coeffs	cf
	)

Definition at line 1358 of file algext.cc.

{
  poly *P=(poly*)omAlloc(rl*sizeof(poly*));
  number *X=(number *)omAlloc(rl*sizeof(number));
  int i;
  for(i=0;i<rl;i++) P[i]=p_Copy((poly)(x[i]),cf->extRing);
  poly result=p_ChineseRemainder(P,X,q,rl,inv_cache,cf->extRing);
  omFreeSize(X,rl*sizeof(number));
  omFreeSize(P,rl*sizeof(poly*));
  return ((number)result);
}

naClearContent()

static void naClearContent ( ICoeffsEnumerator &  numberCollectionEnumerator, number &  c, const coeffs  cf  )

static

Definition at line 1107 of file algext.cc.

{
  assume(cf != NULL);
  assume(getCoeffType(cf) == n_algExt);
  assume(nCoeff_is_Q_algext(cf)); // only over (Q[a]/m(a)), while the default impl. is used over Zp[a]/m(a) !
 
  const ring   R = cf->extRing;
  assume(R != NULL);
  const coeffs Q = R->cf;
  assume(Q != NULL);
  assume(nCoeff_is_Q(Q));
 
  numberCollectionEnumerator.Reset();
 
  if( !numberCollectionEnumerator.MoveNext() ) // empty zero polynomial?
  {
    c = n_Init(1, cf);
    return;
  }
 
  naTest(numberCollectionEnumerator.Current());
 
  // part 1, find a small candidate for gcd
  int s1; int s=2147483647; // max. int
 
  const BOOLEAN lc_is_pos=naGreaterZero(numberCollectionEnumerator.Current(),cf);
 
  int normalcount = 0;
 
  poly cand1, cand;
 
  do
  {
    number& n = numberCollectionEnumerator.Current();
    naNormalize(n, cf); ++normalcount;
 
    naTest(n);
 
    cand1 = (poly)n;
 
    s1 = p_Deg(cand1, R); // naSize?
    if (s>s1)
    {
      cand = cand1;
      s = s1;
    }
  } while (numberCollectionEnumerator.MoveNext() );
 
//  assume( nlGreaterZero(cand,cf) ); // cand may be a negative integer!
 
  cand = p_Copy(cand, R);
  // part 2: compute gcd(cand,all coeffs)
 
  numberCollectionEnumerator.Reset();
 
  int length = 0;
  while (numberCollectionEnumerator.MoveNext() )
  {
    number& n = numberCollectionEnumerator.Current();
    ++length;
 
    if( (--normalcount) <= 0)
      naNormalize(n, cf);
 
    naTest(n);
 
//    p_InpGcd(cand, (poly)n, R);
 
    { // R->cf is QQ
      poly tmp=gcd_over_Q(cand,(poly)n,R);
      p_Delete(&cand,R);
      cand=tmp;
    }
 
//    cand1 = p_Gcd(cand,(poly)n, R); p_Delete(&cand, R); cand = cand1;
 
    assume( naGreaterZero((number)cand, cf) ); // ???
/*
    if(p_IsConstant(cand,R))
    {
      c = cand;
 
      if(!lc_is_pos)
      {
        // make the leading coeff positive
        c = nlNeg(c, cf);
        numberCollectionEnumerator.Reset();
 
        while (numberCollectionEnumerator.MoveNext() )
        {
          number& nn = numberCollectionEnumerator.Current();
          nn = nlNeg(nn, cf);
        }
      }
      return;
    }
*/
 
  }
 
 
  // part3: all coeffs = all coeffs / cand
  if (!lc_is_pos)
    cand = p_Neg(cand, R);
 
  c = (number)cand; naTest(c);
 
  poly cInverse = (poly)naInvers(c, cf);
  assume(cInverse != NULL); // c is non-zero divisor!?
 
 
  numberCollectionEnumerator.Reset();
 
 
  while (numberCollectionEnumerator.MoveNext() )
  {
    number& n = numberCollectionEnumerator.Current();
 
    assume( length > 0 );
 
    if( --length > 0 )
    {
      assume( cInverse != NULL );
      n = (number) p_Mult_q(p_Copy(cInverse, R), (poly)n, R);
    }
    else
    {
      n = (number) p_Mult_q(cInverse, (poly)n, R);
      cInverse = NULL;
      assume(length == 0);
    }
 
    definiteReduce((poly &)n, naMinpoly, cf);
  }
 
  assume(length == 0);
  assume(cInverse == NULL); //   p_Delete(&cInverse, R);
 
  // Quick and dirty fix for constant content clearing... !?
  CRecursivePolyCoeffsEnumerator<NAConverter> itr(numberCollectionEnumerator); // recursively treat the numbers as polys!
 
  number cc;
 
  n_ClearContent(itr, cc, Q); // TODO: get rid of (-LC) normalization!?
 
  // over alg. ext. of Q // takes over the input number
  c = (number) __p_Mult_nn( (poly)c, cc, R);
//      p_Mult_q(p_NSet(cc, R), , R);
 
  n_Delete(&cc, Q);
 
  // TODO: the above is not enough! need GCD's of polynomial coeffs...!
/*
  // old and wrong part of p_Content
    if (rField_is_Q_a(r) && !CLEARENUMERATORS) // should not be used anymore if CLEARENUMERATORS is 1
    {
      // we only need special handling for alg. ext.
      if (getCoeffType(r->cf)==n_algExt)
      {
        number hzz = n_Init(1, r->cf->extRing->cf);
        p=ph;
        while (p!=NULL)
        { // each monom: coeff in Q_a
          poly c_n_n=(poly)pGetCoeff(p);
          poly c_n=c_n_n;
          while (c_n!=NULL)
          { // each monom: coeff in Q
            d=n_NormalizeHelper(hzz,pGetCoeff(c_n),r->cf->extRing->cf);
            n_Delete(&hzz,r->cf->extRing->cf);
            hzz=d;
            pIter(c_n);
          }
          pIter(p);
        }
        // hzz contains the 1/lcm of all denominators in c_n_n
        h=n_Invers(hzz,r->cf->extRing->cf);
        n_Delete(&hzz,r->cf->extRing->cf);
        n_Normalize(h,r->cf->extRing->cf);
        if(!n_IsOne(h,r->cf->extRing->cf))
        {
          p=ph;
          while (p!=NULL)
          { // each monom: coeff in Q_a
            poly c_n=(poly)pGetCoeff(p);
            while (c_n!=NULL)
            { // each monom: coeff in Q
              d=n_Mult(h,pGetCoeff(c_n),r->cf->extRing->cf);
              n_Normalize(d,r->cf->extRing->cf);
              n_Delete(&pGetCoeff(c_n),r->cf->extRing->cf);
              pGetCoeff(c_n)=d;
              pIter(c_n);
            }
            pIter(p);
          }
        }
        n_Delete(&h,r->cf->extRing->cf);
      }
    }
*/
 
 
//  c = n_Init(1, cf); assume(FALSE); // TODO: NOT YET IMPLEMENTED!!!
}

naClearDenominators()

void naClearDenominators	(	ICoeffsEnumerator &	numberCollectionEnumerator,
		number &	c,
		const coeffs	cf
	)

Definition at line 1312 of file algext.cc.

{
  assume(cf != NULL);
  assume((getCoeffType(cf) == n_algExt)||(getCoeffType(cf) == n_polyExt));
  assume(nCoeff_is_Q_algext(cf)); // only over (Q[a]/m(a)), while the default impl. is used over Zp[a]/m(a) !
 
  assume(cf->extRing != NULL);
  const coeffs Q = cf->extRing->cf;
  assume(Q != NULL);
  assume(nCoeff_is_Q(Q));
  number n;
  CRecursivePolyCoeffsEnumerator<NAConverter> itr(numberCollectionEnumerator); // recursively treat the numbers as polys!
  n_ClearDenominators(itr, n, Q); // this should probably be fine...
  c = (number)p_NSet(n, cf->extRing); // over alg. ext. of Q // takes over the input number
}

naCoeffIsEqual()

static BOOLEAN naCoeffIsEqual ( const coeffs  cf, n_coeffType  n, void *  param  )

static

Definition at line 683 of file algext.cc.

{
  if (n_algExt != n) return FALSE;
  AlgExtInfo *e = (AlgExtInfo *)param;
  /* for extension coefficient fields we expect the underlying
     polynomial rings to be IDENTICAL, i.e. the SAME OBJECT;
     this expectation is based on the assumption that we have properly
     registered cf and perform reference counting rather than creating
     multiple copies of the same coefficient field/domain/ring */
  if (naRing == e->r)
    return TRUE;
  /* (Note that then also the minimal ideals will necessarily be
     the same, as they are attached to the ring.) */
 
  // NOTE: Q(a)[x] && Q(a)[y] should better share the _same_ Q(a)...
  if( rEqual(naRing, e->r, TRUE) ) // also checks the equality of qideals
  {
    const ideal mi = naRing->qideal;
    assume( IDELEMS(mi) == 1 );
    const ideal ii = e->r->qideal;
    assume( IDELEMS(ii) == 1 );
 
    // TODO: the following should be extended for 2 *equal* rings...
    assume( p_EqualPolys(mi->m[0], ii->m[0], naRing, e->r) );
 
    rDelete(e->r);
 
    return TRUE;
  }
 
  return FALSE;
 
}

naCoeffName()

char * naCoeffName

(

const coeffs

r

)

Definition at line 1335 of file algext.cc.

{
  const char* const* p=n_ParameterNames(r);
  int l=0;
  int i;
  for(i=0; i<n_NumberOfParameters(r);i++)
  {
    l+=(strlen(p[i])+1);
  }
  STATIC_VAR char s[200];
  s[0]='\0';
  snprintf(s,10+1,"%d",r->ch); /* Fp(a) or Q(a) */
  char tt[2];
  tt[0]=',';
  tt[1]='\0';
  for(i=0; i<n_NumberOfParameters(r);i++)
  {
    strcat(s,tt);
    strcat(s,p[i]);
  }
  return s;
}

naCoeffWrite()

void naCoeffWrite	(	const coeffs	cf,
		BOOLEAN	details
	)

Definition at line 392 of file algext.cc.

{
  assume( cf != NULL );
 
  const ring A = cf->extRing;
 
  assume( A != NULL );
  assume( A->cf != NULL );
 
  n_CoeffWrite(A->cf, details);
 
//  rWrite(A);
 
  const int P = rVar(A);
  assume( P > 0 );
 
  PrintS("[");
 
  for (int nop=0; nop < P; nop ++)
  {
    Print("%s", rRingVar(nop, A));
    if (nop!=P-1) PrintS(", ");
  }
 
  PrintS("]/(");
 
  const ideal I = A->qideal;
 
  assume( I != NULL );
  assume( IDELEMS(I) == 1 );
 
 
  if ( details )
  {
    p_Write0( I->m[0], A);
    PrintS(")");
  }
  else
    PrintS("...)");
 
/*
  char *x = rRingVar(0, A);
 
  Print("//   Coefficients live in the extension field K[%s]/<f(%s)>\n", x, x);
  Print("//   with the minimal polynomial f(%s) = %s\n", x,
        p_String(A->qideal->m[0], A));
  PrintS("//   and K: ");
*/
}

naConvFactoryNSingN()

number naConvFactoryNSingN	(	const CanonicalForm	n,
		const coeffs	cf
	)

Definition at line 755 of file algext.cc.

{
  if (n.isZero()) return NULL;
  poly p=convFactoryPSingP(n,naRing);
  return (number)p;
}

naConvSingNFactoryN()

CanonicalForm naConvSingNFactoryN	(	number	n,
		BOOLEAN	,
		const coeffs	cf
	)

Definition at line 761 of file algext.cc.

{
  naTest(n);
  if (n==NULL) return CanonicalForm(0);
 
  return convSingPFactoryP((poly)n,naRing);
}

naCopy()

number naCopy	(	number	a,
		const coeffs	cf
	)

Definition at line 296 of file algext.cc.

{
  naTest(a);
  if (((poly)a)==naMinpoly) return a;
  return (number)p_Copy((poly)a, naRing);
}

naCopyTrans2AlgExt()

number naCopyTrans2AlgExt	(	number	a,
		const coeffs	src,
		const coeffs	dst
	)

Definition at line 895 of file algext.cc.

{
  assume (nCoeff_is_transExt (src));
  assume (nCoeff_is_algExt (dst));
  fraction fa=(fraction)a;
  poly p, q;
  if (rSamePolyRep(src->extRing, dst->extRing))
  {
    p = p_Copy(NUM(fa),src->extRing);
    if (!DENIS1(fa))
    {
      q = p_Copy(DEN(fa),src->extRing);
      assume (q != NULL);
    }
  }
  else
  {
    assume ((strcmp(rRingVar(0,src->extRing),rRingVar(0,dst->extRing))==0) && (rVar (src->extRing) == rVar (dst->extRing)));
 
    nMapFunc nMap= n_SetMap (src->extRing->cf, dst->extRing->cf);
 
    assume (nMap != NULL);
    p= p_PermPoly (NUM (fa), NULL, src->extRing, dst->extRing,nMap, NULL,rVar (src->extRing));
    if (!DENIS1(fa))
    {
      q= p_PermPoly (DEN (fa), NULL, src->extRing, dst->extRing,nMap, NULL,rVar (src->extRing));
      assume (q != NULL);
    }
  }
  definiteReduce(p, dst->extRing->qideal->m[0], dst);
  p_Test (p, dst->extRing);
  if (!DENIS1(fa))
  {
    definiteReduce(q, dst->extRing->qideal->m[0], dst);
    p_Test (q, dst->extRing);
    if (q != NULL)
    {
      number t= naDiv ((number)p,(number)q, dst);
      p_Delete (&p, dst->extRing);
      p_Delete (&q, dst->extRing);
      return t;
    }
    WerrorS ("mapping denominator to zero");
  }
  return (number) p;
}

naDBTest()

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

Definition at line 233 of file algext.cc.

{
  if (a == NULL) return TRUE;
  p_Test((poly)a, naRing);
  if (getCoeffType(cf)==n_algExt)
  {
    if((((poly)a)!=naMinpoly)
    && p_Totaldegree((poly)a, naRing) >= p_Totaldegree(naMinpoly, naRing)
    && (p_Totaldegree((poly)a, naRing)> 1)) // allow to output par(1)
    {
      dReportError("deg >= deg(minpoly) in %s:%d\n",f,l);
      return FALSE;
    }
  }
  return TRUE;
}

naDelete()

void naDelete	(	number *	a,
		const coeffs	cf
	)

Definition at line 278 of file algext.cc.

{
  if (*a == NULL) return;
  if (((poly)*a)==naMinpoly) { *a=NULL;return;}
  poly aAsPoly = (poly)(*a);
  p_Delete(&aAsPoly, naRing);
  *a = NULL;
}

naDiv()

number naDiv	(	number	a,
		number	b,
		const coeffs	cf
	)

Definition at line 474 of file algext.cc.

{
  naTest(a); naTest(b);
  if (b == NULL) WerrorS(nDivBy0);
  if (a == NULL) return NULL;
  poly bInverse = (poly)naInvers(b, cf);
  if(bInverse != NULL) // b is non-zero divisor!
  {
    poly aDivB = p_Mult_q(p_Copy((poly)a, naRing), bInverse, naRing);
    definiteReduce(aDivB, naMinpoly, cf);
    p_Normalize(aDivB,naRing);
    return (number)aDivB;
  }
  return NULL;
}

naEqual()

BOOLEAN naEqual	(	number	a,
		number	b,
		const coeffs	cf
	)

simple tests

Definition at line 287 of file algext.cc.

{
  naTest(a); naTest(b);
  /// simple tests
  if (a == NULL) return (b == NULL);
  if (b == NULL) return (a == NULL);
  return p_EqualPolys((poly)a,(poly)b,naRing);
}

naFarey()

number naFarey	(	number	p,
		number	n,
		const coeffs	cf
	)

Definition at line 1370 of file algext.cc.

{
  // n is really a bigint
  poly result=p_Farey(p_Copy((poly)p,cf->extRing),n,cf->extRing);
  return ((number)result);
}

naGcd()

number naGcd	(	number	a,
		number	b,
		const coeffs	cf
	)

Definition at line 775 of file algext.cc.

{
  if (a==NULL)  return naCopy(b,cf);
  if (b==NULL)  return naCopy(a,cf);
 
  poly ax=(poly)a;
  poly bx=(poly)b;
  if (pNext(ax)!=NULL)
    return (number)p_Copy(ax, naRing);
  else
  {
    if(nCoeff_is_Zp(naRing->cf))
      return naInit(1,cf);
    else
    {
      number x = n_Copy(pGetCoeff((poly)a),naRing->cf);
      if (n_IsOne(x,naRing->cf))
        return (number)p_NSet(x,naRing);
      while (pNext(ax)!=NULL)
      {
        pIter(ax);
        number y = n_SubringGcd(x, pGetCoeff(ax), naRing->cf);
        n_Delete(&x,naRing->cf);
        x = y;
        if (n_IsOne(x,naRing->cf))
          return (number)p_NSet(x,naRing);
      }
      do
      {
        number y = n_SubringGcd(x, pGetCoeff(bx), naRing->cf);
        n_Delete(&x,naRing->cf);
        x = y;
        if (n_IsOne(x,naRing->cf))
          return (number)p_NSet(x,naRing);
        pIter(bx);
      }
      while (bx!=NULL);
      return (number)p_NSet(x,naRing);
    }
  }
#if 0
  naTest(a); naTest(b);
  const ring R = naRing;
  return (number) singclap_gcd_r((poly)a, (poly)b, R);
#endif
//  return (number)p_Gcd((poly)a, (poly)b, naRing);
}

naGenMap()

number naGenMap	(	number	a,
		const coeffs	cf,
		const coeffs	dst
	)

Definition at line 977 of file algext.cc.

{
  if (a==NULL) return NULL;
 
  const ring rSrc = cf->extRing;
  const ring rDst = dst->extRing;
 
  const nMapFunc nMap=n_SetMap(rSrc->cf,rDst->cf);
  poly f = (poly)a;
  poly g = prMapR(f, nMap, rSrc, rDst);
 
  n_Test((number)g, dst);
  return (number)g;
}

naGenTrans2AlgExt()

number naGenTrans2AlgExt	(	number	a,
		const coeffs	cf,
		const coeffs	dst
	)

Definition at line 992 of file algext.cc.

{
  if (a==NULL) return NULL;
 
  const ring rSrc = cf->extRing;
  const ring rDst = dst->extRing;
 
  const nMapFunc nMap=n_SetMap(rSrc->cf,rDst->cf);
  fraction f = (fraction)a;
  poly g = prMapR(NUM(f), nMap, rSrc, rDst);
 
  number result=NULL;
  poly h = NULL;
 
  if (!DENIS1(f))
     h = prMapR(DEN(f), nMap, rSrc, rDst);
 
  if (h!=NULL)
  {
    result=naDiv((number)g,(number)h,dst);
    p_Delete(&g,dst->extRing);
    p_Delete(&h,dst->extRing);
  }
  else
    result=(number)g;
 
  n_Test((number)result, dst);
  return (number)result;
}

naGetDenom()

number naGetDenom	(	number &	a,
		const coeffs	cf
	)

Definition at line 308 of file algext.cc.

{
  naTest(a);
  return naInit(1, cf);
}

naGetNumerator()

number naGetNumerator	(	number &	a,
		const coeffs	cf
	)

Definition at line 303 of file algext.cc.

{
  return naCopy(a, cf);
}

naGreater()

BOOLEAN naGreater	(	number	a,
		number	b,
		const coeffs	cf
	)

Definition at line 363 of file algext.cc.

{
  naTest(a); naTest(b);
  if (naIsZero(a, cf))
  {
    if (naIsZero(b, cf)) return FALSE;
    return !n_GreaterZero(pGetCoeff((poly)b),naCoeffs);
  }
  if (naIsZero(b, cf))
  {
    return n_GreaterZero(pGetCoeff((poly)a),naCoeffs);
  }
  int aDeg = p_Totaldegree((poly)a, naRing);
  int bDeg = p_Totaldegree((poly)b, naRing);
  if (aDeg>bDeg) return TRUE;
  if (aDeg<bDeg) return FALSE;
  return n_Greater(pGetCoeff((poly)a),pGetCoeff((poly)b),naCoeffs);
}

naGreaterZero()

BOOLEAN naGreaterZero	(	number	a,
		const coeffs	cf
	)

forward declarations

Definition at line 383 of file algext.cc.

{
  naTest(a);
  if (a == NULL)                                            return FALSE;
  if (n_GreaterZero(p_GetCoeff((poly)a, naRing), naCoeffs)) return TRUE;
  if (p_Totaldegree((poly)a, naRing) > 0)                   return TRUE;
  return FALSE;
}

naInit()

number naInit	(	long	i,
		const coeffs	cf
	)

Definition at line 338 of file algext.cc.

{
  if (i == 0) return NULL;
  else        return (number)p_ISet(i, naRing);
}

naInitChar()

BOOLEAN naInitChar	(	coeffs	cf,
		void *	infoStruct
	)

Initialize the coeffs object.

first check whether cf->extRing != NULL and delete old ring???

Definition at line 1378 of file algext.cc.

{
  assume( infoStruct != NULL );
 
  AlgExtInfo *e = (AlgExtInfo *)infoStruct;
  /// first check whether cf->extRing != NULL and delete old ring???
 
  assume(e->r                     != NULL);      // extRing;
  assume(e->r->cf                 != NULL);      // extRing->cf;
 
  assume((e->r->qideal            != NULL) &&    // minideal has one
         (IDELEMS(e->r->qideal)   == 1)    &&    // non-zero generator
         (e->r->qideal->m[0]      != NULL)    ); // at m[0];
 
  assume( cf != NULL );
  assume(getCoeffType(cf) == n_algExt);                     // coeff type;
 
  rIncRefCnt(e->r); // increase the ref.counter for the ground poly. ring!
  const ring R = e->r; // no copy!
  cf->extRing  = R;
 
  /* propagate characteristic up so that it becomes
     directly accessible in cf: */
  cf->ch = R->cf->ch;
 
  cf->is_field=TRUE;
  cf->is_domain=TRUE;
  cf->rep=n_rep_poly;
 
  #ifdef LDEBUG
  p_Test((poly)naMinpoly, naRing);
  #endif
 
  cf->cfCoeffName    = naCoeffName;
 
  cf->cfGreaterZero  = naGreaterZero;
  cf->cfGreater      = naGreater;
  cf->cfEqual        = naEqual;
  cf->cfIsZero       = naIsZero;
  cf->cfIsOne        = naIsOne;
  cf->cfIsMOne       = naIsMOne;
  cf->cfInit         = naInit;
  cf->cfInitMPZ      = naInitMPZ;
  cf->cfFarey        = naFarey;
  cf->cfChineseRemainder= naChineseRemainder;
  cf->cfInt          = naInt;
  cf->cfInpNeg       = naNeg;
  cf->cfAdd          = naAdd;
  cf->cfSub          = naSub;
  cf->cfMult         = naMult;
  cf->cfDiv          = naDiv;
  cf->cfExactDiv     = naDiv;
  cf->cfPower        = naPower;
  cf->cfCopy         = naCopy;
 
  cf->cfWriteLong        = naWriteLong;
 
  if( rCanShortOut(naRing) )
    cf->cfWriteShort = naWriteShort;
  else
    cf->cfWriteShort = naWriteLong;
 
  cf->cfRead         = naRead;
  cf->cfDelete       = naDelete;
  cf->cfSetMap       = naSetMap;
  cf->cfGetDenom     = naGetDenom;
  cf->cfGetNumerator = naGetNumerator;
  cf->cfRePart       = naCopy;
  cf->cfCoeffWrite   = naCoeffWrite;
  cf->cfNormalize    = naNormalize;
  cf->cfKillChar     = naKillChar;
#ifdef LDEBUG
  cf->cfDBTest       = naDBTest;
#endif
  cf->cfGcd          = naGcd;
  cf->cfNormalizeHelper          = naLcmContent;
  cf->cfSize         = naSize;
  cf->nCoeffIsEqual  = naCoeffIsEqual;
  cf->cfInvers       = naInvers;
  cf->convFactoryNSingN=naConvFactoryNSingN;
  cf->convSingNFactoryN=naConvSingNFactoryN;
  cf->cfParDeg = naParDeg;
 
  cf->iNumberOfParameters = rVar(R);
  cf->pParameterNames = (const char**)R->names;
  cf->cfParameter = naParameter;
  cf->has_simple_Inverse= R->cf->has_simple_Inverse;
  /* cf->has_simple_Alloc= FALSE; */
 
  if( nCoeff_is_Q(R->cf) )
  {
    cf->cfClearContent = naClearContent;
    cf->cfClearDenominators = naClearDenominators;
  }
 
  return FALSE;
}

naInitMPZ()

static number naInitMPZ ( mpz_t  m, const coeffs  r  )

static

Definition at line 344 of file algext.cc.

{
  number n=n_InitMPZ(m,r->extRing->cf);
  return (number)p_NSet(n,r->extRing);
}

naInt()

long naInt	(	number &	a,
		const coeffs	cf
	)

Definition at line 350 of file algext.cc.

{
  naTest(a);
  poly aAsPoly = (poly)a;
  if(aAsPoly == NULL)
    return 0;
  if (!p_IsConstant(aAsPoly, naRing))
    return 0;
  assume( aAsPoly != NULL );
  return n_Int(p_GetCoeff(aAsPoly, naRing), naCoeffs);
}

naInvers()

number naInvers	(	number	a,
		const coeffs	cf
	)

Definition at line 823 of file algext.cc.

{
  naTest(a);
  if (a == NULL) WerrorS(nDivBy0);
 
  poly aFactor = NULL; poly mFactor = NULL; poly theGcd = NULL;
// singclap_extgcd!
  const BOOLEAN ret = singclap_extgcd ((poly)a, naMinpoly, theGcd, aFactor, mFactor, naRing);
 
  assume( !ret );
 
//  if( ret ) theGcd = p_ExtGcd((poly)a, aFactor, naMinpoly, mFactor, naRing);
 
  naTest((number)theGcd); naTest((number)aFactor); naTest((number)mFactor);
  p_Delete(&mFactor, naRing);
 
  //  /* the gcd must be 1 since naMinpoly is irreducible and a != NULL: */
  //  assume(naIsOne((number)theGcd, cf));
 
  if( !naIsOne((number)theGcd, cf) )
  {
    WerrorS("zero divisor found - your minpoly is not irreducible");
    p_Delete(&aFactor, naRing); aFactor = NULL;
  }
  p_Delete(&theGcd, naRing);
 
  return (number)(aFactor);
}

naIsMOne()

BOOLEAN naIsMOne	(	number	a,
		const coeffs	cf
	)

Definition at line 322 of file algext.cc.

{
  naTest(a);
  poly aAsPoly = (poly)a;
  if ((a==NULL) || (!p_IsConstant(aAsPoly, naRing))) return FALSE;
  return n_IsMOne(p_GetCoeff(aAsPoly, naRing), naCoeffs);
}

naIsOne()

BOOLEAN naIsOne	(	number	a,
		const coeffs	cf
	)

Definition at line 314 of file algext.cc.

{
  naTest(a);
  poly aAsPoly = (poly)a;
  if ((a==NULL) || (!p_IsConstant(aAsPoly, naRing))) return FALSE;
  return n_IsOne(p_GetCoeff(aAsPoly, naRing), naCoeffs);
}

naIsParam()

int naIsParam	(	number	m,
		const coeffs	cf
	)

if m == var(i)/1 => return i,

Definition at line 1096 of file algext.cc.

{
  assume((getCoeffType(cf) == n_algExt)||(getCoeffType(cf) == n_polyExt));
 
  const ring R = cf->extRing;
  assume( R != NULL );
 
  return p_Var( (poly)m, R );
}

naIsZero()

BOOLEAN naIsZero	(	number	a,
		const coeffs	cf
	)

Definition at line 272 of file algext.cc.

{
  naTest(a);
  return (a == NULL);
}

naKillChar()

void naKillChar

(

coeffs

cf

)

Definition at line 1328 of file algext.cc.

{
  rDecRefCnt(cf->extRing);
  if(cf->extRing->ref<0)
    rDelete(cf->extRing);
}

naLcmContent()

number naLcmContent	(	number	a,
		number	b,
		const coeffs	cf
	)

Definition at line 648 of file algext.cc.

{
  if (nCoeff_is_Zp(naRing->cf)) return naCopy(a,cf);
#if 0
  else {
    number g = ndGcd(a, b, cf);
    return g;
  }
#else
  {
    a=(number)p_Copy((poly)a,naRing);
    number t=napNormalizeHelper(b,cf);
    if(!n_IsOne(t,naRing->cf))
    {
      number bt, rr;
      poly xx=(poly)a;
      while (xx!=NULL)
      {
        bt = n_SubringGcd(t, pGetCoeff(xx), naRing->cf);
        rr = n_Mult(t, pGetCoeff(xx), naRing->cf);
        n_Delete(&pGetCoeff(xx),naRing->cf);
        pGetCoeff(xx) = n_Div(rr, bt, naRing->cf);
        n_Normalize(pGetCoeff(xx),naRing->cf);
        n_Delete(&bt,naRing->cf);
        n_Delete(&rr,naRing->cf);
        pIter(xx);
      }
    }
    n_Delete(&t,naRing->cf);
    return (number) a;
  }
#endif
}

naMap00()

number naMap00	(	number	a,
		const coeffs	src,
		const coeffs	dst
	)

Definition at line 853 of file algext.cc.

{
  if (n_IsZero(a, src)) return NULL;
  assume(src->rep == dst->extRing->cf->rep);
  poly result = p_One(dst->extRing);
  p_SetCoeff(result, n_Copy(a, src), dst->extRing);
  return (number)result;
}

naMap0P()

number naMap0P	(	number	a,
		const coeffs	src,
		const coeffs	dst
	)

Definition at line 943 of file algext.cc.

{
  if (n_IsZero(a, src)) return NULL;
  // int p = rChar(dst->extRing);
 
  number q = nlModP(a, src, dst->extRing->cf); // FIXME? TODO? // extern number nlModP(number q, const coeffs Q, const coeffs Zp); // Map q \in QQ \to pZ
 
  poly result = p_NSet(q, dst->extRing);
 
  return (number)result;
}

naMapP0()

number naMapP0	(	number	a,
		const coeffs	src,
		const coeffs	dst
	)

Definition at line 875 of file algext.cc.

{
  if (n_IsZero(a, src)) return NULL;
  /* mapping via intermediate int: */
  int n = n_Int(a, src);
  number q = n_Init(n, dst->extRing->cf);
  poly result = p_One(dst->extRing);
  p_SetCoeff(result, q, dst->extRing);
  return (number)result;
}

naMapPP()

number naMapPP	(	number	a,
		const coeffs	src,
		const coeffs	dst
	)

Definition at line 956 of file algext.cc.

{
  if (n_IsZero(a, src)) return NULL;
  assume(src == dst->extRing->cf);
  poly result = p_One(dst->extRing);
  p_SetCoeff(result, n_Copy(a, src), dst->extRing);
  return (number)result;
}

naMapUP()

number naMapUP	(	number	a,
		const coeffs	src,
		const coeffs	dst
	)

Definition at line 966 of file algext.cc.

{
  if (n_IsZero(a, src)) return NULL;
  /* mapping via intermediate int: */
  int n = n_Int(a, src);
  number q = n_Init(n, dst->extRing->cf);
  poly result = p_One(dst->extRing);
  p_SetCoeff(result, q, dst->extRing);
  return (number)result;
}

naMapZ0()

number naMapZ0	(	number	a,
		const coeffs	src,
		const coeffs	dst
	)

Definition at line 863 of file algext.cc.

{
  if (n_IsZero(a, src)) return NULL;
  poly result = p_One(dst->extRing);
  nMapFunc nMap=n_SetMap(src,dst->extRing->cf);
  p_SetCoeff(result, nMap(a, src, dst->extRing->cf), dst->extRing);
  if (n_IsZero(pGetCoeff(result),dst->extRing->cf))
    p_Delete(&result,dst->extRing);
  return (number)result;
}

naMult()

number naMult	(	number	a,
		number	b,
		const coeffs	cf
	)

Definition at line 464 of file algext.cc.

{
  naTest(a); naTest(b);
  if ((a == NULL)||(b == NULL)) return NULL;
  poly aTimesB = pp_Mult_qq((poly)a, (poly)b, naRing);
  definiteReduce(aTimesB, naMinpoly, cf);
  p_Normalize(aTimesB,naRing);
  return (number)aTimesB;
}

naNeg()

number naNeg	(	number	a,
		const coeffs	cf
	)

this is in-place, modifies a

Definition at line 331 of file algext.cc.

{
  naTest(a);
  if (a != NULL) a = (number)p_Neg((poly)a, naRing);
  return a;
}

naNormalize()

void naNormalize	(	number &	a,
		const coeffs	cf
	)

Definition at line 747 of file algext.cc.

{
  poly aa=(poly)a;
  if (aa!=naMinpoly)
    definiteReduce(aa,naMinpoly,cf);
  a=(number)aa;
}

naParameter()

number naParameter	(	const int	iParameter,
		const coeffs	cf
	)

return the specified parameter as a number in the given alg. field

Definition at line 1081 of file algext.cc.

{
  assume(getCoeffType(cf) == n_algExt);
 
  const ring R = cf->extRing;
  assume( R != NULL );
  assume( 0 < iParameter && iParameter <= rVar(R) );
 
  poly p = p_One(R); p_SetExp(p, iParameter, 1, R); p_Setm(p, R);
 
  return (number) p;
}

naParDeg()

int naParDeg	(	number	a,
		const coeffs	cf
	)

Definition at line 1073 of file algext.cc.

{
  if (a == NULL) return -1;
  poly aa=(poly)a;
  return cf->extRing->pFDeg(aa,cf->extRing);
}

napNormalizeHelper()

number napNormalizeHelper	(	number	b,
		const coeffs	cf
	)

Definition at line 634 of file algext.cc.

{
  number h=n_Init(1,naRing->cf);
  poly bb=(poly)b;
  number d;
  while(bb!=NULL)
  {
    d=n_NormalizeHelper(h,pGetCoeff(bb), naRing->cf);
    n_Delete(&h,naRing->cf);
    h=d;
    pIter(bb);
  }
  return h;
}

naPower()

void naPower	(	number	a,
		int	exp,
		number *	b,
		const coeffs	cf
	)

Definition at line 498 of file algext.cc.

{
  naTest(a);
 
  /* special cases first */
  if (a == NULL)
  {
    if (exp >= 0) *b = NULL;
    else          WerrorS(nDivBy0);
    return;
  }
  else if (exp ==  0) { *b = naInit(1, cf); return; }
  else if (exp ==  1) { *b = naCopy(a, cf); return; }
  else if (exp == -1) { *b = naInvers(a, cf); return; }
 
  int expAbs = exp; if (expAbs < 0) expAbs = -expAbs;
 
  /* now compute a^expAbs */
  poly pow; poly aAsPoly = (poly)a;
  if (expAbs <= 7)
  {
    pow = p_Copy(aAsPoly, naRing);
    for (int i = 2; i <= expAbs; i++)
    {
      pow = p_Mult_q(pow, p_Copy(aAsPoly, naRing), naRing);
      heuristicReduce(pow, naMinpoly, cf);
    }
    definiteReduce(pow, naMinpoly, cf);
  }
  else
  {
    pow = p_ISet(1, naRing);
    poly factor = p_Copy(aAsPoly, naRing);
    while (expAbs != 0)
    {
      if (expAbs & 1)
      {
        pow = p_Mult_q(pow, p_Copy(factor, naRing), naRing);
        heuristicReduce(pow, naMinpoly, cf);
      }
      expAbs = expAbs / 2;
      if (expAbs != 0)
      {
        factor = p_Mult_q(factor, p_Copy(factor, naRing), naRing);
        heuristicReduce(factor, naMinpoly, cf);
      }
    }
    p_Delete(&factor, naRing);
    definiteReduce(pow, naMinpoly, cf);
  }
 
  /* invert if original exponent was negative */
  number n = (number)pow;
  if (exp < 0)
  {
    number m = naInvers(n, cf);
    naDelete(&n, cf);
    n = m;
  }
  *b = n;
}

naRead()

const char * naRead	(	const char *	s,
		number *	a,
		const coeffs	cf
	)

Definition at line 611 of file algext.cc.

{
  poly aAsPoly;
  const char * result = p_Read(s, aAsPoly, naRing);
  if (aAsPoly!=NULL) definiteReduce(aAsPoly, naMinpoly, cf);
  *a = (number)aAsPoly;
  return result;
}

naSetMap()

nMapFunc naSetMap	(	const coeffs	src,
		const coeffs	dst
	)

Get a mapping function from src into the domain of this type (n_algExt)

Q or Z --> Q(a)

Z --> Q(a)

Z/p --> Q(a)

Q --> Z/p(a)

Z --> Z/p(a)

Z/p --> Z/p(a)

Z/u --> Z/p(a)

default

Definition at line 1022 of file algext.cc.

{
  /* dst is expected to be an algebraic field extension */
  assume(getCoeffType(dst) == n_algExt);
 
  int h = 0; /* the height of the extension tower given by dst */
  coeffs bDst = nCoeff_bottom(dst, h); /* the bottom field in the tower dst */
  coeffs bSrc = nCoeff_bottom(src, h); /* the bottom field in the tower src */
 
  /* for the time being, we only provide maps if h = 1 or 0 */
  if (h==0)
  {
    if ((src->rep==n_rep_gap_rat) && nCoeff_is_Q(bDst))
      return naMap00;                            /// Q or Z     -->  Q(a)
    if ((src->rep==n_rep_gap_gmp) && nCoeff_is_Q(bDst))
      return naMapZ0;                            /// Z     -->  Q(a)
    if (nCoeff_is_Zp(src) && nCoeff_is_Q(bDst))
      return naMapP0;                            /// Z/p   -->  Q(a)
    if (nCoeff_is_Q_or_BI(src) && nCoeff_is_Zp(bDst))
      return naMap0P;                            /// Q      --> Z/p(a)
    if ((src->rep==n_rep_gap_gmp) && nCoeff_is_Zp(bDst))
      return naMapZ0;                            /// Z     -->  Z/p(a)
    if (nCoeff_is_Zp(src) && nCoeff_is_Zp(bDst))
    {
      if (src->ch == dst->ch) return naMapPP;    /// Z/p    --> Z/p(a)
      else return naMapUP;                       /// Z/u    --> Z/p(a)
    }
  }
  if (h != 1) return NULL;
  if ((!nCoeff_is_Zp(bDst)) && (!nCoeff_is_Q(bDst))) return NULL;
  if ((!nCoeff_is_Zp(bSrc)) && (!nCoeff_is_Q_or_BI(bSrc))) return NULL;
 
  nMapFunc nMap=n_SetMap(src->extRing->cf,dst->extRing->cf);
  if (rSamePolyRep(src->extRing, dst->extRing) && (strcmp(rRingVar(0, src->extRing), rRingVar(0, dst->extRing)) == 0))
  {
    if (src->type==n_algExt)
       return ndCopyMap; // naCopyMap;         /// K(a)   --> K(a)
    else
       return naCopyTrans2AlgExt;
  }
  else if ((nMap!=NULL) && (strcmp(rRingVar(0,src->extRing),rRingVar(0,dst->extRing))==0) && (rVar (src->extRing) == rVar (dst->extRing)))
  {
    if (src->type==n_algExt)
       return naGenMap; // naCopyMap;         /// K(a)   --> K'(a)
    else
       return naGenTrans2AlgExt;
  }
 
  return NULL;                                           /// default
}

naSize()

int naSize	(	number	a,
		const coeffs	cf
	)

Definition at line 717 of file algext.cc.

{
  if (a == NULL) return 0;
  poly aAsPoly = (poly)a;
  int theDegree = 0; int noOfTerms = 0;
  while (aAsPoly != NULL)
  {
    noOfTerms++;
    int d = p_GetExp(aAsPoly, 1, naRing);
    if (d > theDegree) theDegree = d;
    pIter(aAsPoly);
  }
  return (theDegree +1) * noOfTerms;
}

naSub()

number naSub	(	number	a,
		number	b,
		const coeffs	cf
	)

Definition at line 453 of file algext.cc.

{
  naTest(a); naTest(b);
  if (b == NULL) return naCopy(a, cf);
  poly minusB = p_Neg(p_Copy((poly)b, naRing), naRing);
  if (a == NULL) return (number)minusB;
  poly aMinusB = p_Add_q(p_Copy((poly)a, naRing), minusB, naRing);
  //definiteReduce(aMinusB, naMinpoly, cf);
  return (number)aMinusB;
}

naWriteLong()

void naWriteLong	(	number	a,
		const coeffs	cf
	)

Definition at line 575 of file algext.cc.

{
  naTest(a);
  if (a == NULL)
    StringAppendS("0");
  else
  {
    poly aAsPoly = (poly)a;
    /* basically, just write aAsPoly using p_Write,
       but use brackets around the output, if a is not
       a constant living in naCoeffs = cf->extRing->cf */
    BOOLEAN useBrackets = !(p_IsConstant(aAsPoly, naRing));
    if (useBrackets) StringAppendS("(");
    p_String0Long(aAsPoly, naRing, naRing);
    if (useBrackets) StringAppendS(")");
  }
}

naWriteShort()

void naWriteShort	(	number	a,
		const coeffs	cf
	)

Definition at line 593 of file algext.cc.

{
  naTest(a);
  if (a == NULL)
    StringAppendS("0");
  else
  {
    poly aAsPoly = (poly)a;
    /* basically, just write aAsPoly using p_Write,
       but use brackets around the output, if a is not
       a constant living in naCoeffs = cf->extRing->cf */
    BOOLEAN useBrackets = !(p_IsConstant(aAsPoly, naRing));
    if (useBrackets) StringAppendS("(");
    p_String0Short(aAsPoly, naRing, naRing);
    if (useBrackets) StringAppendS(")");
  }
}

nCoeff_bottom()

static coeffs nCoeff_bottom ( const coeffs  r, int &  height  )

static

Definition at line 258 of file algext.cc.

{
  assume(r != NULL);
  coeffs cf = r;
  height = 0;
  while (nCoeff_is_Extension(cf))
  {
    assume(cf->extRing != NULL); assume(cf->extRing->cf != NULL);
    cf = cf->extRing->cf;
    height++;
  }
  return cf;
}

p_ExtGcd()

poly p_ExtGcd	(	poly	p,
		poly &	pFactor,
		poly	q,
		poly &	qFactor,
		ring	r
	)

assumes that p and q are univariate polynomials in r, mentioning the same variable; assumes a global monomial ordering in r; assumes that not both p and q are NULL; returns the gcd of p and q; moreover, afterwards pFactor and qFactor contain appropriate factors such that gcd(p, q) = p * pFactor + q * qFactor; leaves p and q unmodified

Definition at line 216 of file algext.cc.

{
  assume((p != NULL) || (q != NULL));
  poly a = p; poly b = q; BOOLEAN aCorrespondsToP = TRUE;
  if (p_Deg(a, r) < p_Deg(b, r))
    { a = q; b = p; aCorrespondsToP = FALSE; }
  a = p_Copy(a, r); b = p_Copy(b, r);
  poly aFactor = NULL; poly bFactor = NULL;
  poly theGcd = p_ExtGcdHelper(a, aFactor, b, bFactor, r);
  if (aCorrespondsToP) { pFactor = aFactor; qFactor = bFactor; }
  else                 { pFactor = bFactor; qFactor = aFactor; }
  return theGcd;
}

p_ExtGcdHelper()

static poly p_ExtGcdHelper ( poly &  p, poly &  pFactor, poly &  q, poly &  qFactor, ring  r  )

inlinestatic

Definition at line 183 of file algext.cc.

{
  if (q == NULL)
  {
    qFactor = NULL;
    pFactor = p_ISet(1, r);
    p_SetCoeff(pFactor, n_Invers(p_GetCoeff(p, r), r->cf), r);
    p_Monic(p, r);
    return p;
  }
  else
  {
    poly pDivQ = p_PolyDiv(p, q, TRUE, r);
    poly ppFactor = NULL; poly qqFactor = NULL;
    poly theGcd = p_ExtGcdHelper(q, qqFactor, p, ppFactor, r);
    pFactor = ppFactor;
    qFactor = p_Add_q(qqFactor,
                      p_Neg(p_Mult_q(pDivQ, p_Copy(ppFactor, r), r), r),
                      r);
    return theGcd;
  }
}

p_Gcd()

static poly p_Gcd ( const poly  p, const poly  q, const ring  r  )

inlinestatic

Definition at line 165 of file algext.cc.

{
  assume((p != NULL) || (q != NULL));
 
  poly a = p; poly b = q;
  if (p_Deg(a, r) < p_Deg(b, r)) { a = q; b = p; }
  a = p_Copy(a, r); b = p_Copy(b, r);
 
  /* We have to make p monic before we return it, so that if the
     gcd is a unit in the ground field, we will actually return 1. */
  a = p_GcdHelper(a, b, r);
  p_Monic(a, r);
  return a;
}

p_GcdHelper()

static poly p_GcdHelper ( poly &  p, poly &  q, const ring  r  )

inlinestatic

see p_Gcd; additional assumption: deg(p) >= deg(q); must destroy p and q (unless one of them is returned)

Definition at line 145 of file algext.cc.

{
  while (q != NULL)
  {
    p_PolyDiv(p, q, FALSE, r);
    // swap p and q:
    poly& t = q;
    q = p;
    p = t;
 
  }
  return p;
}

p_Monic()

static void p_Monic ( poly  p, const ring  r  )

inlinestatic

returns NULL if p == NULL, otherwise makes p monic by dividing by its leading coefficient (only done if this is not already 1); this assumes that we are over a ground field so that division is well-defined; modifies p

assumes that p and q are univariate polynomials in r, mentioning the same variable; assumes a global monomial ordering in r; assumes that not both p and q are NULL; returns the gcd of p and q; leaves p and q unmodified

Definition at line 120 of file algext.cc.

{
  if (p == NULL) return;
  number n = n_Init(1, r->cf);
  if (p->next==NULL) { p_SetCoeff(p,n,r); return; }
  poly pp = p;
  number lc = p_GetCoeff(p, r);
  if (n_IsOne(lc, r->cf)) return;
  number lcInverse = n_Invers(lc, r->cf);
  p_SetCoeff(p, n, r);   // destroys old leading coefficient!
  pIter(p);
  while (p != NULL)
  {
    number n = n_Mult(p_GetCoeff(p, r), lcInverse, r->cf);
    n_Normalize(n,r->cf);
    p_SetCoeff(p, n, r);   // destroys old leading coefficient!
    pIter(p);
  }
  n_Delete(&lcInverse, r->cf);
  p = pp;
}