source: git/libpolys/coeffs/ffields.cc @ e64221

spielwiese
Last change on this file since e64221 was e64221, checked in by Hans Schoenemann <hannes@…>, 8 years ago
fix: debug output
  • Property mode set to 100644
File size: 20.4 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/*
5* ABSTRACT: finite fields with a none-prime number of elements (via tables)
6*/
7#include <misc/auxiliary.h>
8#include <omalloc/omalloc.h>
9
10#include <misc/mylimits.h>
11#include <misc/sirandom.h>
12
13#include <reporter/reporter.h>
14
15#include "coeffs.h"
16#include "numbers.h"
17#include "longrat.h"
18
19#include <string.h>
20#include <math.h>
21#include <errno.h>
22
23BOOLEAN nfGreaterZero (number k, const coeffs r);
24number  nfMult        (number a, number b, const coeffs r);
25number  nfInit        (long i, const coeffs r);
26number  nfParameter   (int i, const coeffs r);
27long    nfInt         (number &n, const coeffs r);
28number  nfAdd         (number a, number b, const coeffs r);
29number  nfSub         (number a, number b, const coeffs r);
30void    nfPower       (number a, int i, number * result, const coeffs r);
31BOOLEAN nfIsZero      (number a, const coeffs r);
32BOOLEAN nfIsOne       (number a, const coeffs r);
33BOOLEAN nfIsMOne      (number a, const coeffs r);
34number  nfDiv         (number a, number b, const coeffs r);
35number  nfNeg         (number c, const coeffs r);
36number  nfInvers      (number c, const coeffs r);
37BOOLEAN nfGreater     (number a, number b, const coeffs r);
38BOOLEAN nfEqual       (number a, number b, const coeffs r);
39const char *  nfRead  (const char *s, number *a, const coeffs r);
40#ifdef LDEBUG
41BOOLEAN nfDBTest      (number a, const char *f, const int l, const coeffs r);
42#endif
43//void    nfSetChar     (const coeffs r);
44
45nMapFunc nfSetMap     (const coeffs src, const coeffs dst);
46char *  nfName        (number n, const coeffs r);
47void    nfReadTable   (const int c, const coeffs r);
48
49void    nfCoeffWrite(const coeffs r, BOOLEAN details);
50void    nfShowMipo(const coeffs r);
51
52
53
54/// Our Type!
55static const n_coeffType ID = n_GF;
56
57//unsigned short *nfPlus1Table=NULL; /* the table i=log(z^i) -> log(z^i+1) */
58
59const double sixteenlog2= 11.09035489;
60/* the q's from the table 'fftable' */
61const unsigned short fftable[]={
62    4,  8, 16, 32, 64, 128, 256, 512,1024,2048,4096,8192,16384, 32768,
63/*2^2 2^3 2^4 2^5 2^6  2^7  2^8  2^9 2^10 2^11 2^12 2^13  2^14  2^15*/
64    9, 27, 81,243,729,2187, 6561,19683,59049,
65/*3^2 3^3 3^4 3^5 3^6  3^7  3^8   3^9  3^10*/
66   25,125,625,3125,15625,
67/*5^2 5^3 5^4 5^5  5^6*/
68   49,343,2401,16807,
69/*7^2 7^3  7^4 7^5*/
70   121,1331, 14641,
71/*11^2 11^3  11^4*/
72  169, 2197, 28561,
73/*13^2 13^3  13^4*/
74  289, 4913,
75/*17^2 17^3*/
76  361, 6859,
77/*19^2 19^3*/
78  529, 12167,
79/*23^2 23^3*/
80  841, 24389,
81/*29^2 29^3*/
82  961, 29791,
83/*31^2 31^3*/
84  1369, 50653,
85/*37^2  37^3*/
86  1681, /*41^2*/
87  1849, /*43^2*/
88  2209, /*47^2*/
89  2809, /*53^2*/
90  3481, /*59^2*/
91  3721, /*61^2*/
92  4489, /*67^2*/
93  5041, /*71^2*/
94  5329, /*73^2*/
95  6241, /*79^2*/
96  6889, /*83^2*/
97  7921, /*89^2*/
98  9409, /*97^2*/
99  10201, /*101^2*/
100  10609, /*103^2*/
101  11449, /*107^2*/
102  11881, /*109^2*/
103  12769, /*113^2*/
104  16129, /*127^2*/
105  17161, /*131^2*/
106  18769, /*137^2*/
107  19321, /*139^2*/
108  22201, /*149^2*/
109  22801, /*151^2*/
110  24649, /*157^2*/
111  26569, /*163^2*/
112  27889, /*167^2*/
113  29929, /*173^2*/
114  32041, /*179^2*/
115  32761, /*181^2*/
116  36481, /*191^2*/
117  37249, /*193^2*/
118  38809, /*197^2*/
119  39601, /*199^2*/
120  49729, /*223^2*/
121  44521, /*211^2*/
122  51529, /*227^2*/
123  52441, /*229^2*/
124  54289, /*233^2*/
125  57121, /*239^2*/
126  58081, /*241^2*/
127  63001, /*251^2*/
128  0 };
129
130/*1
131* numbers in GF(p^n):
132* let nfCharQ=q=nfCharP^n=p^n
133* GF(q)\{0} will be generated by powers of an element Z
134* Z^i will be represented by the int i, 1 by the int 0, 0 by the int q=nfChar
135*/
136
137#ifdef LDEBUG
138/*2
139* debugging: is a a valid representation of a number ?
140*/
141BOOLEAN nfDBTest (number a, const char *f, const int l, const coeffs r)
142{
143  assume( r->m_nfPlus1Table != NULL );
144  if (((long)a<0L) || ((long)a>(long)r->m_nfCharQ))
145  {
146    Print("wrong %d in %s:%d\n",(int)((long)a),f,l);
147    return FALSE;
148  }
149  int i=0;
150  do
151  {
152    if (r->m_nfPlus1Table[i]>r->m_nfCharQ)
153    {
154      Print("wrong table %d=%d in %s:%d\n",i,r->m_nfPlus1Table[i],f,l);
155      return FALSE;
156    }
157    i++;
158  } while (i<r->m_nfCharQ);
159  return TRUE;
160}
161#define nfTest(N, R) nfDBTest(N,__FILE__,__LINE__, R)
162#endif
163
164/*2
165* k >= 0 ?
166*/
167BOOLEAN nfGreaterZero (number k, const coeffs r)
168{
169#ifdef LDEBUG
170  nfTest(k, r);
171#endif
172  return !nfIsZero(k, r) && !nfIsMOne(k, r);
173}
174
175/*2
176* a*b
177*/
178number nfMult (number a,number b, const coeffs r)
179{
180#ifdef LDEBUG
181  nfTest(a, r);
182  nfTest(b, r);
183#endif
184  if (((long)a == (long)r->m_nfCharQ) || ((long)b == (long)r->m_nfCharQ))
185    return (number)(long)r->m_nfCharQ;
186  /*else*/
187  int i=(int)((long)a+(long)b);
188  if (i>=r->m_nfCharQ1) i-=r->m_nfCharQ1;
189#ifdef LDEBUG
190  nfTest((number)(long)i, r);
191#endif
192  return (number)(long)i;
193}
194
195/*2
196* int -> number
197*/
198number nfInit (long i, const coeffs r)
199{
200  assume( r->m_nfPlus1Table != NULL );
201  // Hmm .. this is just to prevent initialization
202  // from nfInitChar to go into an infinite loop
203  if (i==0) return (number)(long)r->m_nfCharQ;
204  while (i <  0)    i += r->m_nfCharP;
205  while (i >= r->m_nfCharP) i -= r->m_nfCharP;
206  if (i==0) return (number)(long)r->m_nfCharQ;
207  unsigned short c=0;
208  while (i>1)
209  {
210    c=r->m_nfPlus1Table[c];
211    i--;
212  }
213#ifdef LDEBUG
214  nfTest((number)(long)c, r);
215#endif
216  return (number)(long)c;
217}
218
219/*
220* the generating element `z`
221*/
222number nfParameter (int i, const coeffs)
223{
224  assume(i==1);
225
226  if( i == 1 )
227    return (number)1;
228
229  return NULL;
230}
231
232/*2
233* the degree of the "alg. number"
234*/
235static int nfParDeg(number n, const coeffs r)
236{
237#ifdef LDEBUG
238  nfTest(n, r);
239#endif
240  if((long)r->m_nfCharQ == (long)n) return -1;
241  return (int)((long)n);
242}
243
244/*2
245* number -> int
246*/
247long nfInt (number &n, const coeffs )
248{
249  return (long)n;
250}
251
252/*2
253* a + b
254*/
255number nfAdd (number a, number b, const coeffs R)
256{
257/*4 z^a+z^b=z^b*(z^(a-b)+1), if a>=b; *
258*          =z^a*(z^(b-a)+1)  if a<b  */
259#ifdef LDEBUG
260  nfTest(a, R);
261  nfTest(b, R);
262#endif
263  if ((long)R->m_nfCharQ == (long)a) return b;
264  if ((long)R->m_nfCharQ == (long)b) return a;
265  long zb,zab,r;
266  if ((long)a >= (long)b)
267  {
268    zb = (long)b;
269    zab = (long)a-(long)b;
270  }
271  else
272  {
273    zb = (long)a;
274    zab = (long)b-(long)a;
275  }
276#ifdef LDEBUG
277  nfTest((number)zab, R);
278#endif
279  if (R->m_nfPlus1Table[zab]==R->m_nfCharQ) r=(long)R->m_nfCharQ; /*if z^(a-b)+1 =0*/
280  else
281  {
282    r= zb+(long)R->m_nfPlus1Table[zab];
283    if(r>=(long)R->m_nfCharQ1) r-=(long)R->m_nfCharQ1;
284  }
285#ifdef LDEBUG
286  nfTest((number)r, R);
287#endif
288  return (number)r;
289}
290
291/*2
292* a - b
293*/
294number nfSub (number a, number b, const coeffs r)
295{
296  number mb = nfNeg(b, r);
297  return nfAdd(a,mb,r);
298}
299
300/*2
301* a == 0 ?
302*/
303BOOLEAN nfIsZero (number  a, const coeffs r)
304{
305#ifdef LDEBUG
306  nfTest(a, r);
307#endif
308  return (long)r->m_nfCharQ == (long)a;
309}
310
311/*2
312* a == 1 ?
313*/
314BOOLEAN nfIsOne (number a, const coeffs r)
315{
316#ifdef LDEBUG
317  nfTest(a, r);
318#endif
319  return 0L == (long)a;
320}
321
322/*2
323* a == -1 ?
324*/
325BOOLEAN nfIsMOne (number a, const coeffs r)
326{
327#ifdef LDEBUG
328  nfTest(a, r);
329#endif
330  if (0L == (long)a) return FALSE; /* special handling of char 2*/
331  return (long)r->m_nfM1 == (long)a;
332}
333
334/*2
335* a / b
336*/
337number nfDiv (number a,number b, const coeffs r)
338{
339#ifdef LDEBUG
340  nfTest(b, r);
341#endif
342  if ((long)b==(long)r->m_nfCharQ)
343  {
344    WerrorS(nDivBy0);
345    return (number)((long)r->m_nfCharQ);
346  }
347#ifdef LDEBUG
348  nfTest(a, r);
349#endif
350  if ((long)a==(long)r->m_nfCharQ)
351    return (number)((long)r->m_nfCharQ);
352  /*else*/
353  long s = (long)a - (long)b;
354  if (s < 0L)
355    s += (long)r->m_nfCharQ1;
356#ifdef LDEBUG
357  nfTest((number)s, r);
358#endif
359  return (number)s;
360}
361
362/*2
363* 1 / c
364*/
365number  nfInvers (number c, const coeffs r)
366{
367#ifdef LDEBUG
368  nfTest(c, r);
369#endif
370  if ((long)c==(long)r->m_nfCharQ)
371  {
372    WerrorS(nDivBy0);
373    return (number)((long)r->m_nfCharQ);
374  }
375#ifdef LDEBUG
376  nfTest(((number)((long)r->m_nfCharQ1-(long)c)), r);
377#endif
378  return (number)((long)r->m_nfCharQ1-(long)c);
379}
380
381/*2
382* -c
383*/
384number nfNeg (number c, const coeffs r)
385{
386/*4 -z^c=z^c*(-1)=z^c*nfM1*/
387#ifdef LDEBUG
388  nfTest(c, r);
389#endif
390  if ((long)r->m_nfCharQ == (long)c) return c;
391  long i=(long)c+(long)r->m_nfM1;
392  if (i>=(long)r->m_nfCharQ1) i-=(long)r->m_nfCharQ1;
393#ifdef LDEBUG
394  nfTest((number)i, r);
395#endif
396  return (number)i;
397}
398
399/*2
400* a > b ?
401*/
402BOOLEAN nfGreater (number a,number b, const coeffs r)
403{
404#ifdef LDEBUG
405  nfTest(a, r);
406  nfTest(b, r);
407#endif
408  return (long)a != (long)b;
409}
410
411/*2
412* a == b ?
413*/
414BOOLEAN nfEqual (number a,number b, const coeffs r)
415{
416#ifdef LDEBUG
417  nfTest(a, r);
418  nfTest(b, r);
419#endif
420  return (long)a == (long)b;
421}
422
423/*2
424* write via StringAppend
425*/
426static void nfWriteLong (number a, const coeffs r)
427{
428#ifdef LDEBUG
429  nfTest(a, r);
430#endif
431  if ((long)a==(long)r->m_nfCharQ)  StringAppendS("0");
432  else if ((long)a==0L)   StringAppendS("1");
433  else if (nfIsMOne(a, r))   StringAppendS("-1");
434  else
435  {
436    StringAppendS(n_ParameterNames(r)[0]);
437    if ((long)a!=1L)
438    {
439      StringAppend("^%d",(int)((long)a)); // long output!
440    }
441  }
442}
443
444
445/*2
446* write (shortert output) via StringAppend
447*/
448static void nfWriteShort (number a, const coeffs r)
449{
450#ifdef LDEBUG
451  nfTest(a, r);
452#endif
453  if ((long)a==(long)r->m_nfCharQ)  StringAppendS("0");
454  else if ((long)a==0L)   StringAppendS("1");
455  else if (nfIsMOne(a, r))   StringAppendS("-1");
456  else
457  {
458    StringAppendS(n_ParameterNames(r)[0]);
459    if ((long)a!=1L)
460    {
461      StringAppend("%d",(int)((long)a));
462    }
463  }
464}
465
466/*2
467*
468*/
469char * nfName(number a, const coeffs r)
470{
471#ifdef LDEBUG
472  nfTest(a, r);
473#endif
474  char *s;
475  const char * const nf_Parameter=n_ParameterNames(r)[0];
476  if (((long)a==(long)r->m_nfCharQ) || ((long)a==0L)) return NULL;
477  else if ((long)a==1L)
478  {
479    return omStrDup(nf_Parameter);
480  }
481  else
482  {
483    s=(char *)omAlloc(4+strlen(nf_Parameter));
484    sprintf(s,"%s%d",nf_Parameter,(int)((long)a));
485  }
486  return s;
487}
488/*2
489* c ^ i with i>=0
490*/
491void nfPower (number a, int i, number * result, const coeffs r)
492{
493#ifdef LDEBUG
494  nfTest(a, r);
495#endif
496  if (i==0)
497  {
498    *result = (number)0L;
499  }
500  else if (i==1)
501  {
502    *result = a;
503  }
504  else
505  {
506    long rl;
507    if ((long)a == (long)r->m_nfCharQ) rl=(long)r->m_nfCharQ;
508    else rl=((long)a*(long)i) % (long)r->m_nfCharQ1;
509    *result = (number)rl;
510  }
511#ifdef LDEBUG
512  nfTest(*result, r);
513#endif
514}
515
516/*4
517* read an integer (with reduction mod p)
518*/
519static const char* nfEati(const char *s, int *i, const coeffs r)
520{
521  if (*s >= '0' && *s <= '9')
522  {
523    *i = 0;
524    do
525    {
526      *i *= 10;
527      *i += *s++ - '0';
528      if (*i > (MAX_INT_VAL / 10)) *i = *i % r->m_nfCharP;
529    }
530    while (*s >= '0' && *s <= '9');
531    if (*i >= r->m_nfCharP) *i = *i % r->m_nfCharP;
532  }
533  else *i = 1;
534  return s;
535}
536
537/*2
538* read a number
539*/
540const char * nfRead (const char *s, number *a, const coeffs r)
541{
542  int i;
543  number z;
544  number n;
545
546  s = nfEati(s, &i, r);
547  z=nfInit(i, r);
548  *a=z;
549  if (*s == '/')
550  {
551    s++;
552    s = nfEati(s, &i, r);
553    n=nfInit(i, r);
554    *a = nfDiv(z,n,r);
555  }
556  const char * const nf_Parameter = n_ParameterNames(r)[0];
557  const int N = strlen(nf_Parameter);
558  if (strncmp(s,nf_Parameter, N)==0)
559  {
560    s += N;
561    if ((*s >= '0') && (*s <= '9'))
562    {
563      s=eati(s,&i);
564      while (i>=r->m_nfCharQ1) i-=r->m_nfCharQ1;
565    }
566    else
567      i=1;
568    z=(number)(long)i;
569    *a=nfMult(*a,z,r);
570  }
571#ifdef LDEBUG
572  nfTest(*a, r);
573#endif
574  return s;
575}
576
577int gf_tab_numdigits62 ( int q );
578int convertback62 ( char * p, int n );
579
580int nfMinPoly[16];
581
582void nfShowMipo(const coeffs r)
583{
584  int i=nfMinPoly[0];
585  int j=0;
586  loop
587  {
588    j++;
589    if (nfMinPoly[j]!=0)
590      StringAppend("%d*%s^%d",nfMinPoly[j],n_ParameterNames(r)[0],i);
591    i--;
592    if(i<0) break;
593    if (nfMinPoly[j]!=0)
594      StringAppendS("+");
595  }
596}
597
598static void nfReadMipo(char *s)
599{
600  const char *l=strchr(s,';')+1;
601  char *n;
602  int i=strtol(l,&n,10);
603  l=n;
604  int j=1;
605  nfMinPoly[0]=i;
606  while(i>=0)
607  {
608    nfMinPoly[j]=strtol(l,&n,10);
609    if (l==n) break;
610    l=n;
611    j++;
612    i--;
613  }
614  if (i>=0)
615  {
616    WerrorS("error in reading minpoly from gftables");
617  }
618}
619
620/*2
621* init global variables from files 'gftables/%d'
622*/
623void nfReadTable(const int c, const coeffs r)
624{
625  //Print("GF(%d)\n",c);
626  if ((c==r->m_nfCharQ)||(c==-r->m_nfCharQ))
627    /*this field is already set*/  return;
628  int i=0;
629
630  while ((fftable[i]!=c) && (fftable[i]!=0))
631    i++;
632
633  if (fftable[i]==0)
634  {
635    // illegal GF-table size: c
636    return;
637  }
638
639  if (r->m_nfCharQ > 1)
640  {
641    omFreeSize( (ADDRESS)r->m_nfPlus1Table,r->m_nfCharQ*sizeof(unsigned short) );
642    r->m_nfPlus1Table=NULL;
643  }
644  if ((c>1) || (c<0))
645  {
646    if (c>1) r->m_nfCharQ = c;
647    else     r->m_nfCharQ = -c;
648    char buf[100];
649    sprintf(buf,"gftables/%d",r->m_nfCharQ);
650    FILE * fp = feFopen(buf,"r",NULL,TRUE);
651    if (fp==NULL)
652    {
653      return;
654    }
655    if(!fgets( buf, sizeof(buf), fp)) return;
656    if(strcmp(buf,"@@ factory GF(q) table @@\n")!=0)
657    {
658      goto err;
659    }
660    if(!fgets( buf, sizeof(buf), fp))
661    {
662      goto err;
663    }
664    int q;
665    int res = -1;
666    do
667    {
668      res = sscanf(buf,"%d %d",&r->m_nfCharP,&q);
669    }
670    while((res < 0) and (errno == EINTR));
671
672    nfReadMipo(buf);
673    r->m_nfCharQ1=r->m_nfCharQ-1;
674    //Print("nfCharQ=%d,nfCharQ1=%d,mipo=>>%s<<\n",nfCharQ,nfCharQ1,buf);
675    r->m_nfPlus1Table= (unsigned short *)omAlloc( (r->m_nfCharQ)*sizeof(unsigned short) );
676    int digs = gf_tab_numdigits62( r->m_nfCharQ );
677    char * bufptr;
678    int i = 1;
679    int k;
680    while ( i < r->m_nfCharQ )
681    {
682      (void)fgets( buf, sizeof(buf), fp);
683      //( strlen( buffer ) == (size_t)digs * 30, "illegal table" );
684      bufptr = buf;
685      k = 0;
686      while ( (i < r->m_nfCharQ) && (k < 30) )
687      {
688        r->m_nfPlus1Table[i] = convertback62( bufptr, digs );
689        if(r->m_nfPlus1Table[i]>r->m_nfCharQ)
690        {
691          Print("wrong entry %d: %d(%c%c%c)\n",i,r->m_nfPlus1Table[i],bufptr[0],bufptr[1],bufptr[2]);
692        }
693        bufptr += digs;
694        if (r->m_nfPlus1Table[i]==r->m_nfCharQ)
695        {
696          if(i==r->m_nfCharQ1)
697          {
698            r->m_nfM1=0;
699          }
700          else
701          {
702            r->m_nfM1=i;
703          }
704        }
705        i++; k++;
706      }
707    }
708    r->m_nfPlus1Table[0]=r->m_nfPlus1Table[r->m_nfCharQ1];
709  }
710  else
711    r->m_nfCharQ=0;
712#ifdef LDEBUG
713  nfTest((number)0, r);
714#endif
715  return;
716err:
717  Werror("illegal GF-table %d",r->m_nfCharQ);
718}
719
720/*2
721* map Z/p -> GF(p,n)
722*/
723number nfMapP(number c, const coeffs, const coeffs dst)
724{
725  return nfInit((int)((long)c), dst);
726}
727
728/*2
729* map GF(p,n1) -> GF(p,n2), n1 < n2, n1 | n2
730*/
731int nfMapGG_factor;
732number nfMapGG(number c, const coeffs src, const coeffs)
733{
734  int i=(long)c;
735  i*= nfMapGG_factor;
736  while (i >src->m_nfCharQ1) i-=src->m_nfCharQ1;
737  return (number)((long)i);
738}
739/*2
740* map GF(p,n1) -> GF(p,n2), n1 > n2, n2 | n1
741*/
742number nfMapGGrev(number c, const coeffs src, const coeffs)
743{
744  int ex=(int)((long)c);
745  if ((ex % nfMapGG_factor)==0)
746    return (number)(((long)ex) / ((long)nfMapGG_factor));
747  else
748    return (number)(long)src->m_nfCharQ; /* 0 */
749}
750
751/*2
752* set map function nMap ... -> GF(p,n)
753*/
754nMapFunc nfSetMap(const coeffs src, const coeffs dst)
755{
756  if (nCoeff_is_GF(src,src->m_nfCharQ))
757  {
758    return ndCopyMap;   /* GF(p,n) -> GF(p,n) */
759  }
760  if (nCoeff_is_GF(src))
761  {
762    const coeffs r = dst;
763    int q=src->ch;
764    if ((src->m_nfCharQ % q)==0) /* GF(p,n1) -> GF(p,n2), n2 > n1 */
765    {
766      // check if n2 is a multiple of n1
767      int n1=1;
768      int qq=r->m_nfCharP;
769      while(qq!=q) { qq *= r->m_nfCharP; n1++; }
770      int n2=1;
771      qq=r->m_nfCharP;
772      while(qq!=src->m_nfCharQ) { qq *= r->m_nfCharP; n2++; }
773      //Print("map %d^%d -> %d^%d\n",r->m_nfCharP,n1,r->m_nfCharP,n2);
774      if ((n2 % n1)==0)
775      {
776        int save_ch=r->m_nfCharQ;
777        nfReadTable(src->m_nfCharQ, r);
778        int nn=r->m_nfPlus1Table[0];
779        nfReadTable(save_ch, r);
780        nfMapGG_factor= r->m_nfPlus1Table[0] / nn;
781        //Print("nfMapGG_factor=%d (%d / %d)\n",nfMapGG_factor, r->m_nfPlus1Table[0], nn);
782        return nfMapGG;
783      }
784      else if ((n1 % n2)==0)
785      {
786        nfMapGG_factor= (n1/n2);
787        return nfMapGGrev;
788      }
789      else
790        return NULL;
791    }
792  }
793  if ((src->rep==n_rep_int) && nCoeff_is_Zp(src,dst->m_nfCharP))
794  {
795    return nfMapP;    /* Z/p -> GF(p,n) */
796  }
797
798  if (src->rep==n_rep_gap_rat) /*Q, Z */
799  {
800    return nlModP; // FIXME? TODO? // extern number nlModP(number q, const coeffs Q, const coeffs Zp); // Map q \in QQ \to Zp // FIXME!
801  }
802
803  return NULL;     /* default */
804}
805
806static BOOLEAN nfCoeffIsEqual(const coeffs, n_coeffType, void*);
807
808static void nfKillChar(coeffs r)
809{
810  char** p = (char**)n_ParameterNames(r);
811
812  const int P = n_NumberOfParameters(r);
813
814  for( int i = 1; i <= P; i++ )
815    if (p[i-1] != NULL)
816      omFree( (ADDRESS)p[i-1] );
817
818  omFreeSize((ADDRESS)p, P * sizeof(char*));
819}
820
821static char* nfCoeffString(const coeffs r)
822{
823  const char *p=n_ParameterNames(r)[0];
824  char *s=(char*)omAlloc(11+1+strlen(p));
825  sprintf(s,"%d,%s",r->m_nfCharQ,p);
826  return s;
827}
828
829static number nfRandom(siRandProc p,number ,number, const coeffs cf)
830{
831  return (number)(long)(p() %(cf->m_nfCharQ+1));
832}
833
834BOOLEAN nfInitChar(coeffs r,  void * parameter)
835{
836  r->is_field=TRUE;
837  r->is_domain=TRUE;
838  r->rep=n_rep_gf;
839  //r->cfInitChar=npInitChar;
840  r->cfKillChar=nfKillChar;
841  r->nCoeffIsEqual=nfCoeffIsEqual;
842  r->cfCoeffString=nfCoeffString;
843
844  r->cfMult  = nfMult;
845  r->cfSub   = nfSub;
846  r->cfAdd   = nfAdd;
847  r->cfDiv   = nfDiv;
848  //r->cfIntMod= ndIntMod;
849  r->cfExactDiv= nfDiv;
850  r->cfInit = nfInit;
851  //r->cfSize  = ndSize;
852  r->cfInt  = nfInt;
853  #ifdef HAVE_RINGS
854  //r->cfDivComp = NULL; // only for ring stuff
855  //r->cfIsUnit = NULL; // only for ring stuff
856  //r->cfGetUnit = NULL; // only for ring stuff
857  //r->cfExtGcd = NULL; // only for ring stuff
858  // r->cfDivBy = NULL; // only for ring stuff
859  #endif
860  r->cfInpNeg   = nfNeg;
861  r->cfInvers= nfInvers;
862  //r->cfCopy  = ndCopy;
863  //r->cfRePart = ndCopy;
864  //r->cfImPart = ndReturn0;
865
866  r->cfWriteLong = nfWriteLong;
867  r->cfRead = nfRead;
868  //r->cfNormalize=ndNormalize;
869  r->cfGreater = nfGreater;
870  r->cfEqual = nfEqual;
871  r->cfIsZero = nfIsZero;
872  r->cfIsOne = nfIsOne;
873  r->cfIsMOne = nfIsMOne;
874  r->cfGreaterZero = nfGreaterZero;
875  r->cfPower = nfPower;
876  //r->cfGcd  = ndGcd;
877  //r->cfLcm  = ndGcd;
878  //r->cfDelete= ndDelete;
879  r->cfSetMap = nfSetMap;
880  //r->cfName = ndName;
881  // debug stuff
882  r->cfCoeffWrite=nfCoeffWrite;
883
884  r->cfParDeg = nfParDeg;
885
886  r->cfRandom = nfRandom;
887
888#ifdef LDEBUG
889  r->cfDBTest=nfDBTest;
890#endif
891
892  // the variables:
893  r->nNULL = (number)0;
894  assume( getCoeffType(r) == n_GF );
895
896  GFInfo* p = (GFInfo *)(parameter);
897  assume (p->GFChar > 0);
898  assume (p->GFDegree > 0);
899
900  const char * name = p->GFPar_name;
901
902  r->m_nfCharQ = 0;
903  r->m_nfCharP = p->GFChar;
904  r->m_nfCharQ1 = 0;
905
906  r->iNumberOfParameters = 1;
907  r->cfParameter = nfParameter;
908
909  char ** pParameterNames = (char **) omAlloc0(sizeof(char *));
910  pParameterNames[0] = omStrDup(name); //TODO use omAlloc for allocating memory and use strcpy?
911
912  assume( pParameterNames != NULL );
913  assume( pParameterNames[0] != NULL );
914
915  r->pParameterNames = (const char**)pParameterNames;
916  // NOTE: r->m_nfParameter was replaced by n_ParameterNames(r)[0]
917
918  // TODO: nfKillChar MUST destroy r->pParameterNames[0] (0-term. string) && r->pParameterNames (array of size 1)
919
920  r->m_nfPlus1Table= NULL;
921
922  if (strlen(name) > 1)
923    r->cfWriteShort = nfWriteLong;
924  else
925    r->cfWriteShort = nfWriteShort;
926
927  r->has_simple_Alloc=TRUE;
928  r->has_simple_Inverse=TRUE;
929
930  if(p->GFChar > (2<<15))
931  {
932#ifndef SING_NDEBUG
933    Warn("illegal characteristic");
934#endif
935    return TRUE;
936  }
937
938  const double check= log ((double) (p->GFChar));
939
940  if( (p->GFDegree * check) > sixteenlog2 )
941  {
942#ifndef SING_NDEBUG
943    Warn("Sorry: illegal size: %u ^ %u", p->GFChar, p->GFDegree );
944#endif
945    return TRUE;
946  }
947
948  int c = pow (p->GFChar, p->GFDegree);
949
950  nfReadTable(c, r);
951
952  if( r->m_nfPlus1Table == NULL )
953  {
954    return TRUE;
955  }
956
957
958  assume (r -> m_nfCharQ > 0);
959
960  r->ch = r->m_nfCharP;
961  assume( r->m_nfPlus1Table != NULL );
962
963  return FALSE;
964
965}
966
967void    nfCoeffWrite  (const coeffs r, BOOLEAN details)
968{
969  // m_nfCharQ = p^k where p is the characteristic (r->CharP) and k is GFDegree
970  Print("//   # ground field : %d\n",r->m_nfCharQ);
971  Print("//   primitive element : %s\n", n_ParameterNames(r)[0]);
972  if ( details )
973  {
974    StringSetS("//   minpoly        : ");
975    nfShowMipo(r);
976    StringAppendS("\n");
977    char *s=StringEndS(); PrintS(s); omFree(s);
978  }
979  else PrintS("//   minpoly        : ...\n");
980}
981
982static BOOLEAN nfCoeffIsEqual (const coeffs r, n_coeffType n, void * parameter)
983{
984  if (n==n_GF) {
985    GFInfo* p = (GFInfo *)(parameter);
986    int c = pow (p->GFChar, p->GFDegree);
987    if ((c == r->m_nfCharQ) && (strcmp(n_ParameterNames(r)[0], p->GFPar_name) == 0))
988      return TRUE;
989  }
990  return FALSE;
991}
Note: See TracBrowser for help on using the repository browser.