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 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 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 476 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 338 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 333 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 600 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 575 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 499 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 593 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 487 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 580 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 327 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 320 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 312 of file modulop.cc.

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

npSetMap()

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

static

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

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

nvDiv()

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

static

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

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

nvInvers()

number nvInvers	(	number	c,
		const coeffs	r
	)

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

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