numbers.cc File Reference

#include <string.h>
#include <stdlib.h>
#include <misc/auxiliary.h>
#include <omalloc/omalloc.h>
#include <factory/factory.h>
#include <reporter/reporter.h>
#include <coeffs/coeffs.h>
#include <coeffs/numbers.h>
#include <coeffs/longrat.h>
#include <coeffs/modulop.h>
#include <coeffs/gnumpfl.h>
#include <coeffs/gnumpc.h>
#include <coeffs/ffields.h>
#include <coeffs/shortfl.h>
#include <coeffs/rmodulo2m.h>
#include <coeffs/rmodulon.h>
#include <coeffs/rintegers.h>
#include <polys/ext_fields/algext.h>
#include <polys/ext_fields/transext.h>

Go to the source code of this file.

Functions
void	nNew (number *d)
static void	ndDelete (number *d, const coeffs)
static number	ndAnn (number, const coeffs)
static char *	ndCoeffString (const coeffs r)
static void	ndInpMult (number &a, number b, const coeffs r)
static void	ndInpAdd (number &a, number b, const coeffs r)
static void	ndPower (number a, int i, number *res, const coeffs r)
static BOOLEAN	ndDBTest (number, const char *, const int, const coeffs)
static number	ndFarey (number, number, const coeffs r)
static number	ndChineseRemainder (number *, number *, int, BOOLEAN, const coeffs r)
static int	ndParDeg (number n, const coeffs r)
static number	ndParameter (const int, const coeffs r)
BOOLEAN	n_IsZeroDivisor (number a, const coeffs r)
	Test whether a is a zero divisor in r i.e. not coprime with char. of r very inefficient implementation: should ONLY be used for debug stuff /tests. More...
static void	ndNormalize (number &, const coeffs)
static number	ndReturn0 (number, const coeffs r)
static number	ndGcd (number, number, const coeffs r)
static number	ndIntMod (number, number, const coeffs r)
static number	ndGetDenom (number &, const coeffs r)
static number	ndGetNumerator (number &a, const coeffs r)
static int	ndSize (number a, const coeffs r)
static char *	ndCoeffName (const coeffs r)
static void	ndClearContent (ICoeffsEnumerator &numberCollectionEnumerator, number &c, const coeffs r)
static void	ndClearDenominators (ICoeffsEnumerator &, number &d, const coeffs r)
static number	ndCopy (number a, const coeffs)
number	ndCopyMap (number a, const coeffs aRing, const coeffs r)
static void	ndKillChar (coeffs)
static void	ndSetChar (const coeffs)
number	nd_Copy (number a, const coeffs r)
static BOOLEAN	ndDivBy (number, number, const coeffs)
static int	ndDivComp (number, number, const coeffs)
static BOOLEAN	ndIsUnit (number a, const coeffs r)
static number	ndExtGcd (number, number, number *, number *, const coeffs r)
static CanonicalForm	ndConvSingNFactoryN (number, BOOLEAN, const coeffs)
static number	ndConvFactoryNSingN (const CanonicalForm, const coeffs)
	[in, out] a bigint number >= 0 More...
static void	ndMPZ (mpz_t result, number &n, const coeffs r)
	Converts a non-negative bigint number into a GMP number. More...
static number	ndInitMPZ (mpz_t m, const coeffs r)
static BOOLEAN	ndCoeffIsEqual (const coeffs r, n_coeffType n, void *)
coeffs	nInitChar (n_coeffType t, void *parameter)
	one-time initialisations for new coeffs in case of an error return NULL More...
void	nKillChar (coeffs r)
	undo all initialisations More...
n_coeffType	nRegister (n_coeffType n, cfInitCharProc p)
void	n_Print (number &a, const coeffs r)
	print a number (BEWARE of string buffers!) mostly for debugging More...
number	n_convFactoryNSingN (const CanonicalForm n, const coeffs r)
CanonicalForm	n_convSingNFactoryN (number n, BOOLEAN setChar, const coeffs r)

Variables
n_Procs_s *	cf_root =NULL
static n_coeffType	nLastCoeffs =n_CF
cfInitCharProc	nInitCharTableDefault []
static cfInitCharProc *	nInitCharTable =nInitCharTableDefault

Function Documentation

number n_convFactoryNSingN	(	const CanonicalForm	n,
		const coeffs	r
	)

Definition at line 549 of file numbers.cc.

{ STATISTIC(n_convFactoryNSingN); assume(r != NULL); assume(r->convFactoryNSingN != NULL); return r->convFactoryNSingN(n, r); }

CanonicalForm n_convSingNFactoryN	(	number	n,
		BOOLEAN	setChar,
		const coeffs	r
	)

Definition at line 554 of file numbers.cc.

{ STATISTIC(n_convSingNFactoryN); assume(r != NULL); assume(r->convSingNFactoryN != NULL); return r->convSingNFactoryN(n, setChar, r); }

BOOLEAN n_IsZeroDivisor	(	number	a,
		const coeffs	r
	)

Test whether a is a zero divisor in r i.e. not coprime with char. of r very inefficient implementation: should ONLY be used for debug stuff /tests.

Definition at line 120 of file numbers.cc.

{
  int c = n_GetChar(r);
  BOOLEAN ret = n_IsZero(a, r);
  if( (c != 0) && !ret )
  {
    number ch = n_Init( c, r );
    number g = n_Gcd( ch, a, r );
    ret = !n_IsOne (g, r);
    n_Delete(&ch, r);
    n_Delete(&g, r);
  }
  return ret;
}

void n_Print	(	number &	a,
		const coeffs	r
	)

print a number (BEWARE of string buffers!) mostly for debugging

Definition at line 538 of file numbers.cc.

{
   assume(r != NULL);
   n_Test(a,r);

   StringSetS("");
   n_Write(a, r);
   { char* s = StringEndS(); Print("%s", s); omFree(s); }

number nd_Copy	(	number	a,
		const coeffs	r
	)

Definition at line 240 of file numbers.cc.

{ return r->cfCopy(a, r); }

static number ndAnn ( number  , const coeffs    )

static

Definition at line 53 of file numbers.cc.

{ return NULL;}

static number ndChineseRemainder ( number *  , number *  , int  , BOOLEAN  , const coeffs  r  )

static

Definition at line 103 of file numbers.cc.

{
  Werror("ChineseRemainder not implemented for %s (c=%d)",r->cfCoeffString(r),getCoeffType(r));
  return r->cfInit(0,r);
}

static void ndClearContent ( ICoeffsEnumerator &  numberCollectionEnumerator, number &  c, const coeffs  r  )

static

TODO: move to a separate implementation

Definition at line 144 of file numbers.cc.

{
  assume(r != NULL);

  // no fractions
  assume(!(  nCoeff_is_Q(r) ));
  // all coeffs are given by integers!!!

  numberCollectionEnumerator.Reset();

  if( !numberCollectionEnumerator.MoveNext() ) // empty zero polynomial?
  {
    c = n_Init(1, r);
    return;
  }

  number &curr = numberCollectionEnumerator.Current();

#ifdef HAVE_RINGS
  /// TODO: move to a separate implementation
  if (nCoeff_is_Ring(r))
  {
    if (nCoeff_has_Units(r))
    {
      c = n_GetUnit(curr, r);

      if (!n_IsOne(c, r))
      {
        number inv = n_Invers(c, r);

        n_InpMult(curr, inv, r);

        while( numberCollectionEnumerator.MoveNext() )
        {
          number &n = numberCollectionEnumerator.Current();
          n_Normalize(n, r); // ?
          n_InpMult(n, inv, r); // TODO: either this or directly divide!!!?
        }

        n_Delete(&inv, r);
      }
    } else c = n_Init(1, r);

    return;
  }
#endif

  assume(!nCoeff_is_Ring(r));
  assume(nCoeff_is_Zp(r) || nCoeff_is_numeric(r) || nCoeff_is_GF(r) || nCoeff_is_Zp_a(r) || nCoeff_is_Q_algext(r));

  n_Normalize(curr, r); // Q: good/bad/ugly??

  if (!n_IsOne(curr, r))
  {
    number t = curr; // takes over the curr! note: not a reference!!!

    curr = n_Init(1, r); // ???

    number inv = n_Invers(t, r);

    while( numberCollectionEnumerator.MoveNext() )
    {
      number &n = numberCollectionEnumerator.Current();
      n_InpMult(n, inv, r); // TODO: either this or directly divide!!!?
//      n_Normalize(n, r); // ?
    }

    n_Delete(&inv, r);

    c = t;
  } else
    c = n_Copy(curr, r); // c == 1 and nothing else to do...
}

static void ndClearDenominators ( ICoeffsEnumerator &  , number &  d, const coeffs  r  )

static

Definition at line 218 of file numbers.cc.

{
  assume( r != NULL );
  assume( !(nCoeff_is_Q(r) || nCoeff_is_transExt(r) || nCoeff_is_algExt(r)) );
  assume( nCoeff_is_Ring(r) || nCoeff_is_Zp(r) || nCoeff_is_numeric(r) || nCoeff_is_GF(r) );

  d = n_Init(1, r);
}

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

static

Definition at line 275 of file numbers.cc.

{
  /* test, if r is an instance of nInitCoeffs(n,parameter) */
  /* if parameter is not needed */
  return (n==r->type);

static char* ndCoeffName ( const coeffs  r )

static

Definition at line 142 of file numbers.cc.

{ return r->cfCoeffString(r); }

static char* ndCoeffString ( const coeffs  r )

static

Definition at line 54 of file numbers.cc.

{
  char *s=(char *)omAlloc(11);snprintf(s,11,"Coeffs(%d)",r->type);
  return s;
}

static number ndConvFactoryNSingN ( const CanonicalForm  , const coeffs    )

static

[in, out] a bigint number >= 0

[out] the GMP equivalent

Definition at line 256 of file numbers.cc.

static CanonicalForm ndConvSingNFactoryN ( number  , BOOLEAN  , const coeffs    )

static

Definition at line 249 of file numbers.cc.

{
  CanonicalForm term(0);
  Werror("no conversion to factory");
  return term;
}

static number ndCopy ( number  a, const coeffs    )

static

Definition at line 227 of file numbers.cc.

{ return a; }

number ndCopyMap	(	number	a,
		const coeffs	aRing,
		const coeffs	r
	)

Definition at line 228 of file numbers.cc.

{
  assume( getCoeffType(r) == getCoeffType(aRing) );
  if ( nCoeff_has_simple_Alloc(r) && nCoeff_has_simple_Alloc(aRing) )
    return a;
  else
    return r->cfCopy(a, r);
}

static BOOLEAN ndDBTest ( number  , const char *  , const int  , const coeffs    )

static

Definition at line 95 of file numbers.cc.

{ return TRUE; }

static void ndDelete ( number *  d, const coeffs    )

static

Definition at line 52 of file numbers.cc.

{ *d=NULL; }

static BOOLEAN ndDivBy ( number  , number  , const coeffs    )

static

Definition at line 243 of file numbers.cc.

{ return TRUE; } // assume a,b !=0

static int ndDivComp ( number  , number  , const coeffs    )

static

Definition at line 244 of file numbers.cc.

{ return 2; }

static number ndExtGcd ( number  , number  , number *  , number *  , const coeffs  r  )

static

Definition at line 246 of file numbers.cc.

{ return r->cfInit(1,r); }

static number ndFarey ( number  , number  , const coeffs  r  )

static

Definition at line 98 of file numbers.cc.

{
  Werror("farey not implemented for %s (c=%d)",r->cfCoeffString(r),getCoeffType(r));
  return NULL;
}

static number ndGcd ( number  , number  , const coeffs  r  )

static

Definition at line 137 of file numbers.cc.

{ return r->cfInit(1,r); }

static number ndGetDenom ( number &  , const coeffs  r  )

static

Definition at line 139 of file numbers.cc.

{ return r->cfInit(1,r); }

static number ndGetNumerator ( number &  a, const coeffs  r  )

static

Definition at line 140 of file numbers.cc.

{ return r->cfCopy(a,r); }

static number ndInitMPZ ( mpz_t  m, const coeffs  r  )

static

Definition at line 269 of file numbers.cc.

{
  return r->cfInit( mpz_get_si(m), r);

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

static

Definition at line 65 of file numbers.cc.

{
  number n=r->cfAdd(a,b,r);
  r->cfDelete(&a,r);
  a=n;
}

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

static

Definition at line 59 of file numbers.cc.

{
  number n=r->cfMult(a,b,r);
  r->cfDelete(&a,r);
  a=n;
}

static number ndIntMod ( number  , number  , const coeffs  r  )

static

Definition at line 138 of file numbers.cc.

{ return r->cfInit(0,r); }

static BOOLEAN ndIsUnit ( number  a, const coeffs  r  )

static

Definition at line 245 of file numbers.cc.

{ return !r->cfIsZero(a,r); }

static void ndKillChar ( coeffs  )

static

Definition at line 237 of file numbers.cc.

{}

static void ndMPZ ( mpz_t  result, number &  n, const coeffs  r  )

static

Converts a non-negative bigint number into a GMP number.

Definition at line 264 of file numbers.cc.

{
  mpz_init_set_si( result, r->cfInt(n, r) );

static void ndNormalize ( number &  , const coeffs    )

static

Definition at line 135 of file numbers.cc.

{ }

static number ndParameter ( const int  , const coeffs  r  )

static

Definition at line 114 of file numbers.cc.

{
  Werror("ndParameter: n_Parameter is not implemented/relevant for (coeff_type = %d)",getCoeffType(r));
  return NULL;
}

static int ndParDeg ( number  n, const coeffs  r  )

static

Definition at line 109 of file numbers.cc.

{
  return (-r->cfIsZero(n,r));
}

static void ndPower ( number  a, int  i, number *  res, const coeffs  r  )

static

Definition at line 72 of file numbers.cc.

{
  if (i==0) {
    *res = r->cfInit(1, r);
  } else if (i==1) {
    *res = r->cfCopy(a, r);
  } else if (i==2) {
    *res = r->cfMult(a, a, r);
  } else if (i<0) {
    number b = r->cfInvers(a, r);
    ndPower(b, -i, res, r);
    r->cfDelete(&b, r);
  } else {
    ndPower(a, i/2, res, r);
    r->cfInpMult(*res, *res, r);
    if (i&1) {
      r->cfInpMult(*res, a, r);
    }
  }
}

static number ndReturn0 ( number  , const coeffs  r  )

static

Definition at line 136 of file numbers.cc.

{ return r->cfInit(0,r); }

static void ndSetChar ( const coeffs  )

static

Definition at line 238 of file numbers.cc.

{}

static int ndSize ( number  a, const coeffs  r  )

static

Definition at line 141 of file numbers.cc.

{ return (int)r->cfIsZero(a,r)==FALSE; }

coeffs nInitChar	(	n_coeffType	t,
		void *	parameter
	)

one-time initialisations for new coeffs in case of an error return NULL

Definition at line 316 of file numbers.cc.

{
  n_Procs_s *n=cf_root;

  while((n!=NULL) && (n->nCoeffIsEqual!=NULL) && (!n->nCoeffIsEqual(n,t,parameter)))
      n=n->next;

  if (n==NULL)
  {
    n=(n_Procs_s*)omAlloc0(sizeof(n_Procs_s));
    n->next=cf_root;
    n->ref=1;
    n->type=t;

    // default entries (different from NULL) for some routines:
    n->nCoeffIsEqual = ndCoeffIsEqual;
    n->cfSize = ndSize;
    n->cfGetDenom= ndGetDenom;
    n->cfGetNumerator= ndGetNumerator;
    n->cfImPart=ndReturn0;
    n->cfDelete= ndDelete;
    n->cfAnn = ndAnn;
    n->cfCoeffString = ndCoeffString; // should alway be changed!
    n->cfInpMult=ndInpMult;
    n->cfInpAdd=ndInpAdd;
    n->cfCopy = ndCopy;
    n->cfIntMod=ndIntMod; /* dummy !! */
    n->cfNormalize=ndNormalize;
    n->cfGcd  = ndGcd;
    n->cfNormalizeHelper  = ndGcd; /* tricky, isn't it ?*/
    n->cfLcm  = ndGcd; /* tricky, isn't it ?*/
    n->cfInitMPZ = ndInitMPZ;
    n->cfMPZ = ndMPZ;
    n->cfPower = ndPower;
    n->cfCoeffName = ndCoeffName;

    n->cfKillChar = ndKillChar; /* dummy */
    n->cfSetChar = ndSetChar; /* dummy */
    // temp. removed to catch all the coeffs which miss to implement this!

    n->cfChineseRemainder = ndChineseRemainder;
    n->cfFarey = ndFarey;
    n->cfParDeg = ndParDeg;

    n->cfParameter = ndParameter;

    n->cfClearContent = ndClearContent;
    n->cfClearDenominators = ndClearDenominators;

#ifdef HAVE_RINGS
    n->cfDivComp = ndDivComp;
    n->cfDivBy = ndDivBy;
    n->cfIsUnit = ndIsUnit;
    n->cfExtGcd = ndExtGcd;
    //n->cfGetUnit = (nMapFunc)NULL;
#endif

#ifdef LDEBUG
    n->cfDBTest=ndDBTest;
#endif

    n->convSingNFactoryN=ndConvSingNFactoryN;
    n->convFactoryNSingN=ndConvFactoryNSingN;

    BOOLEAN nOK=TRUE;
    // init
    if ((t<=nLastCoeffs) && (nInitCharTable[t]!=NULL))
      nOK = (nInitCharTable[t])(n,parameter);
    else
       Werror("Sorry: the coeff type [%d] was not registered: it is missing in nInitCharTable", (int)t);
    if (nOK)
    {
      omFreeSize(n,sizeof(*n));
      return NULL;
    }
    cf_root=n;
    // post init settings:
    if (n->cfRePart==NULL) n->cfRePart=n->cfCopy;
    if (n->cfExactDiv==NULL) n->cfExactDiv=n->cfDiv;
    if (n->cfSubringGcd==NULL) n->cfSubringGcd=n->cfGcd;

#ifdef HAVE_RINGS
    if (n->cfGetUnit==NULL) n->cfGetUnit=n->cfCopy;
#endif

    if(n->cfWriteShort==NULL)
      n->cfWriteShort = n->cfWriteLong;

    assume(n->nCoeffIsEqual!=NULL);
    assume(n->cfSetChar!=NULL);
    assume(n->cfCoeffString!=ndCoeffString);
    assume(n->cfMult!=NULL);
    assume(n->cfSub!=NULL);
    assume(n->cfAdd!=NULL);
    assume(n->cfDiv!=NULL);
    assume(n->cfIntMod!=NULL);
    assume(n->cfExactDiv!=NULL);
    assume(n->cfInit!=NULL);
    assume(n->cfInitMPZ!=NULL);
    assume(n->cfSize!=NULL);
    assume(n->cfInt!=NULL);
    assume(n->cfMPZ!=NULL);
    //assume(n->n->cfDivComp!=NULL);
    //assume(n->cfIsUnit!=NULL);
    //assume(n->cfGetUnit!=NULL);
    //assume(n->cfExtGcd!=NULL);
    assume(n->cfInpNeg!=NULL);
    assume(n->cfCopy!=NULL);

    assume(n->cfWriteLong!=NULL);
    assume(n->cfWriteShort!=NULL);

    assume(n->iNumberOfParameters>= 0);

    assume( (n->iNumberOfParameters == 0 && n->pParameterNames == NULL) ||
            (n->iNumberOfParameters >  0 && n->pParameterNames != NULL) );

    assume(n->cfParameter!=NULL);
    assume(n->cfParDeg!=NULL);

    assume(n->cfRead!=NULL);
    assume(n->cfNormalize!=NULL);
    assume(n->cfGreater!=NULL);
    //assume(n->cfDivBy!=NULL);
    assume(n->cfEqual!=NULL);
    assume(n->cfIsZero!=NULL);
    assume(n->cfIsOne!=NULL);
    assume(n->cfIsMOne!=NULL);
    assume(n->cfGreaterZero!=NULL);
    assume(n->cfGetDenom!=NULL);
    assume(n->cfGetNumerator!=NULL);
    assume(n->cfGcd!=NULL);
    assume(n->cfNormalizeHelper!=NULL);
    assume(n->cfDelete!=NULL);
    assume(n->cfSetMap!=NULL);
    assume(n->cfInpMult!=NULL);
//    assume(n->cfInit_bigint!=NULL);
    assume(n->cfCoeffWrite != NULL);

    assume(n->cfClearContent != NULL);
    assume(n->cfClearDenominators != NULL);

    assume(n->type==t);

#ifndef SING_NDEBUG
    if(n->cfKillChar==NULL) Warn("cfKillChar is NULL for coeff %d",t);
    if(n->cfWriteLong==NULL) Warn("cfWrite is NULL for coeff %d",t);
    if(n->cfWriteShort==NULL) Warn("cfWriteShort is NULL for coeff %d",t);
    if(n->cfCoeffString==ndCoeffString) Warn("cfCoeffString is undefined for coeff %d",t);
#endif

   if( n->nNULL == NULL )
     n->nNULL = n->cfInit(0, n); // may still remain NULL
  }
  else
  {
    n->ref++;
  }
  return n;

void nKillChar

(

coeffs

r

)

undo all initialisations

Definition at line 477 of file numbers.cc.

{
  STATISTIC(nKillChar);
  if (r!=NULL)
  {
    r->ref--;
    if (r->ref<=0)
    {
      n_Procs_s tmp;
      n_Procs_s* n=&tmp;
      tmp.next=cf_root;
      while((n->next!=NULL) && (n->next!=r)) n=n->next;
      if (n->next==r)
      {
        n->next=n->next->next;
        if (cf_root==r) cf_root=n->next;
        n_Delete(&(r->nNULL),r);
        assume (r->cfKillChar!=NULL); r->cfKillChar(r); // STATISTIC(nKillChar);
        omFreeSize((void *)r, sizeof(n_Procs_s));
        r=NULL;
      }
      else
      {
        WarnS("cf_root list destroyed");
      }
    }
  }

void nNew

(

number *

d

)

Definition at line 49 of file numbers.cc.

{ *d=NULL; }

n_coeffType nRegister	(	n_coeffType	n,
		cfInitCharProc	p
	)

Definition at line 507 of file numbers.cc.

{
  if (n==n_unknown)
  {
    nLastCoeffs=(n_coeffType)(int(nLastCoeffs)+1);
    if (nInitCharTable==nInitCharTableDefault)
    {
      nInitCharTable=(cfInitCharProc*)omAlloc0(
                                          ((int)nLastCoeffs+1)*sizeof(cfInitCharProc));
      memcpy(nInitCharTable,nInitCharTableDefault,
              ((int)nLastCoeffs)*sizeof(cfInitCharProc));
    }
    else
    {
      nInitCharTable=(cfInitCharProc*)omReallocSize(nInitCharTable,
                                          ((int)nLastCoeffs)*sizeof(cfInitCharProc),
                                          (((int)nLastCoeffs)+1)*sizeof(cfInitCharProc));
    }

    nInitCharTable[nLastCoeffs]=p;
    return nLastCoeffs;
  }
  else
  {
    if (nInitCharTable[n]!=NULL) Print("coeff %d already initialized\n",n);
    nInitCharTable[n]=p;
    return n;
  }

Variable Documentation

n_Procs_s* cf_root =NULL

Definition at line 47 of file numbers.cc.

cfInitCharProc* nInitCharTable =nInitCharTableDefault

static

Definition at line 312 of file numbers.cc.

cfInitCharProc nInitCharTableDefault[]

Initial value:

=
{ NULL,        
 npInitChar,   
 nlInitChar,   
 nrInitChar,   
 nfInitChar,   
 ngfInitChar,  

 naInitChar,  
 ntInitChar,  




 ngcInitChar,  

 nrzInitChar,  
 nrnInitChar,  
 nrnInitChar,  
 nr2mInitChar, 






 NULL         
}

Definition at line 283 of file numbers.cc.

n_coeffType nLastCoeffs =n_CF

static

Definition at line 282 of file numbers.cc.