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