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
static BOOLEAN	npGreaterZero (number k, const coeffs r)
static BOOLEAN	npIsMOne (number a, const coeffs r)
static number	npDiv (number a, number b, const coeffs r)
static number	npNeg (number c, const coeffs r)
static number	npInvers (number c, const coeffs r)
static BOOLEAN	npGreater (number a, number b, const coeffs r)
static BOOLEAN	npEqual (number a, number b, const coeffs r)
static void	npWrite (number a, const coeffs r)
static const char *	npRead (const char *s, number *a, const coeffs r)
static void	nvInpMult (number &a, number b, const coeffs r)
static BOOLEAN	npDBTest (number a, const char *f, const int l, const coeffs r)
static nMapFunc	npSetMap (const coeffs src, const coeffs dst)
static 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)
long	npInt (number &n, 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 void	npWriteFd_S (number n, const coeffs)
static number	npReadFd (const ssiInfo *d, const coeffs)
static number	npReadFd_S (char **s, 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 300 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 276 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 287 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 281 of file modulop.cc.

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

npDBTest()

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

static

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

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

static

Definition at line 98 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 214 of file modulop.cc.

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

npEqual()

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

static

Definition at line 174 of file modulop.cc.

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

npGreater()

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

static

Definition at line 165 of file modulop.cc.

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

npGreaterZero()

static BOOLEAN npGreaterZero ( number  k, const coeffs  r  )

static

Definition at line 51 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 351 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;
  //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
  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->cfWriteFd_S=npWriteFd_S;
  r->cfReadFd=npReadFd;
  r->cfReadFd_S=npReadFd_S;
 
  // 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 346 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 68 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 83 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()

static number npInvers ( number  c, const coeffs  r  )

static

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

static BOOLEAN npIsMOne ( number  a, const coeffs  r  )

static

Definition at line 91 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 257 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 611 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 587 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 512 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 605 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 500 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 592 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()

static number npNeg ( number  c, const coeffs  r  )

static

Definition at line 148 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 340 of file modulop.cc.

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

npRandom()

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

static

Definition at line 333 of file modulop.cc.

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

npRead()

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

static

Definition at line 219 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 317 of file modulop.cc.

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

npReadFd_S()

static number npReadFd_S ( char **  s, const coeffs    )

static

Definition at line 325 of file modulop.cc.

{
  // read int
  int dd;
  dd=s_readint_S(s);
  return (number)(long)dd;
}

npSetMap()

static nMapFunc npSetMap ( const coeffs  src, const coeffs  dst  )

static

Definition at line 618 of file modulop.cc.

{
  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;
  }
  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()

static void npWrite ( number  a, const coeffs  r  )

static

Definition at line 184 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 307 of file modulop.cc.

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

npWriteFd_S()

static void npWriteFd_S ( number  n, const coeffs    )

static

Definition at line 312 of file modulop.cc.

{
  StringAppend("%d ",(int)(long)n);
}

nvDiv()

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

static

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

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

static

Definition at line 655 of file modulop.cc.

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

nvInvers()

number nvInvers	(	number	c,
		const coeffs	r
	)

Definition at line 682 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 661 of file modulop.cc.

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