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.
#define	naTest(a)
#define	naRing   cf->extRing
#define	naCoeffs   cf->extRing->cf
#define	naMinpoly   naRing->qideal->m[0]
#define	n2pTest(a)
	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.
#define	n2pRing   cf->extRing
#define	n2pCoeffs   cf->extRing->cf

Functions
static BOOLEAN	naDBTest (number a, const char *f, const int l, const coeffs r)
static BOOLEAN	naGreaterZero (number a, const coeffs cf)
	forward declarations
static BOOLEAN	naGreater (number a, number b, const coeffs cf)
static BOOLEAN	naEqual (number a, number b, const coeffs cf)
static BOOLEAN	naIsOne (number a, const coeffs cf)
static BOOLEAN	naIsMOne (number a, const coeffs cf)
static number	naInit (long i, const coeffs cf)
static number	naNeg (number a, const coeffs cf)
	this is in-place, modifies a
static number	naInvers (number a, const coeffs cf)
static number	naAdd (number a, number b, const coeffs cf)
static number	naSub (number a, number b, const coeffs cf)
static number	naMult (number a, number b, const coeffs cf)
static number	naDiv (number a, number b, const coeffs cf)
static void	naPower (number a, int exp, number *b, const coeffs cf)
static number	naCopy (number a, const coeffs cf)
static void	naWriteLong (number a, const coeffs cf)
static void	naWriteShort (number a, const coeffs cf)
static number	naGcd (number a, number b, const coeffs cf)
static void	naDelete (number *a, const coeffs cf)
static void	naCoeffWrite (const coeffs cf, BOOLEAN details)
static 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
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)
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
static void	heuristicReduce (poly &p, poly reducer, const coeffs cf)
static void	definiteReduce (poly &p, poly reducer, const coeffs cf)
static coeffs	nCoeff_bottom (const coeffs r, int &height)
static BOOLEAN	naIsZero (number a, const coeffs cf)
static number	naInitMPZ (mpz_t m, const coeffs r)
static long	naInt (number &a, const coeffs cf)
static void	naInpAdd (number &a, number b, const coeffs cf)
static void	naInpMult (number &a, number b, const coeffs cf)
static number	napNormalizeHelper (number b, const coeffs cf)
static number	naLcmContent (number a, number b, const coeffs cf)
static int	naSize (number a, const coeffs cf)
static void	naNormalize (number &a, const coeffs cf)
static number	naConvFactoryNSingN (const CanonicalForm n, const coeffs cf)
static CanonicalForm	naConvSingNFactoryN (number n, BOOLEAN, const coeffs cf)
static number	naMap00 (number a, const coeffs src, const coeffs dst)
static number	naMapZ0 (number a, const coeffs src, const coeffs dst)
static number	naMapP0 (number a, const coeffs src, const coeffs dst)
static number	naCopyTrans2AlgExt (number a, const coeffs src, const coeffs dst)
static number	naMap0P (number a, const coeffs src, const coeffs dst)
static number	naMapPP (number a, const coeffs src, const coeffs dst)
static number	naMapUP (number a, const coeffs src, const coeffs dst)
static number	naGenMap (number a, const coeffs cf, const coeffs dst)
static 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).
static int	naParDeg (number a, const coeffs cf)
static number	naParameter (const int iParameter, const coeffs cf)
	return the specified parameter as a number in the given alg. field
int	naIsParam (number m, const coeffs cf)
	if m == var(i)/1 => return i,
static void	naClearContent (ICoeffsEnumerator &numberCollectionEnumerator, number &c, const coeffs cf)
static void	naClearDenominators (ICoeffsEnumerator &numberCollectionEnumerator, number &c, const coeffs cf)
static void	naKillChar (coeffs cf)
char *	naCoeffName (const coeffs r)
static number	naChineseRemainder (number *x, number *q, int rl, BOOLEAN, CFArray &inv_cache, const coeffs cf)
static number	naFarey (number p, number n, const coeffs cf)
BOOLEAN	naInitChar (coeffs cf, void *infoStruct)
	Initialize the coeffs object.
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 1562 of file algext.cc.

n2pRing

#define n2pRing   cf->extRing

Definition at line 1556 of file algext.cc.

n2pTest

#define n2pTest

(

a

)

Value:

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 1549 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

)

Value:

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 available, 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 )

static

Definition at line 743 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 )

static

Definition at line 573 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()

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

static

Definition at line 1612 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 1632 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 1659 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 1565 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 1587 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 1687 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->cfInpAdd       = naInpAdd;
  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; // use nd*
  //cf->cfGetNumerator = naGetNumerator; // use nd*
  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 1671 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 1579 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 1572 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 1596 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 1603 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 )

static

Definition at line 429 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 )

static

Definition at line 1413 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()

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

static

Definition at line 1162 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 )

static

Definition at line 1367 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()

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

static

Definition at line 691 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 1390 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 )

static

Definition at line 379 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 )

static

Definition at line 763 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 )

static

Definition at line 769 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 )

static

Definition at line 294 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 )

static

Definition at line 950 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 )

static

Definition at line 231 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 )

static

Definition at line 276 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 )

static

Definition at line 482 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 )

static

simple tests

Definition at line 285 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 )

static

Definition at line 1425 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 )

static

Definition at line 783 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 )

static

Definition at line 1032 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 )

static

Definition at line 1047 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;
}

naGreater()

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

static

Definition at line 350 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 )

static

forward declarations

Definition at line 370 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 )

static

Definition at line 325 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 1433 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->cfInpMult      = naInpMult;
  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->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()

number naInitMPZ ( mpz_t m, const coeffs r )

static

Definition at line 331 of file algext.cc.

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

naInpAdd()

void naInpAdd ( number & a, number b, const coeffs cf )

static

Definition at line 440 of file algext.cc.

{
  naTest(a); naTest(b);
  if (a == NULL) a=b;
  else if (b != NULL)
  {
    poly aPlusB = p_Add_q((poly)a, p_Copy((poly)b, naRing), naRing);
    a=(number)aPlusB;
  }
}

naInpMult()

void naInpMult ( number & a, number b, const coeffs cf )

static

Definition at line 472 of file algext.cc.

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

naInt()

long naInt ( number & a, const coeffs cf )

static

Definition at line 337 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 )

static

Definition at line 831 of file algext.cc.

{
  naTest(a);
  if (a == NULL) WerrorS(nDivBy0);
 
  poly aFactor = NULL; poly mFactor = NULL; poly theGcd = NULL;
// singclap_extgcd!
  BOOLEAN ret=FALSE;
  #if 0 
  //#ifdef HAVE_FLINT
    // context for modulus
    ring R=naRing;
    fmpz_mod_ctx_t ctxp;
    fmpz_t p;
    fmpz_init(p); fmpz_init_set_ui(p,R->ch);
    fmpz_mod_ctx_init(ctxp,p);
    fmpz_clear(p);
    // convert modulus
    fmpz_mod_poly_t modulus;
    poly p=R->qideal->m[0];
    fmpz_mod_poly_init2(modulus,deg(p)+1,ctxp);
    while(p!=NULL)
    {
      fmpz_mod_poly_set_coeff_ui(result,p_GetExp(p,1,R),(long)(pGetCoeff(p)));
      pIter(p);
    }
    // ctx for ring r
    fq_ctx_t ctx ctx;
    fq_ctx_init_modulus(ctx,modulus,ctxp,"a");
    fmpz_mod_poly_clear(modulus);
    // convert a
    poly ap=(poly)a;
    fq_poly_t aa;
    fq_poly_init2 (aa, p_GetExp(ap,1,R), ctx);
    while(ap!=NULL)
    {
      fq_t buf;
      fmpz_poly_init2(buf,fq_ctx_degree(ctx));
      _fmpz_poly_set_length(buf, fq_ctx_degree(ctx));
      fmpz_set_si (buf,(long)pGetCoeff(ap));
      fq_poly_set_coeff (aa, p_GetExp(ap,1,R), buf, ctx);
      fq_clear (buf, ctx);
      pIter(ap);
    }
    // gcd
    // convert res
    // cleanup
    fq_ctx_clear(ctx);
    fmpz_mod_ctx_clear(ctxp);
    // return result
    // see fq_gcdinv
 
 
  #else
  ret = singclap_extgcd ((poly)a, naMinpoly, theGcd, aFactor, mFactor, naRing);
  #endif
 
  if (ret) return NULL;
  // 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 )

static

Definition at line 309 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 )

static

Definition at line 301 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 1151 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 )

static

Definition at line 270 of file algext.cc.

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

naKillChar()

void naKillChar ( coeffs cf )

static

Definition at line 1383 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 )

static

Definition at line 656 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 )

static

Definition at line 908 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 )

static

Definition at line 998 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 )

static

Definition at line 930 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 )

static

Definition at line 1011 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 )

static

Definition at line 1021 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 )

static

Definition at line 918 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 )

static

Definition at line 462 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 )

static

this is in-place, modifies a

Definition at line 318 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 )

static

Definition at line 755 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 )

static

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

Definition at line 1136 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 )

static

Definition at line 1128 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 )

static

Definition at line 642 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 )

static

Definition at line 506 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 )

static

Definition at line 619 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 1077 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 )

static

Definition at line 725 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 )

static

Definition at line 451 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 )

static

Definition at line 583 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 )

static

Definition at line 601 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()

coeffs nCoeff_bottom ( const coeffs r, int & height )

static

Definition at line 256 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 214 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()

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

inlinestatic

Definition at line 181 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()

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

inlinestatic

Definition at line 163 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()

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 143 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()

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 118 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;
}