Changeset 5e3046 in git for coeffs/ffields.cc


Ignore:
Timestamp:
Jun 22, 2010, 5:47:47 PM (14 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
Children:
a0ce49c7c05b8b409237dc853e846599cae23aea
Parents:
d61b83a9e2debd2805137931b5341399516d2a63
git-author:
Martin Lee <martinlee84@web.de>2010-06-22 17:47:47+02:00
git-committer:
Mohamed Barakat <mohamed.barakat@rwth-aachen.de>2011-11-09 11:55:16+01:00
Message:
modified finite fields
File:
1 edited

Legend:

Unmodified
Added
Removed

  • coeffs/ffields.cc

    rd61b83a r5e3046  
    1717#include <feFopen.h>
    1818
    19 int nfCharQ=0;  /* the number of elemts: q*/
    20 int nfM1;       /*representation of -1*/
    21 int nfCharP=0;  /* the characteristic: p*/
    22 static int nfCharQ1=0; /* q-1 */
    23 unsigned short *nfPlus1Table=NULL; /* the table i=log(z^i) -> log(z^i+1) */
     19
     20//unsigned short *nfPlus1Table=NULL; /* the table i=log(z^i) -> log(z^i+1) */
     21
    2422/* the q's from the table 'fftable' */
    2523unsigned short fftable[]={
    … …  
    128126* debugging: is a a valid representation of a number ?
    129127*/
    130 BOOLEAN nfDBTest (number a, const char *f, const int l)
    131 {
    132   if (((long)a<0L) || ((long)a>(long)nfCharQ))
     128BOOLEAN nfDBTest (number a, const char *f, const int l, const coeffs r)
     129{
     130  if (((long)a<0L) || ((long)a>(long)r->m_nfCharQ))
    133131  {
    134132    Print("wrong %d in %s:%d\n",(int)((long)a),f,l);
    … …  
    138136  do
    139137  {
    140     if (nfPlus1Table[i]>nfCharQ)
    141     {
    142       Print("wrong table %d=%d in %s:%d\n",i,nfPlus1Table[i],f,l);
     138    if (r->m_nfPlus1Table[i]>r->m_nfCharQ)
     139    {
     140      Print("wrong table %d=%d in %s:%d\n",i,r->m_nfPlus1Table[i],f,l);
    143141      return FALSE;
    144142    }
    145143    i++;
    146   } while (i<nfCharQ);
     144  } while (i<r->m_nfCharQ);
    147145  return TRUE;
    148146}
    149 #define nfTest(N) nfDBTest(N,__FILE__,__LINE__)
     147#define nfTest(N, R) nfDBTest(N,__FILE__,__LINE__, R)
    150148#endif
    151149
    … …  
    156154{
    157155#ifdef LDEBUG
    158   nfTest(k);
     156  nfTest(k, r);
    159157#endif
    160158  return !nfIsZero(k, r) && !nfIsMOne(k, r);
    … …  
    167165{
    168166#ifdef LDEBUG
    169   nfTest(a);
    170   nfTest(b);
    171 #endif
    172   if (((long)a == (long)nfCharQ) || ((long)b == (long)nfCharQ))
    173     return (number)(long)nfCharQ;
     167  nfTest(a, r);
     168  nfTest(b, r);
     169#endif
     170  if (((long)a == (long)r->m_nfCharQ) || ((long)b == (long)r->m_nfCharQ))
     171    return (number)(long)r->m_nfCharQ;
    174172  /*else*/
    175173  int i=(int)((long)a+(long)b);
    176   if (i>=nfCharQ1) i-=nfCharQ1;
    177 #ifdef LDEBUG
    178   nfTest((number)(long)i);
     174  if (i>=r->m_nfCharQ1) i-=r->m_nfCharQ1;
     175#ifdef LDEBUG
     176  nfTest((number)(long)i, r);
    179177#endif
    180178  return (number)(long)i;
    … …  
    188186  // Hmm .. this is just to prevent initialization
    189187  // from nfInitChar to go into an infinite loop
    190   if (i==0) return (number)(long)nfCharQ;
    191   while (i <  0)    i += nfCharP;
    192   while (i >= nfCharP) i -= nfCharP;
    193   if (i==0) return (number)(long)nfCharQ;
     188  if (i==0) return (number)(long)r->m_nfCharQ;
     189  while (i <  0)    i += r->m_nfCharP;
     190  while (i >= r->m_nfCharP) i -= r->m_nfCharP;
     191  if (i==0) return (number)(long)r->m_nfCharQ;
    194192  unsigned short c=0;
    195193  while (i>1)
    196194  {
    197     c=nfPlus1Table[c];
     195    c=r->m_nfPlus1Table[c];
    198196    i--;
    199197  }
    200198#ifdef LDEBUG
    201   nfTest((number)(long)c);
     199  nfTest((number)(long)c, r);
    202200#endif
    203201  return (number)(long)c;
    … …  
    218216{
    219217#ifdef LDEBUG
    220   nfTest(n);
    221 #endif
    222   if((long)nfCharQ == (long)n) return -1;
     218  nfTest(n, r);
     219#endif
     220  if((long)r->m_nfCharQ == (long)n) return -1;
    223221  return (int)((long)n);
    224222}
    … …  
    240238*          =z^a*(z^(b-a)+1)  if a<b  */
    241239#ifdef LDEBUG
    242   nfTest(a);
    243   nfTest(b);
    244 #endif
    245   if ((long)nfCharQ == (long)a) return b;
    246   if ((long)nfCharQ == (long)b) return a;
     240  nfTest(a, R);
     241  nfTest(b, R);
     242#endif
     243  if ((long)R->m_nfCharQ == (long)a) return b;
     244  if ((long)R->m_nfCharQ == (long)b) return a;
    247245  long zb,zab,r;
    248246  if ((long)a >= (long)b)
    … …  
    257255  }
    258256#ifdef LDEBUG
    259   nfTest((number)zab);
    260 #endif
    261   if (nfPlus1Table[zab]==nfCharQ) r=(long)nfCharQ; /*if z^(a-b)+1 =0*/
     257  nfTest((number)zab, R);
     258#endif
     259  if (R->m_nfPlus1Table[zab]==R->m_nfCharQ) r=(long)R->m_nfCharQ; /*if z^(a-b)+1 =0*/
    262260  else
    263261  {
    264     r= zb+(long)nfPlus1Table[zab];
    265     if(r>=(long)nfCharQ1) r-=(long)nfCharQ1;
    266   }
    267 #ifdef LDEBUG
    268   nfTest((number)r);
     262    r= zb+(long)R->m_nfPlus1Table[zab];
     263    if(r>=(long)R->m_nfCharQ1) r-=(long)R->m_nfCharQ1;
     264  }
     265#ifdef LDEBUG
     266  nfTest((number)r, R);
    269267#endif
    270268  return (number)r;
    … …  
    286284{
    287285#ifdef LDEBUG
    288   nfTest(a);
    289 #endif
    290   return (long)nfCharQ == (long)a;
     286  nfTest(a, r);
     287#endif
     288  return (long)r->m_nfCharQ == (long)a;
    291289}
    292290
    … …  
    297295{
    298296#ifdef LDEBUG
    299   nfTest(a);
     297  nfTest(a, r);
    300298#endif
    301299  return 0L == (long)a;
    … …  
    308306{
    309307#ifdef LDEBUG
    310   nfTest(a);
     308  nfTest(a, r);
    311309#endif
    312310  if (0L == (long)a) return FALSE; /* special handling of char 2*/
    313   return (long)nfM1 == (long)a;
     311  return (long)r->m_nfM1 == (long)a;
    314312}
    315313
    … …  
    320318{
    321319#ifdef LDEBUG
    322   nfTest(b);
    323 #endif
    324   if ((long)b==(long)nfCharQ)
     320  nfTest(b, r);
     321#endif
     322  if ((long)b==(long)r->m_nfCharQ)
    325323  {
    326324    WerrorS(nDivBy0);
    327     return (number)((long)nfCharQ);
    328   }
    329 #ifdef LDEBUG
    330   nfTest(a);
    331 #endif
    332   if ((long)a==(long)nfCharQ)
    333     return (number)((long)nfCharQ);
     325    return (number)((long)r->m_nfCharQ);
     326  }
     327#ifdef LDEBUG
     328  nfTest(a, r);
     329#endif
     330  if ((long)a==(long)r->m_nfCharQ)
     331    return (number)((long)r->m_nfCharQ);
    334332  /*else*/
    335333  long s = (long)a - (long)b;
    336334  if (s < 0L)
    337     s += (long)nfCharQ1;
    338 #ifdef LDEBUG
    339   nfTest((number)s);
     335    s += (long)r->m_nfCharQ1;
     336#ifdef LDEBUG
     337  nfTest((number)s, r);
    340338#endif
    341339  return (number)s;
    … …  
    348346{
    349347#ifdef LDEBUG
    350   nfTest(c);
    351 #endif
    352   if ((long)c==(long)nfCharQ)
     348  nfTest(c, r);
     349#endif
     350  if ((long)c==(long)r->m_nfCharQ)
    353351  {
    354352    WerrorS(nDivBy0);
    355     return (number)((long)nfCharQ);
    356   }
    357 #ifdef LDEBUG
    358   nfTest(((number)((long)nfCharQ1-(long)c)));
    359 #endif
    360   return (number)((long)nfCharQ1-(long)c);
     353    return (number)((long)r->m_nfCharQ);
     354  }
     355#ifdef LDEBUG
     356  nfTest(((number)((long)r->m_nfCharQ1-(long)c)), r);
     357#endif
     358  return (number)((long)r->m_nfCharQ1-(long)c);
    361359}
    362360
    … …  
    368366/*4 -z^c=z^c*(-1)=z^c*nfM1*/
    369367#ifdef LDEBUG
    370   nfTest(c);
    371 #endif
    372   if ((long)nfCharQ == (long)c) return c;
    373   long i=(long)c+(long)nfM1;
    374   if (i>=(long)nfCharQ1) i-=(long)nfCharQ1;
    375 #ifdef LDEBUG
    376   nfTest((number)i);
     368  nfTest(c, r);
     369#endif
     370  if ((long)r->m_nfCharQ == (long)c) return c;
     371  long i=(long)c+(long)r->m_nfM1;
     372  if (i>=(long)r->m_nfCharQ1) i-=(long)r->m_nfCharQ1;
     373#ifdef LDEBUG
     374  nfTest((number)i, r);
    377375#endif
    378376  return (number)i;
    … …  
    385383{
    386384#ifdef LDEBUG
    387   nfTest(a);
    388   nfTest(b);
     385  nfTest(a, r);
     386  nfTest(b, r);
    389387#endif
    390388  return (long)a != (long)b;
    … …  
    397395{
    398396#ifdef LDEBUG
    399   nfTest(a);
    400   nfTest(b);
     397  nfTest(a, r);
     398  nfTest(b, r);
    401399#endif
    402400  return (long)a == (long)b;
    … …  
    409407{
    410408#ifdef LDEBUG
    411   nfTest(a);
    412 #endif
    413   if ((long)a==(long)nfCharQ)  StringAppendS("0");
     409  nfTest(a, r);
     410#endif
     411  if ((long)a==(long)r->m_nfCharQ)  StringAppendS("0");
    414412  else if ((long)a==0L)   StringAppendS("1");
    415413  else if (nfIsMOne(a, r))   StringAppendS("-1");
    … …  
    431429{
    432430#ifdef LDEBUG
    433   nfTest(a);
     431  nfTest(a, r);
    434432#endif
    435433  char *s;
    436434  char *nfParameter=r->parameter[0];
    437   if (((long)a==(long)nfCharQ) || ((long)a==0L)) return NULL;
     435  if (((long)a==(long)r->m_nfCharQ) || ((long)a==0L)) return NULL;
    438436  else if ((long)a==1L)
    439437  {
    … …  
    453451{
    454452#ifdef LDEBUG
    455   nfTest(a);
     453  nfTest(a, r);
    456454#endif
    457455  if (i==0)
    … …  
    470468  }
    471469#ifdef LDEBUG
    472   nfTest(*result);
     470  nfTest(*result, r);
    473471#endif
    474472}
    … …  
    477475* read an integer (with reduction mod p)
    478476*/
    479 static const char* nfEati(const char *s, int *i)
     477static const char* nfEati(const char *s, int *i, const coeffs r)
    480478{
    481479  if (*s >= '0' && *s <= '9')
    … …  
    486484      *i *= 10;
    487485      *i += *s++ - '0';
    488       if (*i > (INT_MAX / 10)) *i = *i % nfCharP;
     486      if (*i > (INT_MAX / 10)) *i = *i % r->m_nfCharP;
    489487    }
    490488    while (*s >= '0' && *s <= '9');
    491     if (*i >= nfCharP) *i = *i % nfCharP;
     489    if (*i >= r->m_nfCharP) *i = *i % r->m_nfCharP;
    492490  }
    493491  else *i = 1;
    … …  
    504502  number n;
    505503
    506   s = nfEati(s, &i);
     504  s = nfEati(s, &i, r);
    507505  z=nfInit(i, r);
    508506  *a=z;
    … …  
    510508  {
    511509    s++;
    512     s = nfEati(s, &i);
     510    s = nfEati(s, &i, r);
    513511    n=nfInit(i, r);
    514512    *a = nfDiv(z,n,r);
    … …  
    521519    {
    522520      s=eati(s,&i);
    523       while (i>=nfCharQ1) i-=nfCharQ1;
     521      while (i>=r->m_nfCharQ1) i-=r->m_nfCharQ1;
    524522    }
    525523    else
    … …  
    529527  }
    530528#ifdef LDEBUG
    531   nfTest(*a);
     529  nfTest(*a, r);
    532530#endif
    533531  return s;
    … …  
    607605* init global variables from files 'gftables/%d'
    608606*/
    609 void nfSetChar(int c, char **param)
     607void nfReadTable(const int c, const coeffs r)
    610608{
    611609  //Print("GF(%d)\n",c);
    612   if ((c==nfCharQ)||(c==-nfCharQ))
     610  if ((c==r->m_nfCharQ)||(c==-r->m_nfCharQ))
    613611    /*this field is already set*/  return;
    614612  int i=0;
    … …  
    616614  if (fftable[i]==0)
    617615    return;
    618   if (nfCharQ > 1)
    619   {
    620     omFreeSize( (ADDRESS)nfPlus1Table,nfCharQ*sizeof(unsigned short) );
    621     nfPlus1Table=NULL;
     616  if (r->m_nfCharQ > 1)
     617  {
     618    omFreeSize( (ADDRESS)r->m_nfPlus1Table,r->m_nfCharQ*sizeof(unsigned short) );
     619    r->m_nfPlus1Table=NULL;
    622620  }
    623621  if ((c>1) || (c<0))
    624622  {
    625     if (c>1) nfCharQ = c;
    626     else     nfCharQ = -c;
     623    if (c>1) r->m_nfCharQ = c;
     624    else     r->m_nfCharQ = -c;
    627625    char buf[100];
    628     sprintf(buf,"gftables/%d",nfCharQ);
     626    sprintf(buf,"gftables/%d",r->m_nfCharQ);
    629627    FILE * fp = feFopen(buf,"r",NULL,TRUE);
    630628    if (fp==NULL)
    … …  
    642640    }
    643641    int q;
    644     sscanf(buf,"%d %d",&nfCharP,&q);
     642    sscanf(buf,"%d %d",&r->m_nfCharP,&q);
    645643    nfReadMipo(buf);
    646     nfCharQ1=nfCharQ-1;
     644    r->m_nfCharQ1=r->m_nfCharQ-1;
    647645    //Print("nfCharQ=%d,nfCharQ1=%d,mipo=>>%s<<\n",nfCharQ,nfCharQ1,buf);
    648     nfPlus1Table= (unsigned short *)omAlloc( (nfCharQ)*sizeof(unsigned short) );
    649     int digs = gf_tab_numdigits62( nfCharQ );
     646    r->m_nfPlus1Table= (unsigned short *)omAlloc( (r->m_nfCharQ)*sizeof(unsigned short) );
     647    int digs = gf_tab_numdigits62( r->m_nfCharQ );
    650648    char * bufptr;
    651649    int i = 1;
    652650    int k;
    653     while ( i < nfCharQ )
     651    while ( i < r->m_nfCharQ )
    654652    {
    655653      fgets( buf, sizeof(buf), fp);
    … …  
    657655      bufptr = buf;
    658656      k = 0;
    659       while ( (i < nfCharQ) && (k < 30) )
     657      while ( (i < r->m_nfCharQ) && (k < 30) )
    660658      {
    661         nfPlus1Table[i] = convertback62( bufptr, digs );
    662         if(nfPlus1Table[i]>nfCharQ)
     659        r->m_nfPlus1Table[i] = convertback62( bufptr, digs );
     660        if(r->m_nfPlus1Table[i]>r->m_nfCharQ)
    663661        {
    664           Print("wrong entry %d: %d(%c%c%c)\n",i,nfPlus1Table[i],bufptr[0],bufptr[1],bufptr[2]);
     662          Print("wrong entry %d: %d(%c%c%c)\n",i,r->m_nfPlus1Table[i],bufptr[0],bufptr[1],bufptr[2]);
    665663        }
    666664        bufptr += digs;
    667         if (nfPlus1Table[i]==nfCharQ)
     665        if (r->m_nfPlus1Table[i]==r->m_nfCharQ)
    668666        {
    669           if(i==nfCharQ1)
     667          if(i==r->m_nfCharQ1)
    670668          {
    671             nfM1=0;
     669            r->m_nfM1=0;
    672670          }
    673671          else
    674672          {
    675             nfM1=i;
     673            r->m_nfM1=i;
    676674          }
    677675        }
    … …  
    679677      }
    680678    }
    681     nfPlus1Table[0]=nfPlus1Table[nfCharQ1];
     679    r->m_nfPlus1Table[0]=r->m_nfPlus1Table[r->m_nfCharQ1];
    682680  }
    683681  else
    684     nfCharQ=0;
    685 #ifdef LDEBUG
    686   nfTest((number)0);
     682    r->m_nfCharQ=0;
     683#ifdef LDEBUG
     684  nfTest((number)0, r);
    687685#endif
    688686  return;
    689687err:
    690   Werror("illegal GF-table %d",nfCharQ);
     688  Werror("illegal GF-table %d",r->m_nfCharQ);
    691689}
    692690
    … …  
    707705  int i=(long)c;
    708706  i*= nfMapGG_factor;
    709   while (i >nfCharQ1) i-=nfCharQ1;
     707  while (i >src->m_nfCharQ1) i-=src->m_nfCharQ1;
    710708  return (number)((long)i);
    711709}
    … …  
    719717    return (number)(((long)ex) / ((long)nfMapGG_factor));
    720718  else
    721     return (number)(long)nfCharQ; /* 0 */
     719    return (number)(long)src->m_nfCharQ; /* 0 */
    722720}
    723721
    … …  
    727725nMapFunc nfSetMap(const coeffs r, const coeffs src, const coeffs dst)
    728726{
    729   if (nField_is_GF(src,nfCharQ))
     727  if (nField_is_GF(src,src->m_nfCharQ))
    730728  {
    731729    return ndCopyMap;   /* GF(p,n) -> GF(p,n) */
    … …  
    734732  {
    735733    int q=src->ch;
    736     if ((nfCharQ % q)==0) /* GF(p,n1) -> GF(p,n2), n2 > n1 */
     734    if ((src->m_nfCharQ % q)==0) /* GF(p,n1) -> GF(p,n2), n2 > n1 */
    737735    {
    738736      // check if n2 is a multiple of n1
    739737      int n1=1;
    740       int qq=nfCharP;
    741       while(qq!=q) { qq *= nfCharP; n1++; }
     738      int qq=r->m_nfCharP;
     739      while(qq!=q) { qq *= r->m_nfCharP; n1++; }
    742740      int n2=1;
    743       qq=nfCharP;
    744       while(qq!=nfCharQ) { qq *= nfCharP; n2++; }
    745       Print("map %d^%d -> %d^%d\n",nfCharP,n1,nfCharP,n2);
     741      qq=r->m_nfCharP;
     742      while(qq!=src->m_nfCharQ) { qq *= r->m_nfCharP; n2++; }
     743      Print("map %d^%d -> %d^%d\n",r->m_nfCharP,n1,r->m_nfCharP,n2);
    746744      if ((n2 % n1)==0)
    747745      {
    748746        int save_ch=r->ch;
    749747        char **save_par=r->parameter;
    750         nfSetChar(src->ch,src->parameter);
    751         int nn=nfPlus1Table[0];
    752         nfSetChar(save_ch,save_par);
    753         nfMapGG_factor= nfPlus1Table[0] / nn;
    754         Print("nfMapGG_factor=%d (%d / %d)\n",nfMapGG_factor, nfPlus1Table[0], nn);
     748        nfReadTable(src->ch, r);
     749        int nn=r->m_nfPlus1Table[0];
     750        nfReadTable(save_ch, r);
     751        nfMapGG_factor= r->m_nfPlus1Table[0] / nn;
     752        Print("nfMapGG_factor=%d (%d / %d)\n",nfMapGG_factor, r->m_nfPlus1Table[0], nn);
    755753        return nfMapGG;
    756754      }
    … …  
    764762    }
    765763  }
    766   if (nField_is_Zp(src,nfCharP))
     764  if (nField_is_Zp(src,src->m_nfCharP))
    767765  {
    768766    return nfMapP;    /* Z/p -> GF(p,n) */
    … …  
    770768  return NULL;     /* default */
    771769}
     770
     771void nfInitChar(coeffs r,  void * parameter)
     772{
     773
     774
     775  //r->cfInitChar=npInitChar;
     776  //r->cfKillChar=nfKillChar;
     777  r->cfSetChar= NULL;
     778  //r->nCoeffIsEqual=nfCoeffsEqual;
     779
     780  r->cfMult  = nfMult;
     781  r->cfSub   = nfSub;
     782  r->cfAdd   = nfAdd;
     783  r->cfDiv   = nfDiv;
     784  r->cfIntDiv= nfDiv;
     785  //r->cfIntMod= ndIntMod;
     786  r->cfExactDiv= nfDiv;
     787  r->cfInit = nfInit;
     788  //r->cfPar = ndPar;
     789  //r->cfParDeg = ndParDeg;
     790  //r->cfSize  = ndSize;
     791  r->cfInt  = nfInt;
     792  #ifdef HAVE_RINGS
     793  //r->cfDivComp = NULL; // only for ring stuff
     794  //r->cfIsUnit = NULL; // only for ring stuff
     795  //r->cfGetUnit = NULL; // only for ring stuff
     796  //r->cfExtGcd = NULL; // only for ring stuff
     797  // r->cfDivBy = NULL; // only for ring stuff
     798  #endif
     799  r->cfNeg   = nfNeg;
     800  r->cfInvers= nfInvers;
     801  //r->cfCopy  = ndCopy;
     802  //r->cfRePart = ndCopy;
     803  //r->cfImPart = ndReturn0;
     804  r->cfWrite = nfWrite;
     805  r->cfRead = nfRead;
     806  //r->cfNormalize=ndNormalize;
     807  r->cfGreater = nfGreater;
     808  r->cfEqual = nfEqual;
     809  r->cfIsZero = nfIsZero;
     810  r->cfIsOne = nfIsOne;
     811  r->cfIsMOne = nfIsMOne;
     812  r->cfGreaterZero = nfGreaterZero;
     813  r->cfPower = nfPower;
     814  //r->cfGcd  = ndGcd;
     815  //r->cfLcm  = ndGcd;
     816  //r->cfDelete= ndDelete;
     817  r->cfSetMap = nfSetMap;
     818  //r->cfName = ndName;
     819  // debug stuff
     820  r->cfDBTest=nfDBTest;
     821 
     822  // the variables:
     823  r->nNULL = (number)0;
     824  r->type = n_GF;
     825
     826
     827  r->m_nfCharQ = 0;
     828 
     829
     830  r->has_simple_Alloc=TRUE;
     831  r->has_simple_Inverse=TRUE;
     832  const int c = (int)(long)(parameter);
     833  nfReadTable(c, r);
     834  r->ch = r->m_nfCharP;
     835
     836}
     837
Note: See TracChangeset for help on using the changeset viewer.