modulop.cc File Reference

#include "misc/auxiliary.h"
#include "factory/factory.h"
#include "misc/mylimits.h"
#include "misc/sirandom.h"
#include "reporter/reporter.h"
#include "coeffs/coeffs.h"
#include "coeffs/numbers.h"
#include "coeffs/mpr_complex.h"
#include "coeffs/longrat.h"
#include "coeffs/modulop.h"
#include <string.h>
#include "coeffs/modulop_inl.h"

Go to the source code of this file.

Functions
BOOLEAN	npGreaterZero (number k, const coeffs r)
long	npInt (number &n, const coeffs r)
void	npPower (number a, int i, number *result, const coeffs r)
BOOLEAN	npIsMOne (number a, const coeffs r)
number	npDiv (number a, number b, const coeffs r)
number	npNeg (number c, const coeffs r)
number	npInvers (number c, const coeffs r)
BOOLEAN	npGreater (number a, number b, const coeffs r)
BOOLEAN	npEqual (number a, number b, const coeffs r)
void	npWrite (number a, const coeffs r)
const char *	npRead (const char *s, number *a, const coeffs r)
void	nvInpMult (number &a, number b, const coeffs r)
BOOLEAN	npDBTest (number a, const char *f, const int l, const coeffs r)
nMapFunc	npSetMap (const coeffs src, const coeffs dst)
number	nvDiv (number a, number b, const coeffs r)
number	nvInvers (number c, const coeffs r)
void	npInpMult (number &a, number b, const coeffs r)
static const char *	npEati (const char *s, int *i, const coeffs r)
void	npKillChar (coeffs r)
static BOOLEAN	npCoeffsEqual (const coeffs r, n_coeffType n, void *parameter)
CanonicalForm	npConvSingNFactoryN (number n, BOOLEAN setChar, const coeffs r)
number	npConvFactoryNSingN (const CanonicalForm n, const coeffs r)
static char *	npCoeffName (const coeffs cf)
static void	npWriteFd (number n, const ssiInfo *d, const coeffs)
static number	npReadFd (const ssiInfo *d, const coeffs)
static number	npRandom (siRandProc p, number, number, const coeffs cf)
static number	npPar (int, coeffs r)
static number	npInitMPZ (mpz_t m, const coeffs r)
BOOLEAN	npInitChar (coeffs r, void *p)
static number	npMapP (number from, const coeffs src, const coeffs dst_r)
static number	npMapLongR (number from, const coeffs, const coeffs dst_r)
static number	npMapGMP (number from, const coeffs, const coeffs dst)
static number	npMapZ (number from, const coeffs src, const coeffs dst)
static number	npMapMachineInt (number from, const coeffs, const coeffs dst)
static number	npMapCanonicalForm (number a, const coeffs, const coeffs dst)
static number	nvInversM (number c, const coeffs r)

Function Documentation

npCoeffName()

static char * npCoeffName ( const coeffs  cf )

static

Definition at line 302 of file modulop.cc.

{
  STATIC_VAR char npCoeffName_buf[15];
  snprintf(npCoeffName_buf,14,"ZZ/%d",cf->ch);
  return npCoeffName_buf;
}

npCoeffsEqual()

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

static

Definition at line 278 of file modulop.cc.

{
  /* test, if r is an instance of nInitCoeffs(n,parameter) */
  return (n==n_Zp) && (r->ch==(int)(long)parameter);
}

npConvFactoryNSingN()

number npConvFactoryNSingN	(	const CanonicalForm	n,
		const coeffs	r
	)

Definition at line 289 of file modulop.cc.

{
  if (n.isImm())
  {
    return npInit(n.intval(),r);
  }
  else
  {
    assume(0);
    return NULL;
  }
}

npConvSingNFactoryN()

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

Definition at line 283 of file modulop.cc.

{
  if (setChar) setCharacteristic( r->ch );
  return CanonicalForm(npInt( n,r ));
}

npDBTest()

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

Definition at line 478 of file modulop.cc.

{
  if (((long)a<0L) || ((long)a>(long)r->ch))
  {
    Print("wrong mod p number %ld at %s,%d\n",(long)a,f,l);
    return FALSE;
  }
  return TRUE;
}

npDiv()

number npDiv	(	number	a,
		number	b,
		const coeffs	r
	)

Definition at line 100 of file modulop.cc.

{
  n_Test(a, r);
  n_Test(b, r);
 
  if ((long)b==0L)
  {
    WerrorS(nDivBy0);
    return (number)0L;
  }
  if ((long)a==0) return (number)0L;
 
  number d;
#ifndef HAVE_GENERIC_MULT
  int s = r->npLogTable[(long)a] - r->npLogTable[(long)b];
  #ifdef HAVE_GENERIC_ADD
    if (s < 0)
      s += r->npPminus1M;
  #else
    #if SIZEOF_LONG == 8
    s += ((long)s >> 63) & r->npPminus1M;
    #else
    s += ((long)s >> 31) & r->npPminus1M;
    #endif
  #endif
  d = (number)(long)r->npExpTable[s];
#else
  number inv=npInversM(b,r);
  d = npMultM(a,inv,r);
#endif
 
  n_Test(d, r);
  return d;
 
}

npEati()

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

inlinestatic

Definition at line 216 of file modulop.cc.

{
  return nEati((char *)s,i,(int)r->ch);
}

npEqual()

BOOLEAN npEqual	(	number	a,
		number	b,
		const coeffs	r
	)

Definition at line 176 of file modulop.cc.

{
  n_Test(a, r);
  n_Test(b, r);
 
//  return (long)a == (long)b;
 
  return npEqualM(a,b,r);
}

npGreater()

BOOLEAN npGreater	(	number	a,
		number	b,
		const coeffs	r
	)

Definition at line 167 of file modulop.cc.

{
  n_Test(a, r);
  n_Test(b, r);
 
  //return (long)a != (long)b;
  return ((long)a) > ((long)b);
}

npGreaterZero()

BOOLEAN npGreaterZero	(	number	k,
		const coeffs	r
	)

Definition at line 53 of file modulop.cc.

{
  n_Test(k, r);
 
  int h = (int)((long) k);
  return ((int)h !=0) && (h <= (r->ch>>1));
}

npInitChar()

BOOLEAN npInitChar	(	coeffs	r,
		void *	p
	)

Definition at line 340 of file modulop.cc.

{
  assume( getCoeffType(r) == n_Zp );
  const int c = (int) (long) p;
 
  assume( c > 0 );
 
  int i, w;
 
  r->is_field=TRUE;
  r->is_domain=TRUE;
  r->rep=n_rep_int;
 
  r->ch = c;
  r->npPminus1M = c /*r->ch*/ - 1;
 
  //r->cfInitChar=npInitChar;
  r->cfKillChar=npKillChar;
  r->nCoeffIsEqual=npCoeffsEqual;
  r->cfCoeffName=npCoeffName;
 
  r->cfMult  = npMult;
  r->cfInpMult  = npInpMult;
  r->cfSub   = npSubM;
  r->cfAdd   = npAddM;
  r->cfInpAdd   = npInpAddM;
  r->cfDiv   = npDiv;
  r->cfInit = npInit;
  //r->cfSize  = ndSize;
  r->cfInt  = npInt;
  r->cfInitMPZ = npInitMPZ;
  #ifdef HAVE_RINGS
  //r->cfDivComp = NULL; // only for ring stuff
  //r->cfIsUnit = NULL; // only for ring stuff
  //r->cfGetUnit = NULL; // only for ring stuff
  //r->cfExtGcd = NULL; // only for ring stuff
  // r->cfDivBy = NULL; // only for ring stuff
  #endif
  r->cfInpNeg   = npNeg;
  r->cfInvers= npInvers;
  //r->cfCopy  = ndCopy;
  //r->cfRePart = ndCopy;
  //r->cfImPart = ndReturn0;
  r->cfWriteLong = npWrite;
  r->cfRead = npRead;
  //r->cfNormalize=ndNormalize;
  r->cfGreater = npGreater;
  r->cfEqual = npEqual;
  r->cfIsZero = npIsZero;
  r->cfIsOne = npIsOne;
  r->cfIsMOne = npIsMOne;
  r->cfGreaterZero = npGreaterZero;
  //r->cfPower = npPower;
  //r->cfGetDenom = ndGetDenom;
  //r->cfGetNumerator = ndGetNumerator;
  //r->cfGcd  = ndGcd;
  //r->cfLcm  = ndGcd;
  //r->cfDelete= ndDelete;
  r->cfSetMap = npSetMap;
  //r->cfName = ndName;
  //r->cfInpMult=ndInpMult;
  r->convSingNFactoryN=npConvSingNFactoryN;
  r->convFactoryNSingN=npConvFactoryNSingN;
  r->cfRandom=npRandom;
#ifdef LDEBUG
  // debug stuff
  r->cfDBTest=npDBTest;
#endif
 
  // io via ssi
  r->cfWriteFd=npWriteFd;
  r->cfReadFd=npReadFd;
 
  // the variables:
  r->type = n_Zp;
  r->has_simple_Alloc=TRUE;
  r->has_simple_Inverse=TRUE;
 
  // the tables
#ifdef NV_OPS
  if (r->ch <=NV_MAX_PRIME)
#endif
  {
#ifdef HAVE_INVTABLE
    r->npInvTable=(unsigned short*)omAlloc0( r->ch*sizeof(unsigned short) );
#endif
#ifndef HAVE_GENERIC_MULT
    r->cfParameter=npPar; /* Singular.jl */
    r->npExpTable=(unsigned short *)omAlloc0( r->ch*sizeof(unsigned short) );
    r->npLogTable=(unsigned short *)omAlloc0( r->ch*sizeof(unsigned short) );
    r->npExpTable[0] = 1;
    r->npLogTable[0] = 0;
    if (r->ch > 2)
    {
      w = 1;
      loop
      {
        r->npLogTable[1] = 0;
        w++;
        i = 0;
        loop
        {
          i++;
          r->npExpTable[i] =(int)(((long)w * (long)r->npExpTable[i-1]) % r->ch);
          r->npLogTable[r->npExpTable[i]] = i;
          if /*(i == r->ch - 1 ) ||*/ (/*(*/ r->npExpTable[i] == 1 /*)*/)
            break;
        }
        if (i == r->ch - 1)
          break;
      }
    }
    else
    {
      r->npExpTable[1] = 1;
      r->npLogTable[1] = 0;
    }
#endif
  }
#ifdef NV_OPS
  else /*if (c>NV_MAX_PRIME)*/
  {
    r->cfMult  = nvMult;
    r->cfDiv   = nvDiv;
    r->cfExactDiv = nvDiv;
    r->cfInvers  = nvInvers;
    r->cfInpMult = nvInpMult;
    //r->cfPower= nvPower;
    //if (c>FACTORY_MAX_PRIME) // factory will catch this error
    //{
    //  r->convSingNFactoryN=ndConvSingNFactoryN;
    //}
  }
#endif
  return FALSE;
}

npInitMPZ()

static number npInitMPZ ( mpz_t  m, const coeffs  r  )

static

Definition at line 335 of file modulop.cc.

{
  return (number)mpz_fdiv_ui(m, r->ch);
}

npInpMult()

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

Definition at line 70 of file modulop.cc.

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

npInt()

long npInt	(	number &	n,
		const coeffs	r
	)

Definition at line 85 of file modulop.cc.

{
  n_Test(n, r);
 
  if ((long)n > (((long)r->ch) >>1)) return ((long)n -((long)r->ch));
  else                               return ((long)n);
}

npInvers()

number npInvers	(	number	c,
		const coeffs	r
	)

Definition at line 135 of file modulop.cc.

{
  n_Test(c, r);
 
  if ((long)c==0L)
  {
    WerrorS("1/0");
    return (number)0L;
  }
  number d = npInversM(c,r);
 
  n_Test(d, r);
  return d;
}

npIsMOne()

BOOLEAN npIsMOne	(	number	a,
		const coeffs	r
	)

Definition at line 93 of file modulop.cc.

{
  n_Test(a, r);
 
  return ((r->npPminus1M == (long)a) &&(1L!=(long)a))/*for char 2*/;
}

npKillChar()

void npKillChar

(

coeffs

r

)

Definition at line 259 of file modulop.cc.

{
  #ifdef HAVE_INVTABLE
  if (r->npInvTable!=NULL)
  {
    omFreeSize( (void *)r->npInvTable, r->ch*sizeof(unsigned short) );
    r->npInvTable=NULL;
  }
  #endif
  #ifndef HAVE_GENERIC_MULT
  if (r->npExpTable!=NULL)
  {
    omFreeSize( (void *)r->npExpTable, r->ch*sizeof(unsigned short) );
    omFreeSize( (void *)r->npLogTable, r->ch*sizeof(unsigned short) );
    r->npExpTable=NULL; r->npLogTable=NULL;
  }
  #endif
}

npMapCanonicalForm()

static number npMapCanonicalForm ( number  a, const  coeffs, const coeffs  dst  )

static

Definition at line 602 of file modulop.cc.

{
  setCharacteristic (dst ->ch);
  CanonicalForm f= CanonicalForm ((InternalCF*)(a));
  return (number) (f.intval());
}

npMapGMP()

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

static

Definition at line 577 of file modulop.cc.

{
  return (number)mpz_fdiv_ui((mpz_ptr) from, dst->ch);
}

npMapLongR()

static number npMapLongR ( number  from, const  coeffs, const coeffs  dst_r  )

static

Definition at line 501 of file modulop.cc.

{
  gmp_float *ff=(gmp_float*)from;
  mpf_t *f=ff->_mpfp();
  number res;
  mpz_ptr dest,ndest;
  int size,i;
  int e,al,bl;
  long iz;
  mp_ptr qp,dd,nn;
 
  size = (*f)[0]._mp_size;
  if (size == 0)
    return npInit(0,dst_r);
  if(size<0)
    size = -size;
 
  qp = (*f)[0]._mp_d;
  while(qp[0]==0)
  {
    qp++;
    size--;
  }
 
  if(dst_r->ch>2)
    e=(*f)[0]._mp_exp-size;
  else
    e=0;
  res = ALLOC_RNUMBER();
#if defined(LDEBUG)
  res->debug=123456;
#endif
  dest = res->z;
 
  long in=0;
  if (e<0)
  {
    al = dest->_mp_size = size;
    if (al<2) al = 2;
    dd = (mp_ptr)omAlloc(sizeof(mp_limb_t)*al);
    for (i=0;i<size;i++) dd[i] = qp[i];
    bl = 1-e;
    nn = (mp_ptr)omAlloc(sizeof(mp_limb_t)*bl);
    nn[bl-1] = 1;
    for (i=bl-2;i>=0;i--) nn[i] = 0;
    ndest = res->n;
    ndest->_mp_d = nn;
    ndest->_mp_alloc = ndest->_mp_size = bl;
    res->s = 0;
    in=mpz_fdiv_ui(ndest,dst_r->ch);
    mpz_clear(ndest);
  }
  else
  {
    al = dest->_mp_size = size+e;
    if (al<2) al = 2;
    dd = (mp_ptr)omAlloc(sizeof(mp_limb_t)*al);
    for (i=0;i<size;i++) dd[i+e] = qp[i];
    for (i=0;i<e;i++) dd[i] = 0;
    res->s = 3;
  }
 
  dest->_mp_d = dd;
  dest->_mp_alloc = al;
  iz=mpz_fdiv_ui(dest,dst_r->ch);
  mpz_clear(dest);
  if(res->s==0)
    iz=(long)npDiv((number)iz,(number)in,dst_r);
  FREE_RNUMBER(res); // Q!?
  return (number)iz;
}

npMapMachineInt()

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

static

Definition at line 595 of file modulop.cc.

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

npMapP()

static number npMapP ( number  from, const coeffs  src, const coeffs  dst_r  )

static

Definition at line 489 of file modulop.cc.

{
  long i = (long)from;
  if (i>src->ch/2)
  {
    i-=src->ch;
    while (i < 0) i+=dst_r->ch;
  }
  i%=dst_r->ch;
  return (number)i;
}

npMapZ()

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

static

Definition at line 582 of file modulop.cc.

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

npNeg()

number npNeg	(	number	c,
		const coeffs	r
	)

Definition at line 150 of file modulop.cc.

{
  n_Test(c, r);
 
  if ((long)c==0L) return c;
 
#if 0
  number d = npNegM(c,r);
  n_Test(d, r);
  return d;
#else
  c = npNegM(c,r);
  n_Test(c, r);
  return c;
#endif
}

npPar()

static number npPar ( int  , coeffs  r  )

static

Definition at line 329 of file modulop.cc.

{
  return (number)(long)r->npExpTable[1];
}

npPower()

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

npRandom()

static number npRandom ( siRandProc  p, number  , number  , const coeffs  cf  )

static

Definition at line 322 of file modulop.cc.

{
  return npInit(p(),cf);
}

npRead()

const char * npRead	(	const char *	s,
		number *	a,
		const coeffs	r
	)

Definition at line 221 of file modulop.cc.

{
  int z;
  int n=1;
 
  s = npEati(s, &z, r);
  if ((*s) == '/')
  {
    s++;
    s = npEati(s, &n, r);
  }
  if (n == 1)
    *a = (number)(long)z;
  else
  {
    if ((z==0)&&(n==0))
    {
      WerrorS(nDivBy0);
      *a=(number)0L;
    }
    else
    {
#ifdef NV_OPS
      if (r->ch>NV_MAX_PRIME)
        *a = nvDiv((number)(long)z,(number)(long)n,r);
      else
#endif
        *a = npDiv((number)(long)z,(number)(long)n,r);
    }
  }
  n_Test(*a, r);
  return s;
}

npReadFd()

static number npReadFd ( const ssiInfo *  d, const  coeffs  )

static

Definition at line 314 of file modulop.cc.

{
  // read int
  int dd;
  dd=s_readint(d->f_read);
  return (number)(long)dd;
}

npSetMap()

nMapFunc npSetMap	(	const coeffs	src,
		const coeffs	dst
	)

Definition at line 609 of file modulop.cc.

{
#ifdef HAVE_RINGS
  if ((src->rep==n_rep_int) && nCoeff_is_Ring_2toM(src))
  {
    return npMapMachineInt;
  }
  if (src->rep==n_rep_gmp) //nCoeff_is_Z(src) || nCoeff_is_Ring_PtoM(src) || nCoeff_is_Zn(src))
  {
    return npMapGMP;
  }
  if (src->rep==n_rep_gap_gmp) //nCoeff_is_Z(src)
  {
    return npMapZ;
  }
#endif
  if (src->rep==n_rep_gap_rat)  /* Q, Z */
  {
    return nlModP; // npMap0; // FIXME? TODO? // extern number nlModP(number q, const coeffs Q, const coeffs Zp); // Map q \in QQ \to Zp // FIXME!
  }
  if ((src->rep==n_rep_int) &&  nCoeff_is_Zp(src) )
  {
    return npMapP;
  }
  if ((src->rep==n_rep_gmp_float) && nCoeff_is_long_R(src))
  {
    return npMapLongR;
  }
  if (nCoeff_is_CF (src))
  {
    return npMapCanonicalForm;
  }
  return NULL;      /* default */
}

npWrite()

void npWrite	(	number	a,
		const coeffs	r
	)

Definition at line 186 of file modulop.cc.

{
  n_Test(a, r);
 
  if ((long)a>(((long)r->ch) >>1)) StringAppend("-%d",(int)(((long)r->ch)-((long)a)));
  else                             StringAppend("%d",(int)((long)a));
}

npWriteFd()

static void npWriteFd ( number  n, const ssiInfo *  d, const  coeffs  )

static

Definition at line 309 of file modulop.cc.

{
  fprintf(d->f_write,"%d ",(int)(long)n);
}

nvDiv()

number nvDiv	(	number	a,
		number	b,
		const coeffs	r
	)

Definition at line 660 of file modulop.cc.

{
  if ((long)a==0L)
    return (number)0L;
  else if ((long)b==0L)
  {
    WerrorS(nDivBy0);
    return (number)0L;
  }
  else
  {
    number inv=nvInversM(b,r);
    return nvMult(a,inv,r);
  }
}

nvInpMult()

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

Definition at line 648 of file modulop.cc.

{
  number n=nvMult(a,b,r);
  a=n;
}

nvInvers()

number nvInvers	(	number	c,
		const coeffs	r
	)

Definition at line 675 of file modulop.cc.

{
  if ((long)c==0L)
  {
    WerrorS(nDivBy0);
    return (number)0L;
  }
  return nvInversM(c,r);
}

nvInversM()

static number nvInversM ( number  c, const coeffs  r  )

inlinestatic

Definition at line 654 of file modulop.cc.

{
  long inv=npInvMod((long)c,r);
  return (number)inv;
}