algext.cc
Go to the documentation of this file.
1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 /**
5  * ABSTRACT: numbers in an algebraic extension field K[a] / < f(a) >
6  * Assuming that we have a coeffs object cf, then these numbers
7  * are polynomials in the polynomial ring K[a] represented by
8  * cf->extRing.
9  * IMPORTANT ASSUMPTIONS:
10  * 1.) So far we assume that cf->extRing is a valid polynomial
11  * ring in exactly one variable, i.e., K[a], where K is allowed
12  * to be any field (representable in SINGULAR and which may
13  * itself be some extension field, thus allowing for extension
14  * towers).
15  * 2.) Moreover, this implementation assumes that
16  * cf->extRing->qideal is not NULL but an ideal with at
17  * least one non-zero generator which may be accessed by
18  * cf->extRing->qideal->m[0] and which represents the minimal
19  * polynomial f(a) of the extension variable 'a' in K[a].
20  * 3.) As soon as an std method for polynomial rings becomes
21  * availabe, all reduction steps modulo f(a) should be replaced
22  * by a call to std. Moreover, in this situation one can finally
23  * move from K[a] / < f(a) > to
24  * K[a_1, ..., a_s] / I, with I some zero-dimensional ideal
25  * in K[a_1, ..., a_s] given by a lex
26  * Gröbner basis.
27  * The code in algext.h and algext.cc is then capable of
28  * computing in K[a_1, ..., a_s] / I.
29  **/
30 
31 
32 
33 
34 #include <misc/auxiliary.h>
35 
36 #include <omalloc/omalloc.h>
37 
38 #include <reporter/reporter.h>
39 
40 #include <coeffs/coeffs.h>
41 #include <coeffs/numbers.h>
42 
43 #include <coeffs/longrat.h>
44 
45 #include <polys/monomials/ring.h>
47 #include <polys/simpleideals.h>
48 
49 #include <polys/PolyEnumerator.h>
50 
51 #include <factory/factory.h>
52 #include <polys/clapconv.h>
53 #include <polys/clapsing.h>
54 #include <polys/prCopy.h>
55 
57 #define TRANSEXT_PRIVATES 1
59 
60 #ifdef LDEBUG
61 #define naTest(a) naDBTest(a,__FILE__,__LINE__,cf)
62 BOOLEAN naDBTest(number a, const char *f, const int l, const coeffs r);
63 #else
64 #define naTest(a) do {} while (0)
65 #endif
66 
67 /// Our own type!
68 static const n_coeffType ID = n_algExt;
69 
70 /* polynomial ring in which our numbers live */
71 #define naRing cf->extRing
72 
73 /* coeffs object in which the coefficients of our numbers live;
74  * methods attached to naCoeffs may be used to compute with the
75  * coefficients of our numbers, e.g., use naCoeffs->nAdd to add
76  * coefficients of our numbers */
77 #define naCoeffs cf->extRing->cf
78 
79 /* minimal polynomial */
80 #define naMinpoly naRing->qideal->m[0]
81 
82 /// forward declarations
83 BOOLEAN naGreaterZero(number a, const coeffs cf);
84 BOOLEAN naGreater(number a, number b, const coeffs cf);
85 BOOLEAN naEqual(number a, number b, const coeffs cf);
86 BOOLEAN naIsOne(number a, const coeffs cf);
87 BOOLEAN naIsMOne(number a, const coeffs cf);
88 BOOLEAN naIsZero(number a, const coeffs cf);
89 number naInit(long i, const coeffs cf);
90 long naInt(number &a, const coeffs cf);
91 number naNeg(number a, const coeffs cf);
92 number naInvers(number a, const coeffs cf);
93 number naAdd(number a, number b, const coeffs cf);
94 number naSub(number a, number b, const coeffs cf);
95 number naMult(number a, number b, const coeffs cf);
96 number naDiv(number a, number b, const coeffs cf);
97 void naPower(number a, int exp, number *b, const coeffs cf);
98 number naCopy(number a, const coeffs cf);
99 void naWriteLong(number a, const coeffs cf);
100 void naWriteShort(number a, const coeffs cf);
101 number naGetDenom(number &a, const coeffs cf);
102 number naGetNumerator(number &a, const coeffs cf);
103 number naGcd(number a, number b, const coeffs cf);
104 int naSize(number a, const coeffs cf);
105 void naDelete(number *a, const coeffs cf);
106 void naCoeffWrite(const coeffs cf, BOOLEAN details);
107 //number naIntDiv(number a, number b, const coeffs cf);
108 const char * naRead(const char *s, number *a, const coeffs cf);
109 
110 static BOOLEAN naCoeffIsEqual(const coeffs cf, n_coeffType n, void * param);
111 
112 
113 /// returns NULL if p == NULL, otherwise makes p monic by dividing
114 /// by its leading coefficient (only done if this is not already 1);
115 /// this assumes that we are over a ground field so that division
116 /// is well-defined;
117 /// modifies p
118 // void p_Monic(poly p, const ring r);
119 
120 /// assumes that p and q are univariate polynomials in r,
121 /// mentioning the same variable;
122 /// assumes a global monomial ordering in r;
123 /// assumes that not both p and q are NULL;
124 /// returns the gcd of p and q;
125 /// leaves p and q unmodified
126 // poly p_Gcd(const poly p, const poly q, const ring r);
127 
128 /* returns NULL if p == NULL, otherwise makes p monic by dividing
129  by its leading coefficient (only done if this is not already 1);
130  this assumes that we are over a ground field so that division
131  is well-defined;
132  modifies p */
133 static inline void p_Monic(poly p, const ring r)
134 {
135  if (p == NULL) return;
136  number n = n_Init(1, r->cf);
137  if (p->next==NULL) { p_SetCoeff(p,n,r); return; }
138  poly pp = p;
139  number lc = p_GetCoeff(p, r);
140  if (n_IsOne(lc, r->cf)) return;
141  number lcInverse = n_Invers(lc, r->cf);
142  p_SetCoeff(p, n, r); // destroys old leading coefficient!
143  pIter(p);
144  while (p != NULL)
145  {
146  number n = n_Mult(p_GetCoeff(p, r), lcInverse, r->cf);
147  n_Normalize(n,r->cf);
148  p_SetCoeff(p, n, r); // destroys old leading coefficient!
149  pIter(p);
150  }
151  n_Delete(&lcInverse, r->cf);
152  p = pp;
153 }
154 
155 /// see p_Gcd;
156 /// additional assumption: deg(p) >= deg(q);
157 /// must destroy p and q (unless one of them is returned)
158 static inline poly p_GcdHelper(poly &p, poly &q, const ring r)
159 {
160  while (q != NULL)
161  {
162  p_PolyDiv(p, q, FALSE, r);
163  // swap p and q:
164  poly& t = q;
165  q = p;
166  p = t;
167 
168  }
169  return p;
170 }
171 
172 /* assumes that p and q are univariate polynomials in r,
173  mentioning the same variable;
174  assumes a global monomial ordering in r;
175  assumes that not both p and q are NULL;
176  returns the gcd of p and q;
177  leaves p and q unmodified */
178 static inline poly p_Gcd(const poly p, const poly q, const ring r)
179 {
180  assume((p != NULL) || (q != NULL));
181 
182  poly a = p; poly b = q;
183  if (p_Deg(a, r) < p_Deg(b, r)) { a = q; b = p; }
184  a = p_Copy(a, r); b = p_Copy(b, r);
185 
186  /* We have to make p monic before we return it, so that if the
187  gcd is a unit in the ground field, we will actually return 1. */
188  a = p_GcdHelper(a, b, r);
189  p_Monic(a, r);
190  return a;
191 }
192 
193 /* see p_ExtGcd;
194  additional assumption: deg(p) >= deg(q);
195  must destroy p and q (unless one of them is returned) */
196 static inline poly p_ExtGcdHelper(poly &p, poly &pFactor, poly &q, poly &qFactor,
197  ring r)
198 {
199  if (q == NULL)
200  {
201  qFactor = NULL;
202  pFactor = p_ISet(1, r);
203  p_SetCoeff(pFactor, n_Invers(p_GetCoeff(p, r), r->cf), r);
204  p_Monic(p, r);
205  return p;
206  }
207  else
208  {
209  poly pDivQ = p_PolyDiv(p, q, TRUE, r);
210  poly ppFactor = NULL; poly qqFactor = NULL;
211  poly theGcd = p_ExtGcdHelper(q, qqFactor, p, ppFactor, r);
212  pFactor = ppFactor;
213  qFactor = p_Add_q(qqFactor,
214  p_Neg(p_Mult_q(pDivQ, p_Copy(ppFactor, r), r), r),
215  r);
216  return theGcd;
217  }
218 }
219 
220 
221 /* assumes that p and q are univariate polynomials in r,
222  mentioning the same variable;
223  assumes a global monomial ordering in r;
224  assumes that not both p and q are NULL;
225  returns the gcd of p and q;
226  moreover, afterwards pFactor and qFactor contain appropriate
227  factors such that gcd(p, q) = p * pFactor + q * qFactor;
228  leaves p and q unmodified */
229 poly p_ExtGcd(poly p, poly &pFactor, poly q, poly &qFactor, ring r)
230 {
231  assume((p != NULL) || (q != NULL));
232  poly a = p; poly b = q; BOOLEAN aCorrespondsToP = TRUE;
233  if (p_Deg(a, r) < p_Deg(b, r))
234  { a = q; b = p; aCorrespondsToP = FALSE; }
235  a = p_Copy(a, r); b = p_Copy(b, r);
236  poly aFactor = NULL; poly bFactor = NULL;
237  poly theGcd = p_ExtGcdHelper(a, aFactor, b, bFactor, r);
238  if (aCorrespondsToP) { pFactor = aFactor; qFactor = bFactor; }
239  else { pFactor = bFactor; qFactor = aFactor; }
240  return theGcd;
241 }
242 
243 
244 
245 #ifdef LDEBUG
246 BOOLEAN naDBTest(number a, const char *f, const int l, const coeffs cf)
247 {
248  if (a == NULL) return TRUE;
249  p_Test((poly)a, naRing);
250  if (getCoeffType(cf)==n_algExt)
251  {
252  if((((poly)a)!=naMinpoly)
254  && (p_Totaldegree((poly)a, naRing)> 1)) // allow to output par(1)
255  {
256  dReportError("deg >= deg(minpoly) in %s:%d\n",f,l);
257  return FALSE;
258  }
259  }
260  return TRUE;
261 }
262 #endif
263 
264 void heuristicReduce(poly &p, poly reducer, const coeffs cf);
265 void definiteReduce(poly &p, poly reducer, const coeffs cf);
266 
267 /* returns the bottom field in this field extension tower; if the tower
268  is flat, i.e., if there is no extension, then r itself is returned;
269  as a side-effect, the counter 'height' is filled with the height of
270  the extension tower (in case the tower is flat, 'height' is zero) */
271 static coeffs nCoeff_bottom(const coeffs r, int &height)
272 {
273  assume(r != NULL);
274  coeffs cf = r;
275  height = 0;
276  while (nCoeff_is_Extension(cf))
277  {
278  assume(cf->extRing != NULL); assume(cf->extRing->cf != NULL);
279  cf = cf->extRing->cf;
280  height++;
281  }
282  return cf;
283 }
284 
285 BOOLEAN naIsZero(number a, const coeffs cf)
286 {
287  naTest(a);
288  return (a == NULL);
289 }
290 
291 void naDelete(number * a, const coeffs cf)
292 {
293  if (*a == NULL) return;
294  if (((poly)*a)==naMinpoly) { *a=NULL;return;}
295  poly aAsPoly = (poly)(*a);
296  p_Delete(&aAsPoly, naRing);
297  *a = NULL;
298 }
299 
300 BOOLEAN naEqual(number a, number b, const coeffs cf)
301 {
302  naTest(a); naTest(b);
303  /// simple tests
304  if (a == NULL) return (b == NULL);
305  if (b == NULL) return (a == NULL);
306  return p_EqualPolys((poly)a,(poly)b,naRing);
307 }
308 
309 number naCopy(number a, const coeffs cf)
310 {
311  naTest(a);
312  if (a == NULL) return NULL;
313  if (((poly)a)==naMinpoly) return a;
314  return (number)p_Copy((poly)a, naRing);
315 }
316 
317 number naGetNumerator(number &a, const coeffs cf)
318 {
319  return naCopy(a, cf);
320 }
321 
322 number naGetDenom(number &a, const coeffs cf)
323 {
324  naTest(a);
325  return naInit(1, cf);
326 }
327 
328 BOOLEAN naIsOne(number a, const coeffs cf)
329 {
330  naTest(a);
331  poly aAsPoly = (poly)a;
332  if ((a==NULL) || (!p_IsConstant(aAsPoly, naRing))) return FALSE;
333  return n_IsOne(p_GetCoeff(aAsPoly, naRing), naCoeffs);
334 }
335 
336 BOOLEAN naIsMOne(number a, const coeffs cf)
337 {
338  naTest(a);
339  poly aAsPoly = (poly)a;
340  if ((a==NULL) || (!p_IsConstant(aAsPoly, naRing))) return FALSE;
341  return n_IsMOne(p_GetCoeff(aAsPoly, naRing), naCoeffs);
342 }
343 
344 /// this is in-place, modifies a
345 number naNeg(number a, const coeffs cf)
346 {
347  naTest(a);
348  if (a != NULL) a = (number)p_Neg((poly)a, naRing);
349  return a;
350 }
351 
352 number naInit(long i, const coeffs cf)
353 {
354  if (i == 0) return NULL;
355  else return (number)p_ISet(i, naRing);
356 }
357 
358 long naInt(number &a, const coeffs cf)
359 {
360  naTest(a);
361  poly aAsPoly = (poly)a;
362  if(aAsPoly == NULL)
363  return 0;
364  if (!p_IsConstant(aAsPoly, naRing))
365  return 0;
366  assume( aAsPoly != NULL );
367  return n_Int(p_GetCoeff(aAsPoly, naRing), naCoeffs);
368 }
369 
370 /* TRUE iff (a != 0 and (b == 0 or deg(a) > deg(b) or (deg(a)==deg(b) && lc(a)>lc(b))) */
371 BOOLEAN naGreater(number a, number b, const coeffs cf)
372 {
373  naTest(a); naTest(b);
374  if (naIsZero(a, cf))
375  {
376  if (naIsZero(b, cf)) return FALSE;
377  return !n_GreaterZero(pGetCoeff((poly)b),cf);
378  }
379  if (naIsZero(b, cf))
380  {
381  return n_GreaterZero(pGetCoeff((poly)a),cf);
382  }
383  int aDeg = p_Totaldegree((poly)a, naRing);
384  int bDeg = p_Totaldegree((poly)b, naRing);
385  if (aDeg>bDeg) return TRUE;
386  if (aDeg<bDeg) return FALSE;
387  return n_Greater(pGetCoeff((poly)a),pGetCoeff((poly)b),naCoeffs);
388 }
389 
390 /* TRUE iff a != 0 and (LC(a) > 0 or deg(a) > 0) */
391 BOOLEAN naGreaterZero(number a, const coeffs cf)
392 {
393  naTest(a);
394  if (a == NULL) return FALSE;
395  if (n_GreaterZero(p_GetCoeff((poly)a, naRing), naCoeffs)) return TRUE;
396  if (p_Totaldegree((poly)a, naRing) > 0) return TRUE;
397  return FALSE;
398 }
399 
400 void naCoeffWrite(const coeffs cf, BOOLEAN details)
401 {
402  assume( cf != NULL );
403 
404  const ring A = cf->extRing;
405 
406  assume( A != NULL );
407  assume( A->cf != NULL );
408 
409  n_CoeffWrite(A->cf, details);
410 
411 // rWrite(A);
412 
413  const int P = rVar(A);
414  assume( P > 0 );
415 
416  Print("// %d parameter : ", P);
417 
418  for (int nop=0; nop < P; nop ++)
419  Print("%s ", rRingVar(nop, A));
420 
421  PrintLn();
422 
423  const ideal I = A->qideal;
424 
425  assume( I != NULL );
426  assume( IDELEMS(I) == 1 );
427 
428 
429  if ( details )
430  {
431  PrintS("// minpoly : (");
432  p_Write0( I->m[0], A);
433  PrintS(")");
434  }
435  else
436  PrintS("// minpoly : ...");
437 
438  PrintLn();
439 
440 /*
441  char *x = rRingVar(0, A);
442 
443  Print("// Coefficients live in the extension field K[%s]/<f(%s)>\n", x, x);
444  Print("// with the minimal polynomial f(%s) = %s\n", x,
445  p_String(A->qideal->m[0], A));
446  PrintS("// and K: ");
447 */
448 }
449 
450 number naAdd(number a, number b, const coeffs cf)
451 {
452  naTest(a); naTest(b);
453  if (a == NULL) return naCopy(b, cf);
454  if (b == NULL) return naCopy(a, cf);
455  poly aPlusB = p_Add_q(p_Copy((poly)a, naRing),
456  p_Copy((poly)b, naRing), naRing);
457  //definiteReduce(aPlusB, naMinpoly, cf);
458  return (number)aPlusB;
459 }
460 
461 number naSub(number a, number b, const coeffs cf)
462 {
463  naTest(a); naTest(b);
464  if (b == NULL) return naCopy(a, cf);
465  poly minusB = p_Neg(p_Copy((poly)b, naRing), naRing);
466  if (a == NULL) return (number)minusB;
467  poly aMinusB = p_Add_q(p_Copy((poly)a, naRing), minusB, naRing);
468  //definiteReduce(aMinusB, naMinpoly, cf);
469  return (number)aMinusB;
470 }
471 
472 number naMult(number a, number b, const coeffs cf)
473 {
474  naTest(a); naTest(b);
475  if ((a == NULL)||(b == NULL)) return NULL;
476  poly aTimesB = p_Mult_q(p_Copy((poly)a, naRing),
477  p_Copy((poly)b, naRing), naRing);
478  definiteReduce(aTimesB, naMinpoly, cf);
479  p_Normalize(aTimesB,naRing);
480  return (number)aTimesB;
481 }
482 
483 number naDiv(number a, number b, const coeffs cf)
484 {
485  naTest(a); naTest(b);
486  if (b == NULL) WerrorS(nDivBy0);
487  if (a == NULL) return NULL;
488  poly bInverse = (poly)naInvers(b, cf);
489  if(bInverse != NULL) // b is non-zero divisor!
490  {
491  poly aDivB = p_Mult_q(p_Copy((poly)a, naRing), bInverse, naRing);
492  definiteReduce(aDivB, naMinpoly, cf);
493  p_Normalize(aDivB,naRing);
494  return (number)aDivB;
495  }
496  return NULL;
497 }
498 
499 /* 0^0 = 0;
500  for |exp| <= 7 compute power by a simple multiplication loop;
501  for |exp| >= 8 compute power along binary presentation of |exp|, e.g.
502  p^13 = p^1 * p^4 * p^8, where we utilise that
503  p^(2^(k+1)) = p^(2^k) * p^(2^k);
504  intermediate reduction modulo the minimal polynomial is controlled by
505  the in-place method heuristicReduce(poly, poly, coeffs); see there.
506 */
507 void naPower(number a, int exp, number *b, const coeffs cf)
508 {
509  naTest(a);
510 
511  /* special cases first */
512  if (a == NULL)
513  {
514  if (exp >= 0) *b = NULL;
515  else WerrorS(nDivBy0);
516  return;
517  }
518  else if (exp == 0) { *b = naInit(1, cf); return; }
519  else if (exp == 1) { *b = naCopy(a, cf); return; }
520  else if (exp == -1) { *b = naInvers(a, cf); return; }
521 
522  int expAbs = exp; if (expAbs < 0) expAbs = -expAbs;
523 
524  /* now compute a^expAbs */
525  poly pow; poly aAsPoly = (poly)a;
526  if (expAbs <= 7)
527  {
528  pow = p_Copy(aAsPoly, naRing);
529  for (int i = 2; i <= expAbs; i++)
530  {
531  pow = p_Mult_q(pow, p_Copy(aAsPoly, naRing), naRing);
532  heuristicReduce(pow, naMinpoly, cf);
533  }
534  definiteReduce(pow, naMinpoly, cf);
535  }
536  else
537  {
538  pow = p_ISet(1, naRing);
539  poly factor = p_Copy(aAsPoly, naRing);
540  while (expAbs != 0)
541  {
542  if (expAbs & 1)
543  {
544  pow = p_Mult_q(pow, p_Copy(factor, naRing), naRing);
545  heuristicReduce(pow, naMinpoly, cf);
546  }
547  expAbs = expAbs / 2;
548  if (expAbs != 0)
549  {
550  factor = p_Mult_q(factor, p_Copy(factor, naRing), naRing);
551  heuristicReduce(factor, naMinpoly, cf);
552  }
553  }
554  p_Delete(&factor, naRing);
555  definiteReduce(pow, naMinpoly, cf);
556  }
557 
558  /* invert if original exponent was negative */
559  number n = (number)pow;
560  if (exp < 0)
561  {
562  number m = naInvers(n, cf);
563  naDelete(&n, cf);
564  n = m;
565  }
566  *b = n;
567 }
568 
569 /* may reduce p modulo the reducer by calling definiteReduce;
570  the decision is made based on the following heuristic
571  (which should also only be changed here in this method):
572  if (deg(p) > 10*deg(reducer) then perform reduction;
573  modifies p */
574 void heuristicReduce(poly &p, poly reducer, const coeffs cf)
575 {
576  #ifdef LDEBUG
577  p_Test((poly)p, naRing);
578  p_Test((poly)reducer, naRing);
579  #endif
580  if (p_Totaldegree(p, naRing) > 10 * p_Totaldegree(reducer, naRing))
581  definiteReduce(p, reducer, cf);
582 }
583 
584 void naWriteLong(number a, const coeffs cf)
585 {
586  naTest(a);
587  if (a == NULL)
588  StringAppendS("0");
589  else
590  {
591  poly aAsPoly = (poly)a;
592  /* basically, just write aAsPoly using p_Write,
593  but use brackets around the output, if a is not
594  a constant living in naCoeffs = cf->extRing->cf */
595  BOOLEAN useBrackets = !(p_IsConstant(aAsPoly, naRing));
596  if (useBrackets) StringAppendS("(");
597  p_String0Long(aAsPoly, naRing, naRing);
598  if (useBrackets) StringAppendS(")");
599  }
600 }
601 
602 void naWriteShort(number a, const coeffs cf)
603 {
604  naTest(a);
605  if (a == NULL)
606  StringAppendS("0");
607  else
608  {
609  poly aAsPoly = (poly)a;
610  /* basically, just write aAsPoly using p_Write,
611  but use brackets around the output, if a is not
612  a constant living in naCoeffs = cf->extRing->cf */
613  BOOLEAN useBrackets = !(p_IsConstant(aAsPoly, naRing));
614  if (useBrackets) StringAppendS("(");
615  p_String0Short(aAsPoly, naRing, naRing);
616  if (useBrackets) StringAppendS(")");
617  }
618 }
619 
620 const char * naRead(const char *s, number *a, const coeffs cf)
621 {
622  poly aAsPoly;
623  const char * result = p_Read(s, aAsPoly, naRing);
624  if (aAsPoly!=NULL) definiteReduce(aAsPoly, naMinpoly, cf);
625  *a = (number)aAsPoly;
626  return result;
627 }
628 
629 #if 0
630 /* implemented by the rule lcm(a, b) = a * b / gcd(a, b) */
631 number naLcm(number a, number b, const coeffs cf)
632 {
633  naTest(a); naTest(b);
634  if (a == NULL) return NULL;
635  if (b == NULL) return NULL;
636  number theProduct = (number)p_Mult_q(p_Copy((poly)a, naRing),
637  p_Copy((poly)b, naRing), naRing);
638  /* note that theProduct needs not be reduced w.r.t. naMinpoly;
639  but the final division will take care of the necessary reduction */
640  number theGcd = naGcd(a, b, cf);
641  return naDiv(theProduct, theGcd, cf);
642 }
643 #endif
644 number napNormalizeHelper(number b, const coeffs cf)
645 {
646  number h=n_Init(1,naRing->cf);
647  poly bb=(poly)b;
648  number d;
649  while(bb!=NULL)
650  {
651  d=n_NormalizeHelper(h,pGetCoeff(bb), naRing->cf);
652  n_Delete(&h,naRing->cf);
653  h=d;
654  pIter(bb);
655  }
656  return h;
657 }
658 number naLcmContent(number a, number b, const coeffs cf)
659 {
660  if (nCoeff_is_Zp(naRing->cf)) return naCopy(a,cf);
661 #if 0
662  else {
663  number g = ndGcd(a, b, cf);
664  return g;
665  }
666 #else
667  {
668  a=(number)p_Copy((poly)a,naRing);
669  number t=napNormalizeHelper(b,cf);
670  if(!n_IsOne(t,naRing->cf))
671  {
672  number bt, rr;
673  poly xx=(poly)a;
674  while (xx!=NULL)
675  {
676  bt = n_SubringGcd(t, pGetCoeff(xx), naRing->cf);
677  rr = n_Mult(t, pGetCoeff(xx), naRing->cf);
678  n_Delete(&pGetCoeff(xx),naRing->cf);
679  pGetCoeff(xx) = n_Div(rr, bt, naRing->cf);
680  n_Normalize(pGetCoeff(xx),naRing->cf);
681  n_Delete(&bt,naRing->cf);
682  n_Delete(&rr,naRing->cf);
683  pIter(xx);
684  }
685  }
686  n_Delete(&t,naRing->cf);
687  return (number) a;
688  }
689 #endif
690 }
691 
692 /* expects *param to be castable to AlgExtInfo */
693 static BOOLEAN naCoeffIsEqual(const coeffs cf, n_coeffType n, void * param)
694 {
695  if (n_algExt != n) return FALSE;
696  AlgExtInfo *e = (AlgExtInfo *)param;
697  /* for extension coefficient fields we expect the underlying
698  polynomial rings to be IDENTICAL, i.e. the SAME OBJECT;
699  this expectation is based on the assumption that we have properly
700  registered cf and perform reference counting rather than creating
701  multiple copies of the same coefficient field/domain/ring */
702  if (naRing == e->r)
703  return TRUE;
704  /* (Note that then also the minimal ideals will necessarily be
705  the same, as they are attached to the ring.) */
706 
707  // NOTE: Q(a)[x] && Q(a)[y] should better share the _same_ Q(a)...
708  if( rEqual(naRing, e->r, TRUE) ) // also checks the equality of qideals
709  {
710  const ideal mi = naRing->qideal;
711  assume( IDELEMS(mi) == 1 );
712  const ideal ii = e->r->qideal;
713  assume( IDELEMS(ii) == 1 );
714 
715  // TODO: the following should be extended for 2 *equal* rings...
716  assume( p_EqualPolys(mi->m[0], ii->m[0], naRing, e->r) );
717 
718  rDelete(e->r);
719 
720  return TRUE;
721  }
722 
723  return FALSE;
724 
725 }
726 
727 int naSize(number a, const coeffs cf)
728 {
729  if (a == NULL) return -1;
730  /* this has been taken from the old implementation of field extensions,
731  where we computed the sum of the degree and the number of terms in
732  (poly)a; so we leave it at that, for the time being;
733  maybe, the number of terms alone is a better measure? */
734  poly aAsPoly = (poly)a;
735  int theDegree = 0; int noOfTerms = 0;
736  while (aAsPoly != NULL)
737  {
738  noOfTerms++;
739  int d = p_GetExp(aAsPoly, 1, naRing);
740  if (d > theDegree) theDegree = d;
741  pIter(aAsPoly);
742  }
743  return theDegree + noOfTerms;
744 }
745 
746 /* performs polynomial division and overrides p by the remainder
747  of division of p by the reducer;
748  modifies p */
749 void definiteReduce(poly &p, poly reducer, const coeffs cf)
750 {
751  #ifdef LDEBUG
752  p_Test((poly)p, naRing);
753  p_Test((poly)reducer, naRing);
754  #endif
755  if ((p!=NULL) && (p_GetExp(p,1,naRing)>=p_GetExp(reducer,1,naRing)))
756  {
757  p_PolyDiv(p, reducer, FALSE, naRing);
758  }
759 }
760 
761 void naNormalize(number &a, const coeffs cf)
762 {
763  poly aa=(poly)a;
764  if (aa!=naMinpoly)
765  definiteReduce(aa,naMinpoly,cf);
766  a=(number)aa;
767 }
768 
769 number naConvFactoryNSingN( const CanonicalForm n, const coeffs cf)
770 {
771  if (n.isZero()) return NULL;
773  return (number)p;
774 }
775 CanonicalForm naConvSingNFactoryN( number n, BOOLEAN /*setChar*/, const coeffs cf )
776 {
777  naTest(n);
778  if (n==NULL) return CanonicalForm(0);
779 
780  return convSingPFactoryP((poly)n,naRing);
781 }
782 
783 /* IMPORTANT NOTE: Since an algebraic field extension is again a field,
784  the gcd of two elements is not very interesting. (It
785  is actually any unit in the field, i.e., any non-
786  zero element.) Note that the below method does not operate
787  in this strong sense but rather computes the gcd of
788  two given elements in the underlying polynomial ring. */
789 number naGcd(number a, number b, const coeffs cf)
790 {
791  if (a==NULL) return naCopy(b,cf);
792  if (b==NULL) return naCopy(a,cf);
793 
794  poly ax=(poly)a;
795  poly bx=(poly)b;
796  if (pNext(ax)!=NULL)
797  return (number)p_Copy(ax, naRing);
798  else
799  {
800  if(nCoeff_is_Zp(naRing->cf))
801  return naInit(1,cf);
802  else
803  {
804  number x = n_Copy(pGetCoeff((poly)a),naRing->cf);
805  if (n_IsOne(x,naRing->cf))
806  return (number)p_NSet(x,naRing);
807  while (pNext(ax)!=NULL)
808  {
809  pIter(ax);
810  number y = n_SubringGcd(x, pGetCoeff(ax), naRing->cf);
811  n_Delete(&x,naRing->cf);
812  x = y;
813  if (n_IsOne(x,naRing->cf))
814  return (number)p_NSet(x,naRing);
815  }
816  do
817  {
818  number y = n_SubringGcd(x, pGetCoeff(bx), naRing->cf);
819  n_Delete(&x,naRing->cf);
820  x = y;
821  if (n_IsOne(x,naRing->cf))
822  return (number)p_NSet(x,naRing);
823  pIter(bx);
824  }
825  while (bx!=NULL);
826  return (number)p_NSet(x,naRing);
827  }
828  }
829 #if 0
830  naTest(a); naTest(b);
831  const ring R = naRing;
832  return (number) singclap_gcd(p_Copy((poly)a, R), p_Copy((poly)b, R), R);
833 #endif
834 // return (number)p_Gcd((poly)a, (poly)b, naRing);
835 }
836 
837 number naInvers(number a, const coeffs cf)
838 {
839  naTest(a);
840  if (a == NULL) WerrorS(nDivBy0);
841 
842  poly aFactor = NULL; poly mFactor = NULL; poly theGcd = NULL;
843 // singclap_extgcd!
844  const BOOLEAN ret = singclap_extgcd ((poly)a, naMinpoly, theGcd, aFactor, mFactor, naRing);
845 
846  assume( !ret );
847 
848 // if( ret ) theGcd = p_ExtGcd((poly)a, aFactor, naMinpoly, mFactor, naRing);
849 
850  naTest((number)theGcd); naTest((number)aFactor); naTest((number)mFactor);
851  p_Delete(&mFactor, naRing);
852 
853  // /* the gcd must be 1 since naMinpoly is irreducible and a != NULL: */
854  // assume(naIsOne((number)theGcd, cf));
855 
856  if( !naIsOne((number)theGcd, cf) )
857  {
858  WerrorS("zero divisor found - your minpoly is not irreducible");
859  p_Delete(&aFactor, naRing); aFactor = NULL;
860  }
861  p_Delete(&theGcd, naRing);
862 
863  return (number)(aFactor);
864 }
865 
866 /* assumes that src = Q or Z, dst = Q(a) */
867 number naMap00(number a, const coeffs src, const coeffs dst)
868 {
869  if (n_IsZero(a, src)) return NULL;
870  assume(src->rep == dst->extRing->cf->rep);
871  poly result = p_One(dst->extRing);
872  p_SetCoeff(result, n_Copy(a, src), dst->extRing);
873  return (number)result;
874 }
875 
876 /* assumes that src = Z, dst = K(a) */
877 number naMapZ0(number a, const coeffs src, const coeffs dst)
878 {
879  if (n_IsZero(a, src)) return NULL;
880  poly result = p_One(dst->extRing);
881  nMapFunc nMap=n_SetMap(src,dst->extRing->cf);
882  p_SetCoeff(result, nMap(a, src, dst->extRing->cf), dst->extRing);
883  if (n_IsZero(pGetCoeff(result),dst->extRing->cf))
884  p_Delete(&result,dst->extRing);
885  return (number)result;
886 }
887 
888 /* assumes that src = Z/p, dst = Q(a) */
889 number naMapP0(number a, const coeffs src, const coeffs dst)
890 {
891  if (n_IsZero(a, src)) return NULL;
892  /* mapping via intermediate int: */
893  int n = n_Int(a, src);
894  number q = n_Init(n, dst->extRing->cf);
895  poly result = p_One(dst->extRing);
896  p_SetCoeff(result, q, dst->extRing);
897  return (number)result;
898 }
899 
900 #if 0
901 /* assumes that either src = Q(a), dst = Q(a), or
902  src = Z/p(a), dst = Z/p(a) */
903 number naCopyMap(number a, const coeffs src, const coeffs dst)
904 {
905  return naCopy(a, dst);
906 }
907 #endif
908 
909 number naCopyTrans2AlgExt(number a, const coeffs src, const coeffs dst)
910 {
911  assume (nCoeff_is_transExt (src));
912  assume (nCoeff_is_algExt (dst));
913  fraction fa=(fraction)a;
914  poly p, q;
915  if (rSamePolyRep(src->extRing, dst->extRing))
916  {
917  p = p_Copy(NUM(fa),src->extRing);
918  if (!DENIS1(fa))
919  {
920  q = p_Copy(DEN(fa),src->extRing);
921  assume (q != NULL);
922  }
923  }
924  else
925  {
926  assume ((strcmp(rRingVar(0,src->extRing),rRingVar(0,dst->extRing))==0) && (rVar (src->extRing) == rVar (dst->extRing)));
927 
928  nMapFunc nMap= n_SetMap (src->extRing->cf, dst->extRing->cf);
929 
930  assume (nMap != NULL);
931  p= p_PermPoly (NUM (fa), NULL, src->extRing, dst->extRing,nMap, NULL,rVar (src->extRing));
932  if (!DENIS1(fa))
933  {
934  q= p_PermPoly (DEN (fa), NULL, src->extRing, dst->extRing,nMap, NULL,rVar (src->extRing));
935  assume (q != NULL);
936  }
937  }
938  definiteReduce(p, dst->extRing->qideal->m[0], dst);
939  p_Test (p, dst->extRing);
940  if (!DENIS1(fa))
941  {
942  definiteReduce(q, dst->extRing->qideal->m[0], dst);
943  p_Test (q, dst->extRing);
944  if (q != NULL)
945  {
946  number t= naDiv ((number)p,(number)q, dst);
947  p_Delete (&p, dst->extRing);
948  p_Delete (&q, dst->extRing);
949  return t;
950  }
951  WerrorS ("mapping denominator to zero");
952  }
953  return (number) p;
954 }
955 
956 /* assumes that src = Q, dst = Z/p(a) */
957 number naMap0P(number a, const coeffs src, const coeffs dst)
958 {
959  if (n_IsZero(a, src)) return NULL;
960  // int p = rChar(dst->extRing);
961 
962  number q = nlModP(a, src, dst->extRing->cf); // FIXME? TODO? // extern number nlModP(number q, const coeffs Q, const coeffs Zp); // Map q \in QQ \to pZ
963 
964  poly result = p_NSet(q, dst->extRing);
965 
966  return (number)result;
967 }
968 
969 /* assumes that src = Z/p, dst = Z/p(a) */
970 number naMapPP(number a, const coeffs src, const coeffs dst)
971 {
972  if (n_IsZero(a, src)) return NULL;
973  assume(src == dst->extRing->cf);
974  poly result = p_One(dst->extRing);
975  p_SetCoeff(result, n_Copy(a, src), dst->extRing);
976  return (number)result;
977 }
978 
979 /* assumes that src = Z/u, dst = Z/p(a), where u != p */
980 number naMapUP(number a, const coeffs src, const coeffs dst)
981 {
982  if (n_IsZero(a, src)) return NULL;
983  /* mapping via intermediate int: */
984  int n = n_Int(a, src);
985  number q = n_Init(n, dst->extRing->cf);
986  poly result = p_One(dst->extRing);
987  p_SetCoeff(result, q, dst->extRing);
988  return (number)result;
989 }
990 
991 number naGenMap(number a, const coeffs cf, const coeffs dst)
992 {
993  if (a==NULL) return NULL;
994 
995  const ring rSrc = cf->extRing;
996  const ring rDst = dst->extRing;
997 
998  const nMapFunc nMap=n_SetMap(rSrc->cf,rDst->cf);
999  poly f = (poly)a;
1000  poly g = prMapR(f, nMap, rSrc, rDst);
1001 
1002  n_Test((number)g, dst);
1003  return (number)g;
1004 }
1005 
1006 number naGenTrans2AlgExt(number a, const coeffs cf, const coeffs dst)
1007 {
1008  if (a==NULL) return NULL;
1009 
1010  const ring rSrc = cf->extRing;
1011  const ring rDst = dst->extRing;
1012 
1013  const nMapFunc nMap=n_SetMap(rSrc->cf,rDst->cf);
1014  fraction f = (fraction)a;
1015  poly g = prMapR(NUM(f), nMap, rSrc, rDst);
1016 
1017  number result=NULL;
1018  poly h = NULL;
1019 
1020  if (!DENIS1(f))
1021  h = prMapR(DEN(f), nMap, rSrc, rDst);
1022 
1023  if (h!=NULL)
1024  {
1025  result=naDiv((number)g,(number)h,dst);
1026  p_Delete(&g,dst->extRing);
1027  p_Delete(&h,dst->extRing);
1028  }
1029  else
1030  result=(number)g;
1031 
1032  n_Test((number)result, dst);
1033  return (number)result;
1034 }
1035 
1036 nMapFunc naSetMap(const coeffs src, const coeffs dst)
1037 {
1038  /* dst is expected to be an algebraic field extension */
1039  assume(getCoeffType(dst) == ID);
1040 
1041  if( src == dst ) return ndCopyMap;
1042 
1043  int h = 0; /* the height of the extension tower given by dst */
1044  coeffs bDst = nCoeff_bottom(dst, h); /* the bottom field in the tower dst */
1045  coeffs bSrc = nCoeff_bottom(src, h); /* the bottom field in the tower src */
1046 
1047  /* for the time being, we only provide maps if h = 1 or 0 */
1048  if (h==0)
1049  {
1050  if ((src->rep==n_rep_gap_rat) && nCoeff_is_Q(bDst))
1051  return naMap00; /// Q or Z --> Q(a)
1052  if ((src->rep==n_rep_gap_gmp) && nCoeff_is_Q(bDst))
1053  return naMapZ0; /// Z --> Q(a)
1054  if (nCoeff_is_Zp(src) && nCoeff_is_Q(bDst))
1055  return naMapP0; /// Z/p --> Q(a)
1056  if (nCoeff_is_Q_or_BI(src) && nCoeff_is_Zp(bDst))
1057  return naMap0P; /// Q --> Z/p(a)
1058  if ((src->rep==n_rep_gap_gmp) && nCoeff_is_Zp(bDst))
1059  return naMapZ0; /// Z --> Z/p(a)
1060  if (nCoeff_is_Zp(src) && nCoeff_is_Zp(bDst))
1061  {
1062  if (src->ch == dst->ch) return naMapPP; /// Z/p --> Z/p(a)
1063  else return naMapUP; /// Z/u --> Z/p(a)
1064  }
1065  }
1066  if (h != 1) return NULL;
1067  if ((!nCoeff_is_Zp(bDst)) && (!nCoeff_is_Q(bDst))) return NULL;
1068  if ((!nCoeff_is_Zp(bSrc)) && (!nCoeff_is_Q_or_BI(bSrc))) return NULL;
1069 
1070  nMapFunc nMap=n_SetMap(src->extRing->cf,dst->extRing->cf);
1071  if (rSamePolyRep(src->extRing, dst->extRing) && (strcmp(rRingVar(0, src->extRing), rRingVar(0, dst->extRing)) == 0))
1072  {
1073  if (src->type==n_algExt)
1074  return ndCopyMap; // naCopyMap; /// K(a) --> K(a)
1075  else
1076  return naCopyTrans2AlgExt;
1077  }
1078  else if ((nMap!=NULL) && (strcmp(rRingVar(0,src->extRing),rRingVar(0,dst->extRing))==0) && (rVar (src->extRing) == rVar (dst->extRing)))
1079  {
1080  if (src->type==n_algExt)
1081  return naGenMap; // naCopyMap; /// K(a) --> K'(a)
1082  else
1083  return naGenTrans2AlgExt;
1084  }
1085 
1086  return NULL; /// default
1087 }
1088 
1089 static int naParDeg(number a, const coeffs cf)
1090 {
1091  if (a == NULL) return -1;
1092  poly aa=(poly)a;
1093  return cf->extRing->pFDeg(aa,cf->extRing);
1094 }
1095 
1096 /// return the specified parameter as a number in the given alg. field
1097 static number naParameter(const int iParameter, const coeffs cf)
1098 {
1099  assume(getCoeffType(cf) == ID);
1100 
1101  const ring R = cf->extRing;
1102  assume( R != NULL );
1103  assume( 0 < iParameter && iParameter <= rVar(R) );
1104 
1105  poly p = p_One(R); p_SetExp(p, iParameter, 1, R); p_Setm(p, R);
1106 
1107  return (number) p;
1108 }
1109 
1110 
1111 /// if m == var(i)/1 => return i,
1112 int naIsParam(number m, const coeffs cf)
1113 {
1114  assume(getCoeffType(cf) == ID);
1115 
1116  const ring R = cf->extRing;
1117  assume( R != NULL );
1118 
1119  return p_Var( (poly)m, R );
1120 }
1121 
1122 
1123 static void naClearContent(ICoeffsEnumerator& numberCollectionEnumerator, number& c, const coeffs cf)
1124 {
1125  assume(cf != NULL);
1126  assume(getCoeffType(cf) == ID);
1127  assume(nCoeff_is_Q_algext(cf)); // only over (Q[a]/m(a)), while the default impl. is used over Zp[a]/m(a) !
1128 
1129  const ring R = cf->extRing;
1130  assume(R != NULL);
1131  const coeffs Q = R->cf;
1132  assume(Q != NULL);
1133  assume(nCoeff_is_Q(Q));
1134 
1135  numberCollectionEnumerator.Reset();
1136 
1137  if( !numberCollectionEnumerator.MoveNext() ) // empty zero polynomial?
1138  {
1139  c = n_Init(1, cf);
1140  return;
1141  }
1142 
1143  naTest(numberCollectionEnumerator.Current());
1144 
1145  // part 1, find a small candidate for gcd
1146  int s1; int s=2147483647; // max. int
1147 
1148  const BOOLEAN lc_is_pos=naGreaterZero(numberCollectionEnumerator.Current(),cf);
1149 
1150  int normalcount = 0;
1151 
1152  poly cand1, cand;
1153 
1154  do
1155  {
1156  number& n = numberCollectionEnumerator.Current();
1157  naNormalize(n, cf); ++normalcount;
1158 
1159  naTest(n);
1160 
1161  cand1 = (poly)n;
1162 
1163  s1 = p_Deg(cand1, R); // naSize?
1164  if (s>s1)
1165  {
1166  cand = cand1;
1167  s = s1;
1168  }
1169  } while (numberCollectionEnumerator.MoveNext() );
1170 
1171 // assume( nlGreaterZero(cand,cf) ); // cand may be a negative integer!
1172 
1173  cand = p_Copy(cand, R);
1174  // part 2: compute gcd(cand,all coeffs)
1175 
1176  numberCollectionEnumerator.Reset();
1177 
1178  int length = 0;
1179  while (numberCollectionEnumerator.MoveNext() )
1180  {
1181  number& n = numberCollectionEnumerator.Current();
1182  ++length;
1183 
1184  if( (--normalcount) <= 0)
1185  naNormalize(n, cf);
1186 
1187  naTest(n);
1188 
1189 // p_InpGcd(cand, (poly)n, R);
1190 
1191  cand = singclap_gcd(cand, p_Copy((poly)n, R), R);
1192 
1193 // cand1 = p_Gcd(cand,(poly)n, R); p_Delete(&cand, R); cand = cand1;
1194 
1195  assume( naGreaterZero((number)cand, cf) ); // ???
1196 /*
1197  if(p_IsConstant(cand,R))
1198  {
1199  c = cand;
1200 
1201  if(!lc_is_pos)
1202  {
1203  // make the leading coeff positive
1204  c = nlNeg(c, cf);
1205  numberCollectionEnumerator.Reset();
1206 
1207  while (numberCollectionEnumerator.MoveNext() )
1208  {
1209  number& nn = numberCollectionEnumerator.Current();
1210  nn = nlNeg(nn, cf);
1211  }
1212  }
1213  return;
1214  }
1215 */
1216 
1217  }
1218 
1219 
1220  // part3: all coeffs = all coeffs / cand
1221  if (!lc_is_pos)
1222  cand = p_Neg(cand, R);
1223 
1224  c = (number)cand; naTest(c);
1225 
1226  poly cInverse = (poly)naInvers(c, cf);
1227  assume(cInverse != NULL); // c is non-zero divisor!?
1228 
1229 
1230  numberCollectionEnumerator.Reset();
1231 
1232 
1233  while (numberCollectionEnumerator.MoveNext() )
1234  {
1235  number& n = numberCollectionEnumerator.Current();
1236 
1237  assume( length > 0 );
1238 
1239  if( --length > 0 )
1240  {
1241  assume( cInverse != NULL );
1242  n = (number) p_Mult_q(p_Copy(cInverse, R), (poly)n, R);
1243  }
1244  else
1245  {
1246  n = (number) p_Mult_q(cInverse, (poly)n, R);
1247  cInverse = NULL;
1248  assume(length == 0);
1249  }
1250 
1251  definiteReduce((poly &)n, naMinpoly, cf);
1252  }
1253 
1254  assume(length == 0);
1255  assume(cInverse == NULL); // p_Delete(&cInverse, R);
1256 
1257  // Quick and dirty fix for constant content clearing... !?
1258  CRecursivePolyCoeffsEnumerator<NAConverter> itr(numberCollectionEnumerator); // recursively treat the numbers as polys!
1259 
1260  number cc;
1261 
1262  n_ClearContent(itr, cc, Q); // TODO: get rid of (-LC) normalization!?
1263 
1264  // over alg. ext. of Q // takes over the input number
1265  c = (number) p_Mult_nn( (poly)c, cc, R);
1266 // p_Mult_q(p_NSet(cc, R), , R);
1267 
1268  n_Delete(&cc, Q);
1269 
1270  // TODO: the above is not enough! need GCD's of polynomial coeffs...!
1271 /*
1272  // old and wrong part of p_Content
1273  if (rField_is_Q_a(r) && !CLEARENUMERATORS) // should not be used anymore if CLEARENUMERATORS is 1
1274  {
1275  // we only need special handling for alg. ext.
1276  if (getCoeffType(r->cf)==n_algExt)
1277  {
1278  number hzz = n_Init(1, r->cf->extRing->cf);
1279  p=ph;
1280  while (p!=NULL)
1281  { // each monom: coeff in Q_a
1282  poly c_n_n=(poly)pGetCoeff(p);
1283  poly c_n=c_n_n;
1284  while (c_n!=NULL)
1285  { // each monom: coeff in Q
1286  d=n_NormalizeHelper(hzz,pGetCoeff(c_n),r->cf->extRing->cf);
1287  n_Delete(&hzz,r->cf->extRing->cf);
1288  hzz=d;
1289  pIter(c_n);
1290  }
1291  pIter(p);
1292  }
1293  // hzz contains the 1/lcm of all denominators in c_n_n
1294  h=n_Invers(hzz,r->cf->extRing->cf);
1295  n_Delete(&hzz,r->cf->extRing->cf);
1296  n_Normalize(h,r->cf->extRing->cf);
1297  if(!n_IsOne(h,r->cf->extRing->cf))
1298  {
1299  p=ph;
1300  while (p!=NULL)
1301  { // each monom: coeff in Q_a
1302  poly c_n=(poly)pGetCoeff(p);
1303  while (c_n!=NULL)
1304  { // each monom: coeff in Q
1305  d=n_Mult(h,pGetCoeff(c_n),r->cf->extRing->cf);
1306  n_Normalize(d,r->cf->extRing->cf);
1307  n_Delete(&pGetCoeff(c_n),r->cf->extRing->cf);
1308  pGetCoeff(c_n)=d;
1309  pIter(c_n);
1310  }
1311  pIter(p);
1312  }
1313  }
1314  n_Delete(&h,r->cf->extRing->cf);
1315  }
1316  }
1317 */
1318 
1319 
1320 // c = n_Init(1, cf); assume(FALSE); // TODO: NOT YET IMPLEMENTED!!!
1321 }
1322 
1323 
1324 static void naClearDenominators(ICoeffsEnumerator& numberCollectionEnumerator, number& c, const coeffs cf)
1325 {
1326  assume(cf != NULL);
1327  assume(getCoeffType(cf) == ID);
1328  assume(nCoeff_is_Q_algext(cf)); // only over (Q[a]/m(a)), while the default impl. is used over Zp[a]/m(a) !
1329 
1330  assume(cf->extRing != NULL);
1331  const coeffs Q = cf->extRing->cf;
1332  assume(Q != NULL);
1333  assume(nCoeff_is_Q(Q));
1334  number n;
1335  CRecursivePolyCoeffsEnumerator<NAConverter> itr(numberCollectionEnumerator); // recursively treat the numbers as polys!
1336  n_ClearDenominators(itr, n, Q); // this should probably be fine...
1337  c = (number)p_NSet(n, cf->extRing); // over alg. ext. of Q // takes over the input number
1338 }
1339 
1341 {
1342  if ((--cf->extRing->ref) == 0)
1343  rDelete(cf->extRing);
1344 }
1345 
1346 char* naCoeffString(const coeffs r) // currently also for tranext.
1347 {
1348  const char* const* p=n_ParameterNames(r);
1349  int l=0;
1350  int i;
1351  for(i=0; i<n_NumberOfParameters(r);i++)
1352  {
1353  l+=(strlen(p[i])+1);
1354  }
1355  char *s=(char *)omAlloc(l+10+1);
1356  s[0]='\0';
1357  snprintf(s,10+1,"%d",r->ch); /* Fp(a) or Q(a) */
1358  char tt[2];
1359  tt[0]=',';
1360  tt[1]='\0';
1361  for(i=0; i<n_NumberOfParameters(r);i++)
1362  {
1363  strcat(s,tt);
1364  strcat(s,p[i]);
1365  }
1366  return s;
1367 }
1368 
1369 number naChineseRemainder(number *x, number *q,int rl, BOOLEAN /*sym*/,CFArray &inv_cache,const coeffs cf)
1370 {
1371  poly *P=(poly*)omAlloc(rl*sizeof(poly*));
1372  number *X=(number *)omAlloc(rl*sizeof(number));
1373  int i;
1374  for(i=0;i<rl;i++) P[i]=p_Copy((poly)(x[i]),cf->extRing);
1375  poly result=p_ChineseRemainder(P,X,q,rl,inv_cache,cf->extRing);
1376  omFreeSize(X,rl*sizeof(number));
1377  omFreeSize(P,rl*sizeof(poly*));
1378  return ((number)result);
1379 }
1380 
1381 number naFarey(number p, number n, const coeffs cf)
1382 {
1383  // n is really a bigint
1384  poly result=p_Farey(p_Copy((poly)p,cf->extRing),n,cf->extRing);
1385  return ((number)result);
1386 }
1387 
1388 
1389 BOOLEAN naInitChar(coeffs cf, void * infoStruct)
1390 {
1391  assume( infoStruct != NULL );
1392 
1393  AlgExtInfo *e = (AlgExtInfo *)infoStruct;
1394  /// first check whether cf->extRing != NULL and delete old ring???
1395 
1396  assume(e->r != NULL); // extRing;
1397  assume(e->r->cf != NULL); // extRing->cf;
1398 
1399  assume((e->r->qideal != NULL) && // minideal has one
1400  (IDELEMS(e->r->qideal) == 1) && // non-zero generator
1401  (e->r->qideal->m[0] != NULL) ); // at m[0];
1402 
1403  assume( cf != NULL );
1404  assume(getCoeffType(cf) == ID); // coeff type;
1405 
1406  e->r->ref ++; // increase the ref.counter for the ground poly. ring!
1407  const ring R = e->r; // no copy!
1408  cf->extRing = R;
1409 
1410  /* propagate characteristic up so that it becomes
1411  directly accessible in cf: */
1412  cf->ch = R->cf->ch;
1413 
1414  cf->is_field=TRUE;
1415  cf->is_domain=TRUE;
1416  cf->rep=n_rep_poly;
1417 
1418  #ifdef LDEBUG
1420  #endif
1421 
1422  cf->cfCoeffString = naCoeffString;
1423 
1424  cf->cfGreaterZero = naGreaterZero;
1425  cf->cfGreater = naGreater;
1426  cf->cfEqual = naEqual;
1427  cf->cfIsZero = naIsZero;
1428  cf->cfIsOne = naIsOne;
1429  cf->cfIsMOne = naIsMOne;
1430  cf->cfInit = naInit;
1431  cf->cfFarey = naFarey;
1432  cf->cfChineseRemainder= naChineseRemainder;
1433  cf->cfInt = naInt;
1434  cf->cfInpNeg = naNeg;
1435  cf->cfAdd = naAdd;
1436  cf->cfSub = naSub;
1437  cf->cfMult = naMult;
1438  cf->cfDiv = naDiv;
1439  cf->cfExactDiv = naDiv;
1440  cf->cfPower = naPower;
1441  cf->cfCopy = naCopy;
1442 
1443  cf->cfWriteLong = naWriteLong;
1444 
1445  if( rCanShortOut(naRing) )
1446  cf->cfWriteShort = naWriteShort;
1447  else
1448  cf->cfWriteShort = naWriteLong;
1449 
1450  cf->cfRead = naRead;
1451  cf->cfDelete = naDelete;
1452  cf->cfSetMap = naSetMap;
1453  cf->cfGetDenom = naGetDenom;
1454  cf->cfGetNumerator = naGetNumerator;
1455  cf->cfRePart = naCopy;
1456  cf->cfCoeffWrite = naCoeffWrite;
1457  cf->cfNormalize = naNormalize;
1458  cf->cfKillChar = naKillChar;
1459 #ifdef LDEBUG
1460  cf->cfDBTest = naDBTest;
1461 #endif
1462  cf->cfGcd = naGcd;
1463  cf->cfNormalizeHelper = naLcmContent;
1464  cf->cfSize = naSize;
1465  cf->nCoeffIsEqual = naCoeffIsEqual;
1466  cf->cfInvers = naInvers;
1467  cf->convFactoryNSingN=naConvFactoryNSingN;
1468  cf->convSingNFactoryN=naConvSingNFactoryN;
1469  cf->cfParDeg = naParDeg;
1470 
1471  cf->iNumberOfParameters = rVar(R);
1472  cf->pParameterNames = (const char**)R->names;
1473  cf->cfParameter = naParameter;
1474  cf->has_simple_Inverse= R->cf->has_simple_Inverse;
1475  /* cf->has_simple_Alloc= FALSE; */
1476 
1477  if( nCoeff_is_Q(R->cf) )
1478  {
1479  cf->cfClearContent = naClearContent;
1480  cf->cfClearDenominators = naClearDenominators;
1481  }
1482 
1483  return FALSE;
1484 }
1485 
1487 
1488 template class IAccessor<snumber*>;
1489 
1490 /* --------------------------------------------------------------------*/
1491 #if 0
1492 void npolyCoeffWrite(const coeffs cf, BOOLEAN details)
1493 {
1494  assume( cf != NULL );
1495 
1496  const ring A = cf->extRing;
1497 
1498  assume( A != NULL );
1499  Print("// polynomial ring as coefficient ring :\n");
1500  rWrite(A);
1501  PrintLn();
1502 }
1503 number npolyMult(number a, number b, const coeffs cf)
1504 {
1505  naTest(a); naTest(b);
1506  if ((a == NULL)||(b == NULL)) return NULL;
1507  poly aTimesB = p_Mult_q(p_Copy((poly)a, naRing),
1508  p_Copy((poly)b, naRing), naRing);
1509  return (number)aTimesB;
1510 }
1511 
1512 void npolyPower(number a, int exp, number *b, const coeffs cf)
1513 {
1514  naTest(a);
1515 
1516  /* special cases first */
1517  if (a == NULL)
1518  {
1519  if (exp >= 0) *b = NULL;
1520  else WerrorS(nDivBy0);
1521  return;
1522  }
1523  else if (exp == 0) { *b = naInit(1, cf); return; }
1524  else if (exp == 1) { *b = naCopy(a, cf); return; }
1525  else if (exp == -1) { *b = naInvers(a, cf); return; }
1526 
1527  int expAbs = exp; if (expAbs < 0) expAbs = -expAbs;
1528 
1529  /* now compute a^expAbs */
1530  poly pow; poly aAsPoly = (poly)a;
1531  if (expAbs <= 7)
1532  {
1533  pow = p_Copy(aAsPoly, naRing);
1534  for (int i = 2; i <= expAbs; i++)
1535  {
1536  pow = p_Mult_q(pow, p_Copy(aAsPoly, naRing), naRing);
1537  }
1538  }
1539  else
1540  {
1541  pow = p_ISet(1, naRing);
1542  poly factor = p_Copy(aAsPoly, naRing);
1543  while (expAbs != 0)
1544  {
1545  if (expAbs & 1)
1546  {
1547  pow = p_Mult_q(pow, p_Copy(factor, naRing), naRing);
1548  }
1549  expAbs = expAbs / 2;
1550  if (expAbs != 0)
1551  {
1552  factor = p_Mult_q(factor, p_Copy(factor, naRing), naRing);
1553  }
1554  }
1555  p_Delete(&factor, naRing);
1556  }
1557 
1558  /* invert if original exponent was negative */
1559  number n = (number)pow;
1560  if (exp < 0)
1561  {
1562  number m = npolyInvers(n, cf);
1563  naDelete(&n, cf);
1564  n = m;
1565  }
1566  *b = n;
1567 }
1568 
1569 number npolyDiv(number a, number b, const coeffs cf)
1570 {
1571  naTest(a); naTest(b);
1572  if (b == NULL) WerrorS(nDivBy0);
1573  if (a == NULL) return NULL;
1575  return (number)p;
1576 }
1577 
1578 
1579 BOOLEAN npolyInitChar(coeffs cf, void * infoStruct)
1580 {
1581  assume( infoStruct != NULL );
1582 
1583  AlgExtInfo *e = (AlgExtInfo *)infoStruct;
1584  /// first check whether cf->extRing != NULL and delete old ring???
1585 
1586  assume(e->r != NULL); // extRing;
1587  assume(e->r->cf != NULL); // extRing->cf;
1588 
1589  assume( cf != NULL );
1590 
1591  e->r->ref ++; // increase the ref.counter for the ground poly. ring!
1592  const ring R = e->r; // no copy!
1593  cf->extRing = R;
1594 
1595  /* propagate characteristic up so that it becomes
1596  directly accessible in cf: */
1597  cf->ch = R->cf->ch;
1598  cf->is_field=FALSE;
1599  cf->is_domain=TRUE;
1600 
1601  cf->cfCoeffString = naCoeffString;
1602 
1603  cf->cfGreaterZero = naGreaterZero;
1604  cf->cfGreater = naGreater;
1605  cf->cfEqual = naEqual;
1606  cf->cfIsZero = naIsZero;
1607  cf->cfIsOne = naIsOne;
1608  cf->cfIsMOne = naIsMOne;
1609  cf->cfInit = naInit;
1610  cf->cfFarey = naFarey;
1611  cf->cfChineseRemainderSym= naChineseRemainder;
1612  cf->cfInt = naInt;
1613  cf->cfInpNeg = naNeg;
1614  cf->cfAdd = naAdd;
1615  cf->cfSub = naSub;
1616  cf->cfMult = npolyMult;
1617  cf->cfDiv = npolyDiv;
1618  cf->cfPower = naPower;
1619  cf->cfCopy = naCopy;
1620 
1621  cf->cfWriteLong = naWriteLong;
1622 
1623  if( rCanShortOut(naRing) )
1624  cf->cfWriteShort = naWriteShort;
1625  else
1626  cf->cfWriteShort = naWriteLong;
1627 
1628  cf->cfRead = naRead;
1629  cf->cfDelete = naDelete;
1630  cf->cfSetMap = naSetMap;
1631  cf->cfGetDenom = naGetDenom;
1632  cf->cfGetNumerator = naGetNumerator;
1633  cf->cfRePart = naCopy;
1634  cf->cfCoeffWrite = npolyCoeffWrite;
1635  cf->cfNormalize = npolyNormalize;
1636  cf->cfKillChar = naKillChar;
1637 #ifdef LDEBUG
1638  cf->cfDBTest = naDBTest;
1639 #endif
1640  cf->cfGcd = naGcd;
1641  cf->cfNormalizeHelper = naLcmContent;
1642  cf->cfSize = naSize;
1643  cf->nCoeffIsEqual = naCoeffIsEqual;
1644  cf->cfInvers = npolyInvers;
1645  cf->convFactoryNSingN=naConvFactoryNSingN;
1646  cf->convSingNFactoryN=naConvSingNFactoryN;
1647  cf->cfParDeg = naParDeg;
1648 
1649  cf->iNumberOfParameters = rVar(R);
1650  cf->pParameterNames = (const char**)R->names;
1651  cf->cfParameter = naParameter;
1652  cf->has_simple_Inverse=FALSE;
1653  /* cf->has_simple_Alloc= FALSE; */
1654 
1655  if( nCoeff_is_Q(R->cf) )
1656  {
1657  cf->cfClearContent = naClearContent;
1658  cf->cfClearDenominators = naClearDenominators;
1659  }
1660 
1661  return FALSE;
1662 }
1663 #endif
static FORCE_INLINE BOOLEAN n_Greater(number a, number b, const coeffs r)
ordered fields: TRUE iff &#39;a&#39; is larger than &#39;b&#39;; in Z/pZ: TRUE iff la > lb, where la and lb are the l...
Definition: coeffs.h:512
static FORCE_INLINE char const ** n_ParameterNames(const coeffs r)
Returns a (const!) pointer to (const char*) names of parameters.
Definition: coeffs.h:801
const CanonicalForm int s
Definition: facAbsFact.cc:55
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
void naDelete(number *a, const coeffs cf)
Definition: algext.cc:291
static void p_Monic(poly p, const ring r)
returns NULL if p == NULL, otherwise makes p monic by dividing by its leading coefficient (only done ...
Definition: algext.cc:133
const poly a
Definition: syzextra.cc:212
void PrintLn()
Definition: reporter.cc:327
#define naTest(a)
Definition: algext.cc:61
#define Print
Definition: emacs.cc:83
static FORCE_INLINE BOOLEAN nCoeff_is_Zp(const coeffs r)
Definition: coeffs.h:823
ring r
Definition: algext.h:40
BOOLEAN naIsZero(number a, const coeffs cf)
Definition: algext.cc:285
BOOLEAN naInitChar(coeffs cf, void *infoStruct)
Initialize the coeffs object.
Definition: algext.cc:1389
void p_String0Long(const poly p, ring lmRing, ring tailRing)
print p in a long way
Definition: polys0.cc:116
#define FALSE
Definition: auxiliary.h:140
return P p
Definition: myNF.cc:203
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the one element.
Definition: coeffs.h:469
poly p_NSet(number n, const ring r)
returns the poly representing the number n, destroys n
Definition: p_polys.cc:1448
number ndCopyMap(number a, const coeffs aRing, const coeffs r)
Definition: numbers.cc:239
number naChineseRemainder(number *x, number *q, int rl, BOOLEAN, CFArray &inv_cache, const coeffs cf)
Definition: algext.cc:1369
number naMapZ0(number a, const coeffs src, const coeffs dst)
Definition: algext.cc:877
void naKillChar(coeffs cf)
Definition: algext.cc:1340
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:539
void naPower(number a, int exp, number *b, const coeffs cf)
Definition: algext.cc:507
static FORCE_INLINE BOOLEAN nCoeff_is_Q_or_BI(const coeffs r)
Definition: coeffs.h:832
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
number naSub(number a, number b, const coeffs cf)
Definition: algext.cc:461
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:537
poly singclap_gcd(poly f, poly g, const ring r)
destroys f and g
Definition: clapsing.cc:287
(), see rinteger.h, new impl.
Definition: coeffs.h:111
const char * naRead(const char *s, number *a, const coeffs cf)
Definition: algext.cc:620
nMapFunc naSetMap(const coeffs src, const coeffs dst)
Get a mapping function from src into the domain of this type (n_algExt)
Definition: algext.cc:1036
number naInit(long i, const coeffs cf)
Definition: algext.cc:352
factory&#39;s main class
Definition: canonicalform.h:75
#define TRUE
Definition: auxiliary.h:144
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1436
static FORCE_INLINE void n_Normalize(number &n, const coeffs r)
inplace-normalization of n; produces some canonical representation of n;
Definition: coeffs.h:579
number naMap00(number a, const coeffs src, const coeffs dst)
Definition: algext.cc:867
g
Definition: cfModGcd.cc:4031
void WerrorS(const char *s)
Definition: feFopen.cc:24
long naInt(number &a, const coeffs cf)
Definition: algext.cc:358
BOOLEAN naGreater(number a, number b, const coeffs cf)
Definition: algext.cc:371
static FORCE_INLINE number n_NormalizeHelper(number a, number b, const coeffs r)
assume that r is a quotient field (otherwise, return 1) for arguments (a1/a2,b1/b2) return (lcm(a1...
Definition: coeffs.h:718
static poly p_GcdHelper(poly &p, poly &q, const ring r)
see p_Gcd; additional assumption: deg(p) >= deg(q); must destroy p and q (unless one of them is retur...
Definition: algext.cc:158
Templated accessor interface for accessing individual data (for instance, of an enumerator).
Definition: Enumerator.h:81
#define Q
Definition: sirandom.c:25
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
static FORCE_INLINE BOOLEAN nCoeff_is_Q(const coeffs r)
Definition: coeffs.h:829
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy ...
Definition: monomials.h:51
static void naClearDenominators(ICoeffsEnumerator &numberCollectionEnumerator, number &c, const coeffs cf)
Definition: algext.cc:1324
char * naCoeffString(const coeffs r)
Definition: algext.cc:1346
poly singclap_pdivide(poly f, poly g, const ring r)
Definition: clapsing.cc:547
#define omAlloc(size)
Definition: omAllocDecl.h:210
static BOOLEAN naCoeffIsEqual(const coeffs cf, n_coeffType n, void *param)
Definition: algext.cc:693
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:407
static BOOLEAN rCanShortOut(const ring r)
Definition: ring.h:531
static poly p_Gcd(const poly p, const poly q, const ring r)
Definition: algext.cc:178
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:810
poly pp
Definition: myNF.cc:296
(poly), see algext.h
Definition: coeffs.h:112
number naMapP0(number a, const coeffs src, const coeffs dst)
Definition: algext.cc:889
CanonicalForm lc(const CanonicalForm &f)
static FORCE_INLINE int n_NumberOfParameters(const coeffs r)
Returns the number of parameters.
Definition: coeffs.h:797
poly prMapR(poly src, nMapFunc nMap, ring src_r, ring dest_r)
Definition: prCopy.cc:47
#define pIter(p)
Definition: monomials.h:44
BOOLEAN naGreaterZero(number a, const coeffs cf)
forward declarations
Definition: algext.cc:391
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of &#39;a&#39; and &#39;b&#39;, i.e., a*b
Definition: coeffs.h:637
virtual void Reset()=0
Sets the enumerator to its initial position: -1, which is before the first element in the collection...
number naFarey(number p, number n, const coeffs cf)
Definition: algext.cc:1381
const char * p_Read(const char *st, poly &rc, const ring r)
Definition: p_polys.cc:1353
static poly p_ExtGcdHelper(poly &p, poly &pFactor, poly &q, poly &qFactor, ring r)
Definition: algext.cc:196
static FORCE_INLINE void n_ClearContent(ICoeffsEnumerator &numberCollectionEnumerator, number &c, const coeffs r)
Computes the content and (inplace) divides it out on a collection of numbers number c is the content ...
Definition: coeffs.h:931
#define naCoeffs
Definition: algext.cc:77
int naSize(number a, const coeffs cf)
Definition: algext.cc:727
long p_Deg(poly a, const ring r)
Definition: p_polys.cc:586
const ring r
Definition: syzextra.cc:208
poly p_PermPoly(poly p, const int *perm, const ring oldRing, const ring dst, nMapFunc nMap, const int *par_perm, int OldPar, BOOLEAN use_mult)
Definition: p_polys.cc:3937
Coefficient rings, fields and other domains suitable for Singular polynomials.
number naCopyTrans2AlgExt(number a, const coeffs src, const coeffs dst)
Definition: algext.cc:909
number naMapPP(number a, const coeffs src, const coeffs dst)
Definition: algext.cc:970
poly p_Farey(poly p, number N, const ring r)
Definition: p_polys.cc:61
static FORCE_INLINE BOOLEAN nCoeff_is_algExt(const coeffs r)
TRUE iff r represents an algebraic extension field.
Definition: coeffs.h:913
int naIsParam(number m, const coeffs cf)
if m == var(i)/1 => return i,
Definition: algext.cc:1112
static FORCE_INLINE long n_Int(number &n, const coeffs r)
conversion of n to an int; 0 if not possible in Z/pZ: the representing int lying in (-p/2 ...
Definition: coeffs.h:548
BOOLEAN naEqual(number a, number b, const coeffs cf)
Definition: algext.cc:300
number naConvFactoryNSingN(const CanonicalForm n, const coeffs cf)
Definition: algext.cc:769
poly p_One(const ring r)
Definition: p_polys.cc:1318
Concrete implementation of enumerators over polynomials.
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent : the integer VarOffset encodes:
Definition: p_polys.h:464
number naDiv(number a, number b, const coeffs cf)
Definition: algext.cc:483
number naGetDenom(number &a, const coeffs cf)
Definition: algext.cc:322
BOOLEAN naDBTest(number a, const char *f, const int l, const coeffs r)
Definition: algext.cc:246
#define assume(x)
Definition: mod2.h:405
static BOOLEAN p_IsConstant(const poly p, const ring r)
Definition: p_polys.h:1785
The main handler for Singular numbers which are suitable for Singular polynomials.
static void naClearContent(ICoeffsEnumerator &numberCollectionEnumerator, number &c, const coeffs cf)
Definition: algext.cc:1123
Templated enumerator interface for simple iteration over a generic collection of T&#39;s.
Definition: Enumerator.h:124
void StringAppendS(const char *st)
Definition: reporter.cc:107
#define A
Definition: sirandom.c:23
static int theDegree
Definition: cf_char.cc:21
poly convFactoryPSingP(const CanonicalForm &f, const ring r)
Definition: clapconv.cc:41
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition: coeffs.h:72
number naGenMap(number a, const coeffs cf, const coeffs dst)
Definition: algext.cc:991
const ring R
Definition: DebugPrint.cc:36
number naMult(number a, number b, const coeffs cf)
Definition: algext.cc:472
number nlModP(number q, const coeffs Q, const coeffs Zp)
Definition: longrat.cc:1425
virtual reference Current()=0
Gets the current element in the collection (read and write).
number naGenTrans2AlgExt(number a, const coeffs cf, const coeffs dst)
Definition: algext.cc:1006
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:739
All the auxiliary stuff.
static FORCE_INLINE number n_Invers(number a, const coeffs r)
return the multiplicative inverse of &#39;a&#39;; raise an error if &#39;a&#39; is not invertible ...
Definition: coeffs.h:565
int m
Definition: cfEzgcd.cc:119
BOOLEAN rSamePolyRep(ring r1, ring r2)
returns TRUE, if r1 and r2 represents the monomials in the same way FALSE, otherwise this is an analo...
Definition: ring.cc:1681
const char *const nDivBy0
Definition: numbers.h:83
poly p_ExtGcd(poly p, poly &pFactor, poly q, poly &qFactor, ring r)
assumes that p and q are univariate polynomials in r, mentioning the same variable; assumes a global ...
Definition: algext.cc:229
static FORCE_INLINE BOOLEAN nCoeff_is_transExt(const coeffs r)
TRUE iff r represents a transcendental extension field.
Definition: coeffs.h:921
void heuristicReduce(poly &p, poly reducer, const coeffs cf)
Definition: algext.cc:574
FILE * f
Definition: checklibs.c:7
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:294
static char * rRingVar(short i, const ring r)
Definition: ring.h:522
static poly p_Mult_nn(poly p, number n, const ring r)
Definition: p_polys.h:901
static int naParDeg(number a, const coeffs cf)
Definition: algext.cc:1089
static const n_coeffType ID
Our own type!
Definition: algext.cc:68
void naWriteLong(number a, const coeffs cf)
Definition: algext.cc:584
void rWrite(ring r, BOOLEAN details)
Definition: ring.cc:236
CanonicalForm factor
Definition: facAbsFact.cc:101
#define IDELEMS(i)
Definition: simpleideals.h:24
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the zero element.
Definition: coeffs.h:465
BOOLEAN rEqual(ring r1, ring r2, BOOLEAN qr)
returns TRUE, if r1 equals r2 FALSE, otherwise Equality is determined componentwise, if qr == 1, then qrideal equality is tested, as well
Definition: ring.cc:1633
static FORCE_INLINE nMapFunc n_SetMap(const coeffs src, const coeffs dst)
set the mapping function pointers for translating numbers from src to dst
Definition: coeffs.h:722
number naInvers(number a, const coeffs cf)
Definition: algext.cc:837
poly p_PolyDiv(poly &p, const poly divisor, const BOOLEAN needResult, const ring r)
assumes that p and divisor are univariate polynomials in r, mentioning the same variable; assumes div...
Definition: p_polys.cc:1781
void naCoeffWrite(const coeffs cf, BOOLEAN details)
Definition: algext.cc:400
go into polynomials over an alg. extension recursively
static FORCE_INLINE n_coeffType getCoeffType(const coeffs r)
Returns the type of coeffs domain.
Definition: coeffs.h:422
BOOLEAN p_EqualPolys(poly p1, poly p2, const ring r)
Definition: p_polys.cc:4318
static number ndGcd(number, number, const coeffs r)
Definition: numbers.cc:148
#define p_Test(p, r)
Definition: p_polys.h:160
static coeffs nCoeff_bottom(const coeffs r, int &height)
Definition: algext.cc:271
void p_Normalize(poly p, const ring r)
Definition: p_polys.cc:3632
void p_Write0(poly p, ring lmRing, ring tailRing)
Definition: polys0.cc:196
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:849
(number), see longrat.h
Definition: coeffs.h:110
number napNormalizeHelper(number b, const coeffs cf)
Definition: algext.cc:644
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent : VarOffset encodes the position in p->exp
Definition: p_polys.h:483
number naLcmContent(number a, number b, const coeffs cf)
Definition: algext.cc:658
n_coeffType
Definition: coeffs.h:27
#define naMinpoly
Definition: algext.cc:80
CanonicalForm cf
Definition: cfModGcd.cc:4024
static FORCE_INLINE void n_CoeffWrite(const coeffs r, BOOLEAN details=TRUE)
output the coeff description
Definition: coeffs.h:742
#define NULL
Definition: omList.c:10
CanonicalForm convSingPFactoryP(poly p, const ring r)
Definition: clapconv.cc:88
number naAdd(number a, number b, const coeffs cf)
Definition: algext.cc:450
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of &#39;n&#39;
Definition: coeffs.h:452
struct for passing initialization parameters to naInitChar
Definition: algext.h:40
void rDelete(ring r)
unconditionally deletes fields in r
Definition: ring.cc:448
CanonicalForm naConvSingNFactoryN(number n, BOOLEAN, const coeffs cf)
Definition: algext.cc:775
used for all algebraic extensions, i.e., the top-most extension in an extension tower is algebraic ...
Definition: coeffs.h:35
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of &#39;a&#39; and &#39;b&#39;, i.e., a/b; raises an error if &#39;b&#39; is not invertible in r exceptio...
Definition: coeffs.h:616
virtual bool MoveNext()=0
Advances the enumerator to the next element of the collection. returns true if the enumerator was suc...
number naCopy(number a, const coeffs cf)
Definition: algext.cc:309
number naGcd(number a, number b, const coeffs cf)
Definition: algext.cc:789
number naMap0P(number a, const coeffs src, const coeffs dst)
Definition: algext.cc:957
static FORCE_INLINE BOOLEAN nCoeff_is_Q_algext(const coeffs r)
is it an alg. ext. of Q?
Definition: coeffs.h:917
poly p_ChineseRemainder(poly *xx, number *x, number *q, int rl, CFArray &inv_cache, const ring R)
Definition: p_polys.cc:94
Variable x
Definition: cfModGcd.cc:4023
BOOLEAN singclap_extgcd(poly f, poly g, poly &res, poly &pa, poly &pb, const ring r)
Definition: clapsing.cc:460
#define pNext(p)
Definition: monomials.h:43
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:228
#define p_GetCoeff(p, r)
Definition: monomials.h:57
static FORCE_INLINE number n_SubringGcd(number a, number b, const coeffs r)
Definition: coeffs.h:689
int dReportError(const char *fmt,...)
Definition: dError.cc:45
number naNeg(number a, const coeffs cf)
this is in-place, modifies a
Definition: algext.cc:345
static FORCE_INLINE BOOLEAN nCoeff_is_Extension(const coeffs r)
Definition: coeffs.h:849
p exp[i]
Definition: DebugPrint.cc:39
static poly p_Neg(poly p, const ring r)
Definition: p_polys.h:1019
#define naRing
Definition: algext.cc:71
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:456
static FORCE_INLINE BOOLEAN n_IsMOne(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the additive inverse of the one element, i.e. -1.
Definition: coeffs.h:473
static FORCE_INLINE BOOLEAN n_GreaterZero(number n, const coeffs r)
ordered fields: TRUE iff &#39;n&#39; is positive; in Z/pZ: TRUE iff 0 < m <= roundedBelow(p/2), where m is the long representing n in C: TRUE iff (Im(n) != 0 and Im(n) >= 0) or (Im(n) == 0 and Re(n) >= 0) in K(a)/<p(a)>: TRUE iff (n != 0 and (LC(n) > 0 or deg(n) > 0)) in K(t_1, ..., t_n): TRUE iff (LC(numerator(n) is a constant and > 0) or (LC(numerator(n) is not a constant) in Z/2^kZ: TRUE iff 0 < n <= 2^(k-1) in Z/mZ: TRUE iff the internal mpz is greater than zero in Z: TRUE iff n > 0
Definition: coeffs.h:495
void definiteReduce(poly &p, poly reducer, const coeffs cf)
Definition: algext.cc:749
kBucketDestroy & P
Definition: myNF.cc:191
static number naParameter(const int iParameter, const coeffs cf)
return the specified parameter as a number in the given alg. field
Definition: algext.cc:1097
polyrec * poly
Definition: hilb.h:10
number naMapUP(number a, const coeffs src, const coeffs dst)
Definition: algext.cc:980
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:883
BOOLEAN naIsOne(number a, const coeffs cf)
Definition: algext.cc:328
Rational pow(const Rational &a, int e)
Definition: GMPrat.cc:418
static Poly * h
Definition: janet.cc:978
int BOOLEAN
Definition: auxiliary.h:131
const poly b
Definition: syzextra.cc:213
int p_Var(poly m, const ring r)
Definition: p_polys.cc:4462
poly p_ISet(long i, const ring r)
returns the poly representing the integer i
Definition: p_polys.cc:1302
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1026
BOOLEAN naIsMOne(number a, const coeffs cf)
Definition: algext.cc:336
void p_String0Short(const poly p, ring lmRing, ring tailRing)
print p in a short way, if possible
Definition: polys0.cc:97
void naWriteShort(number a, const coeffs cf)
Definition: algext.cc:602
void naNormalize(number &a, const coeffs cf)
Definition: algext.cc:761
return result
Definition: facAbsBiFact.cc:76
int l
Definition: cfEzgcd.cc:94
const CanonicalForm const CanonicalForm const CanonicalForm const CanonicalForm & cand
Definition: cfModGcd.cc:69
static FORCE_INLINE void n_ClearDenominators(ICoeffsEnumerator &numberCollectionEnumerator, number &d, const coeffs r)
(inplace) Clears denominators on a collection of numbers number d is the LCM of all the coefficient d...
Definition: coeffs.h:938
number naGetNumerator(number &a, const coeffs cf)
Definition: algext.cc:317