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 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 BOOLEAN naGreaterZero(number a, const coeffs cf);
74 BOOLEAN naGreater(number a, number b, const coeffs cf);
75 BOOLEAN naEqual(number a, number b, const coeffs cf);
76 BOOLEAN naIsOne(number a, const coeffs cf);
77 BOOLEAN naIsMOne(number a, const coeffs cf);
78 number naInit(long i, const coeffs cf);
79 number naNeg(number a, const coeffs cf);
80 number naInvers(number a, const coeffs cf);
81 number naAdd(number a, number b, const coeffs cf);
82 number naSub(number a, number b, const coeffs cf);
83 number naMult(number a, number b, const coeffs cf);
84 number naDiv(number a, number b, const coeffs cf);
85 void naPower(number a, int exp, number *b, const coeffs cf);
86 number naCopy(number a, const coeffs cf);
87 void naWriteLong(number a, const coeffs cf);
88 void naWriteShort(number a, const coeffs cf);
89 number naGetDenom(number &a, const coeffs cf);
90 number naGetNumerator(number &a, const coeffs cf);
91 number naGcd(number a, number b, const coeffs cf);
92 void naDelete(number *a, const coeffs cf);
93 void naCoeffWrite(const coeffs cf, BOOLEAN details);
94 //number naIntDiv(number a, number b, const coeffs cf);
95 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 void heuristicReduce(poly &p, poly reducer, const coeffs cf);
252 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 BOOLEAN naIsZero(number a, const coeffs cf)
273 {
274  naTest(a);
275  return (a == NULL);
276 }
277 
278 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 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 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 number naGetNumerator(number &a, const coeffs cf)
304 {
305  return naCopy(a, cf);
306 }
307 
308 number naGetDenom(number &a, const coeffs cf)
309 {
310  naTest(a);
311  return naInit(1, cf);
312 }
313 
314 BOOLEAN naIsOne(number a, const coeffs cf)
315 {
316  naTest(a);
317  poly aAsPoly = (poly)a;
318  if ((a==NULL) || (!p_IsConstant(aAsPoly, naRing))) return FALSE;
319  return n_IsOne(p_GetCoeff(aAsPoly, naRing), naCoeffs);
320 }
321 
322 BOOLEAN naIsMOne(number a, const coeffs cf)
323 {
324  naTest(a);
325  poly aAsPoly = (poly)a;
326  if ((a==NULL) || (!p_IsConstant(aAsPoly, naRing))) return FALSE;
327  return n_IsMOne(p_GetCoeff(aAsPoly, naRing), naCoeffs);
328 }
329 
330 /// this is in-place, modifies a
331 number naNeg(number a, const coeffs cf)
332 {
333  naTest(a);
334  if (a != NULL) a = (number)p_Neg((poly)a, naRing);
335  return a;
336 }
337 
338 number naInit(long i, const coeffs cf)
339 {
340  if (i == 0) return NULL;
341  else return (number)p_ISet(i, naRing);
342 }
343 
344 static number naInitMPZ(mpz_t m, const coeffs r)
345 {
346  number n=n_InitMPZ(m,r->extRing->cf);
347  return (number)p_NSet(n,r->extRing);
348 }
349 
350 long naInt(number &a, const coeffs cf)
351 {
352  naTest(a);
353  poly aAsPoly = (poly)a;
354  if(aAsPoly == NULL)
355  return 0;
356  if (!p_IsConstant(aAsPoly, naRing))
357  return 0;
358  assume( aAsPoly != NULL );
359  return n_Int(p_GetCoeff(aAsPoly, naRing), naCoeffs);
360 }
361 
362 /* TRUE iff (a != 0 and (b == 0 or deg(a) > deg(b) or (deg(a)==deg(b) && lc(a)>lc(b))) */
363 BOOLEAN naGreater(number a, number b, const coeffs cf)
364 {
365  naTest(a); naTest(b);
366  if (naIsZero(a, cf))
367  {
368  if (naIsZero(b, cf)) return FALSE;
369  return !n_GreaterZero(pGetCoeff((poly)b),naCoeffs);
370  }
371  if (naIsZero(b, cf))
372  {
373  return n_GreaterZero(pGetCoeff((poly)a),naCoeffs);
374  }
375  int aDeg = p_Totaldegree((poly)a, naRing);
376  int bDeg = p_Totaldegree((poly)b, naRing);
377  if (aDeg>bDeg) return TRUE;
378  if (aDeg<bDeg) return FALSE;
379  return n_Greater(pGetCoeff((poly)a),pGetCoeff((poly)b),naCoeffs);
380 }
381 
382 /* TRUE iff a != 0 and (LC(a) > 0 or deg(a) > 0) */
383 BOOLEAN naGreaterZero(number a, const coeffs cf)
384 {
385  naTest(a);
386  if (a == NULL) return FALSE;
387  if (n_GreaterZero(p_GetCoeff((poly)a, naRing), naCoeffs)) return TRUE;
388  if (p_Totaldegree((poly)a, naRing) > 0) return TRUE;
389  return FALSE;
390 }
391 
392 void naCoeffWrite(const coeffs cf, BOOLEAN details)
393 {
394  assume( cf != NULL );
395 
396  const ring A = cf->extRing;
397 
398  assume( A != NULL );
399  assume( A->cf != NULL );
400 
401  n_CoeffWrite(A->cf, details);
402 
403 // rWrite(A);
404 
405  const int P = rVar(A);
406  assume( P > 0 );
407 
408  PrintS("[");
409 
410  for (int nop=0; nop < P; nop ++)
411  {
412  Print("%s", rRingVar(nop, A));
413  if (nop!=P-1) PrintS(", ");
414  }
415 
416  PrintS("]/(");
417 
418  const ideal I = A->qideal;
419 
420  assume( I != NULL );
421  assume( IDELEMS(I) == 1 );
422 
423 
424  if ( details )
425  {
426  p_Write0( I->m[0], A);
427  PrintS(")");
428  }
429  else
430  PrintS("...)");
431 
432 /*
433  char *x = rRingVar(0, A);
434 
435  Print("// Coefficients live in the extension field K[%s]/<f(%s)>\n", x, x);
436  Print("// with the minimal polynomial f(%s) = %s\n", x,
437  p_String(A->qideal->m[0], A));
438  PrintS("// and K: ");
439 */
440 }
441 
442 number naAdd(number a, number b, const coeffs cf)
443 {
444  naTest(a); naTest(b);
445  if (a == NULL) return naCopy(b, cf);
446  if (b == NULL) return naCopy(a, cf);
447  poly aPlusB = p_Add_q(p_Copy((poly)a, naRing),
448  p_Copy((poly)b, naRing), naRing);
449  //definiteReduce(aPlusB, naMinpoly, cf);
450  return (number)aPlusB;
451 }
452 
453 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 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 number naDiv(number a, number b, const coeffs cf)
475 {
476  naTest(a); naTest(b);
477  if (b == NULL) WerrorS(nDivBy0);
478  if (a == NULL) return NULL;
479  poly bInverse = (poly)naInvers(b, cf);
480  if(bInverse != NULL) // b is non-zero divisor!
481  {
482  poly aDivB = p_Mult_q(p_Copy((poly)a, naRing), bInverse, naRing);
483  definiteReduce(aDivB, naMinpoly, cf);
484  p_Normalize(aDivB,naRing);
485  return (number)aDivB;
486  }
487  return NULL;
488 }
489 
490 /* 0^0 = 0;
491  for |exp| <= 7 compute power by a simple multiplication loop;
492  for |exp| >= 8 compute power along binary presentation of |exp|, e.g.
493  p^13 = p^1 * p^4 * p^8, where we utilise that
494  p^(2^(k+1)) = p^(2^k) * p^(2^k);
495  intermediate reduction modulo the minimal polynomial is controlled by
496  the in-place method heuristicReduce(poly, poly, coeffs); see there.
497 */
498 void naPower(number a, int exp, number *b, const coeffs cf)
499 {
500  naTest(a);
501 
502  /* special cases first */
503  if (a == NULL)
504  {
505  if (exp >= 0) *b = NULL;
506  else WerrorS(nDivBy0);
507  return;
508  }
509  else if (exp == 0) { *b = naInit(1, cf); return; }
510  else if (exp == 1) { *b = naCopy(a, cf); return; }
511  else if (exp == -1) { *b = naInvers(a, cf); return; }
512 
513  int expAbs = exp; if (expAbs < 0) expAbs = -expAbs;
514 
515  /* now compute a^expAbs */
516  poly pow; poly aAsPoly = (poly)a;
517  if (expAbs <= 7)
518  {
519  pow = p_Copy(aAsPoly, naRing);
520  for (int i = 2; i <= expAbs; i++)
521  {
522  pow = p_Mult_q(pow, p_Copy(aAsPoly, naRing), naRing);
524  }
526  }
527  else
528  {
529  pow = p_ISet(1, naRing);
530  poly factor = p_Copy(aAsPoly, naRing);
531  while (expAbs != 0)
532  {
533  if (expAbs & 1)
534  {
537  }
538  expAbs = expAbs / 2;
539  if (expAbs != 0)
540  {
543  }
544  }
547  }
548 
549  /* invert if original exponent was negative */
550  number n = (number)pow;
551  if (exp < 0)
552  {
553  number m = naInvers(n, cf);
554  naDelete(&n, cf);
555  n = m;
556  }
557  *b = n;
558 }
559 
560 /* may reduce p modulo the reducer by calling definiteReduce;
561  the decision is made based on the following heuristic
562  (which should also only be changed here in this method):
563  if (deg(p) > 10*deg(reducer) then perform reduction;
564  modifies p */
565 void heuristicReduce(poly &p, poly reducer, const coeffs cf)
566 {
567  #ifdef LDEBUG
568  p_Test((poly)p, naRing);
569  p_Test((poly)reducer, naRing);
570  #endif
571  if (p_Totaldegree(p, naRing) > 10 * p_Totaldegree(reducer, naRing))
572  definiteReduce(p, reducer, cf);
573 }
574 
575 void naWriteLong(number a, const coeffs cf)
576 {
577  naTest(a);
578  if (a == NULL)
579  StringAppendS("0");
580  else
581  {
582  poly aAsPoly = (poly)a;
583  /* basically, just write aAsPoly using p_Write,
584  but use brackets around the output, if a is not
585  a constant living in naCoeffs = cf->extRing->cf */
586  BOOLEAN useBrackets = !(p_IsConstant(aAsPoly, naRing));
587  if (useBrackets) StringAppendS("(");
588  p_String0Long(aAsPoly, naRing, naRing);
589  if (useBrackets) StringAppendS(")");
590  }
591 }
592 
593 void naWriteShort(number a, const coeffs cf)
594 {
595  naTest(a);
596  if (a == NULL)
597  StringAppendS("0");
598  else
599  {
600  poly aAsPoly = (poly)a;
601  /* basically, just write aAsPoly using p_Write,
602  but use brackets around the output, if a is not
603  a constant living in naCoeffs = cf->extRing->cf */
604  BOOLEAN useBrackets = !(p_IsConstant(aAsPoly, naRing));
605  if (useBrackets) StringAppendS("(");
606  p_String0Short(aAsPoly, naRing, naRing);
607  if (useBrackets) StringAppendS(")");
608  }
609 }
610 
611 const char * naRead(const char *s, number *a, const coeffs cf)
612 {
613  poly aAsPoly;
614  const char * result = p_Read(s, aAsPoly, naRing);
615  if (aAsPoly!=NULL) definiteReduce(aAsPoly, naMinpoly, cf);
616  *a = (number)aAsPoly;
617  return result;
618 }
619 
620 #if 0
621 /* implemented by the rule lcm(a, b) = a * b / gcd(a, b) */
622 number naLcm(number a, number b, const coeffs cf)
623 {
624  naTest(a); naTest(b);
625  if (a == NULL) return NULL;
626  if (b == NULL) return NULL;
627  number theProduct = (number)pp_Mult_qq((poly)a, (poly)b, naRing);
628  /* note that theProduct needs not be reduced w.r.t. naMinpoly;
629  but the final division will take care of the necessary reduction */
630  number theGcd = naGcd(a, b, cf);
631  return naDiv(theProduct, theGcd, cf);
632 }
633 #endif
634 number napNormalizeHelper(number b, const coeffs cf)
635 {
636  number h=n_Init(1,naRing->cf);
637  poly bb=(poly)b;
638  number d;
639  while(bb!=NULL)
640  {
641  d=n_NormalizeHelper(h,pGetCoeff(bb), naRing->cf);
642  n_Delete(&h,naRing->cf);
643  h=d;
644  pIter(bb);
645  }
646  return h;
647 }
648 number naLcmContent(number a, number b, const coeffs cf)
649 {
650  if (nCoeff_is_Zp(naRing->cf)) return naCopy(a,cf);
651 #if 0
652  else {
653  number g = ndGcd(a, b, cf);
654  return g;
655  }
656 #else
657  {
658  a=(number)p_Copy((poly)a,naRing);
659  number t=napNormalizeHelper(b,cf);
660  if(!n_IsOne(t,naRing->cf))
661  {
662  number bt, rr;
663  poly xx=(poly)a;
664  while (xx!=NULL)
665  {
666  bt = n_SubringGcd(t, pGetCoeff(xx), naRing->cf);
667  rr = n_Mult(t, pGetCoeff(xx), naRing->cf);
668  n_Delete(&pGetCoeff(xx),naRing->cf);
669  pGetCoeff(xx) = n_Div(rr, bt, naRing->cf);
670  n_Normalize(pGetCoeff(xx),naRing->cf);
671  n_Delete(&bt,naRing->cf);
672  n_Delete(&rr,naRing->cf);
673  pIter(xx);
674  }
675  }
676  n_Delete(&t,naRing->cf);
677  return (number) a;
678  }
679 #endif
680 }
681 
682 /* expects *param to be castable to AlgExtInfo */
683 static BOOLEAN naCoeffIsEqual(const coeffs cf, n_coeffType n, void * param)
684 {
685  if (n_algExt != n) return FALSE;
686  AlgExtInfo *e = (AlgExtInfo *)param;
687  /* for extension coefficient fields we expect the underlying
688  polynomial rings to be IDENTICAL, i.e. the SAME OBJECT;
689  this expectation is based on the assumption that we have properly
690  registered cf and perform reference counting rather than creating
691  multiple copies of the same coefficient field/domain/ring */
692  if (naRing == e->r)
693  return TRUE;
694  /* (Note that then also the minimal ideals will necessarily be
695  the same, as they are attached to the ring.) */
696 
697  // NOTE: Q(a)[x] && Q(a)[y] should better share the _same_ Q(a)...
698  if( rEqual(naRing, e->r, TRUE) ) // also checks the equality of qideals
699  {
700  const ideal mi = naRing->qideal;
701  assume( IDELEMS(mi) == 1 );
702  const ideal ii = e->r->qideal;
703  assume( IDELEMS(ii) == 1 );
704 
705  // TODO: the following should be extended for 2 *equal* rings...
706  assume( p_EqualPolys(mi->m[0], ii->m[0], naRing, e->r) );
707 
708  rDelete(e->r);
709 
710  return TRUE;
711  }
712 
713  return FALSE;
714 
715 }
716 
717 int naSize(number a, const coeffs cf)
718 {
719  if (a == NULL) return 0;
720  poly aAsPoly = (poly)a;
721  int theDegree = 0; int noOfTerms = 0;
722  while (aAsPoly != NULL)
723  {
724  noOfTerms++;
725  int d = p_GetExp(aAsPoly, 1, naRing);
726  if (d > theDegree) theDegree = d;
727  pIter(aAsPoly);
728  }
729  return (theDegree +1) * noOfTerms;
730 }
731 
732 /* performs polynomial division and overrides p by the remainder
733  of division of p by the reducer;
734  modifies p */
735 void definiteReduce(poly &p, poly reducer, const coeffs cf)
736 {
737  #ifdef LDEBUG
738  p_Test((poly)p, naRing);
739  p_Test((poly)reducer, naRing);
740  #endif
741  if ((p!=NULL) && (p_GetExp(p,1,naRing)>=p_GetExp(reducer,1,naRing)))
742  {
743  p_PolyDiv(p, reducer, FALSE, naRing);
744  }
745 }
746 
747 void naNormalize(number &a, const coeffs cf)
748 {
749  poly aa=(poly)a;
750  if (aa!=naMinpoly)
752  a=(number)aa;
753 }
754 
756 {
757  if (n.isZero()) return NULL;
758  poly p=convFactoryPSingP(n,naRing);
759  return (number)p;
760 }
761 CanonicalForm naConvSingNFactoryN( number n, BOOLEAN /*setChar*/, const coeffs cf )
762 {
763  naTest(n);
764  if (n==NULL) return CanonicalForm(0);
765 
766  return convSingPFactoryP((poly)n,naRing);
767 }
768 
769 /* IMPORTANT NOTE: Since an algebraic field extension is again a field,
770  the gcd of two elements is not very interesting. (It
771  is actually any unit in the field, i.e., any non-
772  zero element.) Note that the below method does not operate
773  in this strong sense but rather computes the gcd of
774  two given elements in the underlying polynomial ring. */
775 number naGcd(number a, number b, const coeffs cf)
776 {
777  if (a==NULL) return naCopy(b,cf);
778  if (b==NULL) return naCopy(a,cf);
779 
780  poly ax=(poly)a;
781  poly bx=(poly)b;
782  if (pNext(ax)!=NULL)
783  return (number)p_Copy(ax, naRing);
784  else
785  {
786  if(nCoeff_is_Zp(naRing->cf))
787  return naInit(1,cf);
788  else
789  {
790  number x = n_Copy(pGetCoeff((poly)a),naRing->cf);
791  if (n_IsOne(x,naRing->cf))
792  return (number)p_NSet(x,naRing);
793  while (pNext(ax)!=NULL)
794  {
795  pIter(ax);
796  number y = n_SubringGcd(x, pGetCoeff(ax), naRing->cf);
797  n_Delete(&x,naRing->cf);
798  x = y;
799  if (n_IsOne(x,naRing->cf))
800  return (number)p_NSet(x,naRing);
801  }
802  do
803  {
804  number y = n_SubringGcd(x, pGetCoeff(bx), naRing->cf);
805  n_Delete(&x,naRing->cf);
806  x = y;
807  if (n_IsOne(x,naRing->cf))
808  return (number)p_NSet(x,naRing);
809  pIter(bx);
810  }
811  while (bx!=NULL);
812  return (number)p_NSet(x,naRing);
813  }
814  }
815 #if 0
816  naTest(a); naTest(b);
817  const ring R = naRing;
818  return (number) singclap_gcd_r((poly)a, (poly)b, R);
819 #endif
820 // return (number)p_Gcd((poly)a, (poly)b, naRing);
821 }
822 
823 number naInvers(number a, const coeffs cf)
824 {
825  naTest(a);
826  if (a == NULL) WerrorS(nDivBy0);
827 
828  poly aFactor = NULL; poly mFactor = NULL; poly theGcd = NULL;
829 // singclap_extgcd!
830  const BOOLEAN ret = singclap_extgcd ((poly)a, naMinpoly, theGcd, aFactor, mFactor, naRing);
831 
832  assume( !ret );
833 
834 // if( ret ) theGcd = p_ExtGcd((poly)a, aFactor, naMinpoly, mFactor, naRing);
835 
836  naTest((number)theGcd); naTest((number)aFactor); naTest((number)mFactor);
837  p_Delete(&mFactor, naRing);
838 
839  // /* the gcd must be 1 since naMinpoly is irreducible and a != NULL: */
840  // assume(naIsOne((number)theGcd, cf));
841 
842  if( !naIsOne((number)theGcd, cf) )
843  {
844  WerrorS("zero divisor found - your minpoly is not irreducible");
845  p_Delete(&aFactor, naRing); aFactor = NULL;
846  }
847  p_Delete(&theGcd, naRing);
848 
849  return (number)(aFactor);
850 }
851 
852 /* assumes that src = Q or Z, dst = Q(a) */
853 number naMap00(number a, const coeffs src, const coeffs dst)
854 {
855  if (n_IsZero(a, src)) return NULL;
856  assume(src->rep == dst->extRing->cf->rep);
857  poly result = p_One(dst->extRing);
858  p_SetCoeff(result, n_Copy(a, src), dst->extRing);
859  return (number)result;
860 }
861 
862 /* assumes that src = Z, dst = K(a) */
863 number naMapZ0(number a, const coeffs src, const coeffs dst)
864 {
865  if (n_IsZero(a, src)) return NULL;
866  poly result = p_One(dst->extRing);
867  nMapFunc nMap=n_SetMap(src,dst->extRing->cf);
868  p_SetCoeff(result, nMap(a, src, dst->extRing->cf), dst->extRing);
869  if (n_IsZero(pGetCoeff(result),dst->extRing->cf))
870  p_Delete(&result,dst->extRing);
871  return (number)result;
872 }
873 
874 /* assumes that src = Z/p, dst = Q(a) */
875 number naMapP0(number a, const coeffs src, const coeffs dst)
876 {
877  if (n_IsZero(a, src)) return NULL;
878  /* mapping via intermediate int: */
879  int n = n_Int(a, src);
880  number q = n_Init(n, dst->extRing->cf);
881  poly result = p_One(dst->extRing);
882  p_SetCoeff(result, q, dst->extRing);
883  return (number)result;
884 }
885 
886 #if 0
887 /* assumes that either src = Q(a), dst = Q(a), or
888  src = Z/p(a), dst = Z/p(a) */
889 number naCopyMap(number a, const coeffs src, const coeffs dst)
890 {
891  return naCopy(a, dst);
892 }
893 #endif
894 
895 number naCopyTrans2AlgExt(number a, const coeffs src, const coeffs dst)
896 {
897  assume (nCoeff_is_transExt (src));
898  assume (nCoeff_is_algExt (dst));
899  fraction fa=(fraction)a;
900  poly p, q;
901  if (rSamePolyRep(src->extRing, dst->extRing))
902  {
903  p = p_Copy(NUM(fa),src->extRing);
904  if (!DENIS1(fa))
905  {
906  q = p_Copy(DEN(fa),src->extRing);
907  assume (q != NULL);
908  }
909  }
910  else
911  {
912  assume ((strcmp(rRingVar(0,src->extRing),rRingVar(0,dst->extRing))==0) && (rVar (src->extRing) == rVar (dst->extRing)));
913 
914  nMapFunc nMap= n_SetMap (src->extRing->cf, dst->extRing->cf);
915 
916  assume (nMap != NULL);
917  p= p_PermPoly (NUM (fa), NULL, src->extRing, dst->extRing,nMap, NULL,rVar (src->extRing));
918  if (!DENIS1(fa))
919  {
920  q= p_PermPoly (DEN (fa), NULL, src->extRing, dst->extRing,nMap, NULL,rVar (src->extRing));
921  assume (q != NULL);
922  }
923  }
924  definiteReduce(p, dst->extRing->qideal->m[0], dst);
925  p_Test (p, dst->extRing);
926  if (!DENIS1(fa))
927  {
928  definiteReduce(q, dst->extRing->qideal->m[0], dst);
929  p_Test (q, dst->extRing);
930  if (q != NULL)
931  {
932  number t= naDiv ((number)p,(number)q, dst);
933  p_Delete (&p, dst->extRing);
934  p_Delete (&q, dst->extRing);
935  return t;
936  }
937  WerrorS ("mapping denominator to zero");
938  }
939  return (number) p;
940 }
941 
942 /* assumes that src = Q, dst = Z/p(a) */
943 number naMap0P(number a, const coeffs src, const coeffs dst)
944 {
945  if (n_IsZero(a, src)) return NULL;
946  // int p = rChar(dst->extRing);
947 
948  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
949 
950  poly result = p_NSet(q, dst->extRing);
951 
952  return (number)result;
953 }
954 
955 /* assumes that src = Z/p, dst = Z/p(a) */
956 number naMapPP(number a, const coeffs src, const coeffs dst)
957 {
958  if (n_IsZero(a, src)) return NULL;
959  assume(src == dst->extRing->cf);
960  poly result = p_One(dst->extRing);
961  p_SetCoeff(result, n_Copy(a, src), dst->extRing);
962  return (number)result;
963 }
964 
965 /* assumes that src = Z/u, dst = Z/p(a), where u != p */
966 number naMapUP(number a, const coeffs src, const coeffs dst)
967 {
968  if (n_IsZero(a, src)) return NULL;
969  /* mapping via intermediate int: */
970  int n = n_Int(a, src);
971  number q = n_Init(n, dst->extRing->cf);
972  poly result = p_One(dst->extRing);
973  p_SetCoeff(result, q, dst->extRing);
974  return (number)result;
975 }
976 
977 number naGenMap(number a, const coeffs cf, const coeffs dst)
978 {
979  if (a==NULL) return NULL;
980 
981  const ring rSrc = cf->extRing;
982  const ring rDst = dst->extRing;
983 
984  const nMapFunc nMap=n_SetMap(rSrc->cf,rDst->cf);
985  poly f = (poly)a;
986  poly g = prMapR(f, nMap, rSrc, rDst);
987 
988  n_Test((number)g, dst);
989  return (number)g;
990 }
991 
992 number naGenTrans2AlgExt(number a, const coeffs cf, const coeffs dst)
993 {
994  if (a==NULL) return NULL;
995 
996  const ring rSrc = cf->extRing;
997  const ring rDst = dst->extRing;
998 
999  const nMapFunc nMap=n_SetMap(rSrc->cf,rDst->cf);
1000  fraction f = (fraction)a;
1001  poly g = prMapR(NUM(f), nMap, rSrc, rDst);
1002 
1003  number result=NULL;
1004  poly h = NULL;
1005 
1006  if (!DENIS1(f))
1007  h = prMapR(DEN(f), nMap, rSrc, rDst);
1008 
1009  if (h!=NULL)
1010  {
1011  result=naDiv((number)g,(number)h,dst);
1012  p_Delete(&g,dst->extRing);
1013  p_Delete(&h,dst->extRing);
1014  }
1015  else
1016  result=(number)g;
1017 
1018  n_Test((number)result, dst);
1019  return (number)result;
1020 }
1021 
1022 nMapFunc naSetMap(const coeffs src, const coeffs dst)
1023 {
1024  /* dst is expected to be an algebraic field extension */
1025  assume(getCoeffType(dst) == n_algExt);
1026 
1027  int h = 0; /* the height of the extension tower given by dst */
1028  coeffs bDst = nCoeff_bottom(dst, h); /* the bottom field in the tower dst */
1029  coeffs bSrc = nCoeff_bottom(src, h); /* the bottom field in the tower src */
1030 
1031  /* for the time being, we only provide maps if h = 1 or 0 */
1032  if (h==0)
1033  {
1034  if ((src->rep==n_rep_gap_rat) && nCoeff_is_Q(bDst))
1035  return naMap00; /// Q or Z --> Q(a)
1036  if ((src->rep==n_rep_gap_gmp) && nCoeff_is_Q(bDst))
1037  return naMapZ0; /// Z --> Q(a)
1038  if (nCoeff_is_Zp(src) && nCoeff_is_Q(bDst))
1039  return naMapP0; /// Z/p --> Q(a)
1040  if (nCoeff_is_Q_or_BI(src) && nCoeff_is_Zp(bDst))
1041  return naMap0P; /// Q --> Z/p(a)
1042  if ((src->rep==n_rep_gap_gmp) && nCoeff_is_Zp(bDst))
1043  return naMapZ0; /// Z --> Z/p(a)
1044  if (nCoeff_is_Zp(src) && nCoeff_is_Zp(bDst))
1045  {
1046  if (src->ch == dst->ch) return naMapPP; /// Z/p --> Z/p(a)
1047  else return naMapUP; /// Z/u --> Z/p(a)
1048  }
1049  }
1050  if (h != 1) return NULL;
1051  if ((!nCoeff_is_Zp(bDst)) && (!nCoeff_is_Q(bDst))) return NULL;
1052  if ((!nCoeff_is_Zp(bSrc)) && (!nCoeff_is_Q_or_BI(bSrc))) return NULL;
1053 
1054  nMapFunc nMap=n_SetMap(src->extRing->cf,dst->extRing->cf);
1055  if (rSamePolyRep(src->extRing, dst->extRing) && (strcmp(rRingVar(0, src->extRing), rRingVar(0, dst->extRing)) == 0))
1056  {
1057  if (src->type==n_algExt)
1058  return ndCopyMap; // naCopyMap; /// K(a) --> K(a)
1059  else
1060  return naCopyTrans2AlgExt;
1061  }
1062  else if ((nMap!=NULL) && (strcmp(rRingVar(0,src->extRing),rRingVar(0,dst->extRing))==0) && (rVar (src->extRing) == rVar (dst->extRing)))
1063  {
1064  if (src->type==n_algExt)
1065  return naGenMap; // naCopyMap; /// K(a) --> K'(a)
1066  else
1067  return naGenTrans2AlgExt;
1068  }
1069 
1070  return NULL; /// default
1071 }
1072 
1073 int naParDeg(number a, const coeffs cf)
1074 {
1075  if (a == NULL) return -1;
1076  poly aa=(poly)a;
1077  return cf->extRing->pFDeg(aa,cf->extRing);
1078 }
1079 
1080 /// return the specified parameter as a number in the given alg. field
1081 number naParameter(const int iParameter, const coeffs cf)
1082 {
1084 
1085  const ring R = cf->extRing;
1086  assume( R != NULL );
1087  assume( 0 < iParameter && iParameter <= rVar(R) );
1088 
1089  poly p = p_One(R); p_SetExp(p, iParameter, 1, R); p_Setm(p, R);
1090 
1091  return (number) p;
1092 }
1093 
1094 
1095 /// if m == var(i)/1 => return i,
1096 int naIsParam(number m, const coeffs cf)
1097 {
1099 
1100  const ring R = cf->extRing;
1101  assume( R != NULL );
1102 
1103  return p_Var( (poly)m, R );
1104 }
1105 
1106 
1107 static void naClearContent(ICoeffsEnumerator& numberCollectionEnumerator, number& c, const coeffs cf)
1108 {
1109  assume(cf != NULL);
1111  assume(nCoeff_is_Q_algext(cf)); // only over (Q[a]/m(a)), while the default impl. is used over Zp[a]/m(a) !
1112 
1113  const ring R = cf->extRing;
1114  assume(R != NULL);
1115  const coeffs Q = R->cf;
1116  assume(Q != NULL);
1117  assume(nCoeff_is_Q(Q));
1118 
1119  numberCollectionEnumerator.Reset();
1120 
1121  if( !numberCollectionEnumerator.MoveNext() ) // empty zero polynomial?
1122  {
1123  c = n_Init(1, cf);
1124  return;
1125  }
1126 
1127  naTest(numberCollectionEnumerator.Current());
1128 
1129  // part 1, find a small candidate for gcd
1130  int s1; int s=2147483647; // max. int
1131 
1132  const BOOLEAN lc_is_pos=naGreaterZero(numberCollectionEnumerator.Current(),cf);
1133 
1134  int normalcount = 0;
1135 
1136  poly cand1, cand;
1137 
1138  do
1139  {
1140  number& n = numberCollectionEnumerator.Current();
1141  naNormalize(n, cf); ++normalcount;
1142 
1143  naTest(n);
1144 
1145  cand1 = (poly)n;
1146 
1147  s1 = p_Deg(cand1, R); // naSize?
1148  if (s>s1)
1149  {
1150  cand = cand1;
1151  s = s1;
1152  }
1153  } while (numberCollectionEnumerator.MoveNext() );
1154 
1155 // assume( nlGreaterZero(cand,cf) ); // cand may be a negative integer!
1156 
1157  cand = p_Copy(cand, R);
1158  // part 2: compute gcd(cand,all coeffs)
1159 
1160  numberCollectionEnumerator.Reset();
1161 
1162  int length = 0;
1163  while (numberCollectionEnumerator.MoveNext() )
1164  {
1165  number& n = numberCollectionEnumerator.Current();
1166  ++length;
1167 
1168  if( (--normalcount) <= 0)
1169  naNormalize(n, cf);
1170 
1171  naTest(n);
1172 
1173 // p_InpGcd(cand, (poly)n, R);
1174 
1175  { // R->cf is QQ
1176  poly tmp=gcd_over_Q(cand,(poly)n,R);
1177  p_Delete(&cand,R);
1178  cand=tmp;
1179  }
1180 
1181 // cand1 = p_Gcd(cand,(poly)n, R); p_Delete(&cand, R); cand = cand1;
1182 
1183  assume( naGreaterZero((number)cand, cf) ); // ???
1184 /*
1185  if(p_IsConstant(cand,R))
1186  {
1187  c = cand;
1188 
1189  if(!lc_is_pos)
1190  {
1191  // make the leading coeff positive
1192  c = nlNeg(c, cf);
1193  numberCollectionEnumerator.Reset();
1194 
1195  while (numberCollectionEnumerator.MoveNext() )
1196  {
1197  number& nn = numberCollectionEnumerator.Current();
1198  nn = nlNeg(nn, cf);
1199  }
1200  }
1201  return;
1202  }
1203 */
1204 
1205  }
1206 
1207 
1208  // part3: all coeffs = all coeffs / cand
1209  if (!lc_is_pos)
1210  cand = p_Neg(cand, R);
1211 
1212  c = (number)cand; naTest(c);
1213 
1214  poly cInverse = (poly)naInvers(c, cf);
1215  assume(cInverse != NULL); // c is non-zero divisor!?
1216 
1217 
1218  numberCollectionEnumerator.Reset();
1219 
1220 
1221  while (numberCollectionEnumerator.MoveNext() )
1222  {
1223  number& n = numberCollectionEnumerator.Current();
1224 
1225  assume( length > 0 );
1226 
1227  if( --length > 0 )
1228  {
1229  assume( cInverse != NULL );
1230  n = (number) p_Mult_q(p_Copy(cInverse, R), (poly)n, R);
1231  }
1232  else
1233  {
1234  n = (number) p_Mult_q(cInverse, (poly)n, R);
1235  cInverse = NULL;
1236  assume(length == 0);
1237  }
1238 
1239  definiteReduce((poly &)n, naMinpoly, cf);
1240  }
1241 
1242  assume(length == 0);
1243  assume(cInverse == NULL); // p_Delete(&cInverse, R);
1244 
1245  // Quick and dirty fix for constant content clearing... !?
1246  CRecursivePolyCoeffsEnumerator<NAConverter> itr(numberCollectionEnumerator); // recursively treat the numbers as polys!
1247 
1248  number cc;
1249 
1250  n_ClearContent(itr, cc, Q); // TODO: get rid of (-LC) normalization!?
1251 
1252  // over alg. ext. of Q // takes over the input number
1253  c = (number) __p_Mult_nn( (poly)c, cc, R);
1254 // p_Mult_q(p_NSet(cc, R), , R);
1255 
1256  n_Delete(&cc, Q);
1257 
1258  // TODO: the above is not enough! need GCD's of polynomial coeffs...!
1259 /*
1260  // old and wrong part of p_Content
1261  if (rField_is_Q_a(r) && !CLEARENUMERATORS) // should not be used anymore if CLEARENUMERATORS is 1
1262  {
1263  // we only need special handling for alg. ext.
1264  if (getCoeffType(r->cf)==n_algExt)
1265  {
1266  number hzz = n_Init(1, r->cf->extRing->cf);
1267  p=ph;
1268  while (p!=NULL)
1269  { // each monom: coeff in Q_a
1270  poly c_n_n=(poly)pGetCoeff(p);
1271  poly c_n=c_n_n;
1272  while (c_n!=NULL)
1273  { // each monom: coeff in Q
1274  d=n_NormalizeHelper(hzz,pGetCoeff(c_n),r->cf->extRing->cf);
1275  n_Delete(&hzz,r->cf->extRing->cf);
1276  hzz=d;
1277  pIter(c_n);
1278  }
1279  pIter(p);
1280  }
1281  // hzz contains the 1/lcm of all denominators in c_n_n
1282  h=n_Invers(hzz,r->cf->extRing->cf);
1283  n_Delete(&hzz,r->cf->extRing->cf);
1284  n_Normalize(h,r->cf->extRing->cf);
1285  if(!n_IsOne(h,r->cf->extRing->cf))
1286  {
1287  p=ph;
1288  while (p!=NULL)
1289  { // each monom: coeff in Q_a
1290  poly c_n=(poly)pGetCoeff(p);
1291  while (c_n!=NULL)
1292  { // each monom: coeff in Q
1293  d=n_Mult(h,pGetCoeff(c_n),r->cf->extRing->cf);
1294  n_Normalize(d,r->cf->extRing->cf);
1295  n_Delete(&pGetCoeff(c_n),r->cf->extRing->cf);
1296  pGetCoeff(c_n)=d;
1297  pIter(c_n);
1298  }
1299  pIter(p);
1300  }
1301  }
1302  n_Delete(&h,r->cf->extRing->cf);
1303  }
1304  }
1305 */
1306 
1307 
1308 // c = n_Init(1, cf); assume(FALSE); // TODO: NOT YET IMPLEMENTED!!!
1309 }
1310 
1311 
1312 void naClearDenominators(ICoeffsEnumerator& numberCollectionEnumerator, number& c, const coeffs cf)
1313 {
1314  assume(cf != NULL);
1316  assume(nCoeff_is_Q_algext(cf)); // only over (Q[a]/m(a)), while the default impl. is used over Zp[a]/m(a) !
1317 
1318  assume(cf->extRing != NULL);
1319  const coeffs Q = cf->extRing->cf;
1320  assume(Q != NULL);
1321  assume(nCoeff_is_Q(Q));
1322  number n;
1323  CRecursivePolyCoeffsEnumerator<NAConverter> itr(numberCollectionEnumerator); // recursively treat the numbers as polys!
1324  n_ClearDenominators(itr, n, Q); // this should probably be fine...
1325  c = (number)p_NSet(n, cf->extRing); // over alg. ext. of Q // takes over the input number
1326 }
1327 
1329 {
1330  rDecRefCnt(cf->extRing);
1331  if(cf->extRing->ref<0)
1332  rDelete(cf->extRing);
1333 }
1334 
1335 char* naCoeffName(const coeffs r) // currently also for tranext.
1336 {
1337  const char* const* p=n_ParameterNames(r);
1338  int l=0;
1339  int i;
1340  for(i=0; i<n_NumberOfParameters(r);i++)
1341  {
1342  l+=(strlen(p[i])+1);
1343  }
1344  STATIC_VAR char s[200];
1345  s[0]='\0';
1346  snprintf(s,10+1,"%d",r->ch); /* Fp(a) or Q(a) */
1347  char tt[2];
1348  tt[0]=',';
1349  tt[1]='\0';
1350  for(i=0; i<n_NumberOfParameters(r);i++)
1351  {
1352  strcat(s,tt);
1353  strcat(s,p[i]);
1354  }
1355  return s;
1356 }
1357 
1358 number naChineseRemainder(number *x, number *q,int rl, BOOLEAN /*sym*/,CFArray &inv_cache,const coeffs cf)
1359 {
1360  poly *P=(poly*)omAlloc(rl*sizeof(poly*));
1361  number *X=(number *)omAlloc(rl*sizeof(number));
1362  int i;
1363  for(i=0;i<rl;i++) P[i]=p_Copy((poly)(x[i]),cf->extRing);
1364  poly result=p_ChineseRemainder(P,X,q,rl,inv_cache,cf->extRing);
1365  omFreeSize(X,rl*sizeof(number));
1366  omFreeSize(P,rl*sizeof(poly*));
1367  return ((number)result);
1368 }
1369 
1370 number naFarey(number p, number n, const coeffs cf)
1371 {
1372  // n is really a bigint
1373  poly result=p_Farey(p_Copy((poly)p,cf->extRing),n,cf->extRing);
1374  return ((number)result);
1375 }
1376 
1377 
1378 BOOLEAN naInitChar(coeffs cf, void * infoStruct)
1379 {
1380  assume( infoStruct != NULL );
1381 
1382  AlgExtInfo *e = (AlgExtInfo *)infoStruct;
1383  /// first check whether cf->extRing != NULL and delete old ring???
1384 
1385  assume(e->r != NULL); // extRing;
1386  assume(e->r->cf != NULL); // extRing->cf;
1387 
1388  assume((e->r->qideal != NULL) && // minideal has one
1389  (IDELEMS(e->r->qideal) == 1) && // non-zero generator
1390  (e->r->qideal->m[0] != NULL) ); // at m[0];
1391 
1392  assume( cf != NULL );
1393  assume(getCoeffType(cf) == n_algExt); // coeff type;
1394 
1395  rIncRefCnt(e->r); // increase the ref.counter for the ground poly. ring!
1396  const ring R = e->r; // no copy!
1397  cf->extRing = R;
1398 
1399  /* propagate characteristic up so that it becomes
1400  directly accessible in cf: */
1401  cf->ch = R->cf->ch;
1402 
1403  cf->is_field=TRUE;
1404  cf->is_domain=TRUE;
1405  cf->rep=n_rep_poly;
1406 
1407  #ifdef LDEBUG
1408  p_Test((poly)naMinpoly, naRing);
1409  #endif
1410 
1411  cf->cfCoeffName = naCoeffName;
1412 
1413  cf->cfGreaterZero = naGreaterZero;
1414  cf->cfGreater = naGreater;
1415  cf->cfEqual = naEqual;
1416  cf->cfIsZero = naIsZero;
1417  cf->cfIsOne = naIsOne;
1418  cf->cfIsMOne = naIsMOne;
1419  cf->cfInit = naInit;
1420  cf->cfInitMPZ = naInitMPZ;
1421  cf->cfFarey = naFarey;
1422  cf->cfChineseRemainder= naChineseRemainder;
1423  cf->cfInt = naInt;
1424  cf->cfInpNeg = naNeg;
1425  cf->cfAdd = naAdd;
1426  cf->cfSub = naSub;
1427  cf->cfMult = naMult;
1428  cf->cfDiv = naDiv;
1429  cf->cfExactDiv = naDiv;
1430  cf->cfPower = naPower;
1431  cf->cfCopy = naCopy;
1432 
1433  cf->cfWriteLong = naWriteLong;
1434 
1435  if( rCanShortOut(naRing) )
1436  cf->cfWriteShort = naWriteShort;
1437  else
1438  cf->cfWriteShort = naWriteLong;
1439 
1440  cf->cfRead = naRead;
1441  cf->cfDelete = naDelete;
1442  cf->cfSetMap = naSetMap;
1443  cf->cfGetDenom = naGetDenom;
1444  cf->cfGetNumerator = naGetNumerator;
1445  cf->cfRePart = naCopy;
1446  cf->cfCoeffWrite = naCoeffWrite;
1447  cf->cfNormalize = naNormalize;
1448  cf->cfKillChar = naKillChar;
1449 #ifdef LDEBUG
1450  cf->cfDBTest = naDBTest;
1451 #endif
1452  cf->cfGcd = naGcd;
1453  cf->cfNormalizeHelper = naLcmContent;
1454  cf->cfSize = naSize;
1455  cf->nCoeffIsEqual = naCoeffIsEqual;
1456  cf->cfInvers = naInvers;
1457  cf->convFactoryNSingN=naConvFactoryNSingN;
1458  cf->convSingNFactoryN=naConvSingNFactoryN;
1459  cf->cfParDeg = naParDeg;
1460 
1461  cf->iNumberOfParameters = rVar(R);
1462  cf->pParameterNames = (const char**)R->names;
1463  cf->cfParameter = naParameter;
1464  cf->has_simple_Inverse= R->cf->has_simple_Inverse;
1465  /* cf->has_simple_Alloc= FALSE; */
1466 
1467  if( nCoeff_is_Q(R->cf) )
1468  {
1469  cf->cfClearContent = naClearContent;
1470  cf->cfClearDenominators = naClearDenominators;
1471  }
1472 
1473  return FALSE;
1474 }
1475 
1477 
1478 template class IAccessor<snumber*>;
1479 
1480 /* --------------------------------------------------------------------*/
1481 /****************************************
1482 * Computer Algebra System SINGULAR *
1483 ****************************************/
1484 /**
1485  * ABSTRACT: numbers as polys in the ring K[a]
1486  * Assuming that we have a coeffs object cf, then these numbers
1487  * are polynomials in the polynomial ring K[a] represented by
1488  * cf->extRing.
1489  * IMPORTANT ASSUMPTIONS:
1490  * 1.) So far we assume that cf->extRing is a valid polynomial
1491  * ring
1492  **/
1493 
1494 #ifdef LDEBUG
1495 #define n2pTest(a) n2pDBTest(a,__FILE__,__LINE__,cf)
1496 BOOLEAN n2pDBTest(number a, const char *f, const int l, const coeffs r);
1497 #else
1498 #define n2pTest(a) do {} while (0)
1499 #endif
1500 
1501 /* polynomial ring in which our numbers live */
1502 #define n2pRing cf->extRing
1503 
1504 /* coeffs object in which the coefficients of our numbers live;
1505  * methods attached to n2pCoeffs may be used to compute with the
1506  * coefficients of our numbers, e.g., use n2pCoeffs->nAdd to add
1507  * coefficients of our numbers */
1508 #define n2pCoeffs cf->extRing->cf
1509 
1510 #ifdef LDEBUG
1511 BOOLEAN n2pDBTest(number a, const char */*f*/, const int /*l*/, const coeffs cf)
1512 {
1513  if (a == NULL) return TRUE;
1514  return p_Test((poly)a, n2pRing);
1515 }
1516 #endif
1517 
1518 void n2pNormalize(number &a, const coeffs cf)
1519 {
1520  poly aa=(poly)a;
1521  p_Normalize(aa,n2pRing);
1522 }
1523 
1524 /* TRUE iff (a != 0 and (b == 0 or deg(a) > deg(b) or (deg(a)==deg(b) && lc(a)>lc(b))) */
1525 number n2pMult(number a, number b, const coeffs cf)
1526 {
1527  n2pTest(a); n2pTest(b);
1528  if ((a == NULL)||(b == NULL)) return NULL;
1529  poly aTimesB = pp_Mult_qq((poly)a, (poly)b, n2pRing);
1530  return (number)aTimesB;
1531 }
1532 
1533 number n2pDiv(number a, number b, const coeffs cf)
1534 {
1535  n2pTest(a); n2pTest(b);
1536  if (b == NULL) WerrorS(nDivBy0);
1537  if (a == NULL) return NULL;
1538  poly p=singclap_pdivide((poly)a,(poly)b,n2pRing);
1539  return (number)p;
1540 }
1541 
1542 void n2pPower(number a, int exp, number *b, const coeffs cf)
1543 {
1544  n2pTest(a);
1545 
1546  *b= (number)p_Power((poly)a,exp,n2pRing);
1547 }
1548 
1549 const char * n2pRead(const char *s, number *a, const coeffs cf)
1550 {
1551  poly aAsPoly;
1552  const char * result = p_Read(s, aAsPoly, n2pRing);
1553  *a = (number)aAsPoly;
1554  return result;
1555 }
1556 
1557 /* expects *param to be castable to AlgExtInfo */
1558 static BOOLEAN n2pCoeffIsEqual(const coeffs cf, n_coeffType n, void * param)
1559 {
1560  if (n_polyExt != n) return FALSE;
1561  AlgExtInfo *e = (AlgExtInfo *)param;
1562  /* for extension coefficient fields we expect the underlying
1563  polynomial rings to be IDENTICAL, i.e. the SAME OBJECT;
1564  this expectation is based on the assumption that we have properly
1565  registered cf and perform reference counting rather than creating
1566  multiple copies of the same coefficient field/domain/ring */
1567  if (n2pRing == e->r)
1568  return TRUE;
1569  // NOTE: Q(a)[x] && Q(a)[y] should better share the _same_ Q(a)...
1570  if( rEqual(n2pRing, e->r, TRUE) ) // also checks the equality of qideals
1571  {
1572  rDelete(e->r);
1573  return TRUE;
1574  }
1575  return FALSE;
1576 }
1577 
1578 char* n2pCoeffName(const coeffs cf)
1579 {
1580  const char* const* p=n_ParameterNames(cf);
1581  int l=0;
1582  int i;
1583  for(i=0; i<rVar(n2pRing);i++)
1584  {
1585  l+=(strlen(p[i])+1);
1586  }
1587  char *cf_s=nCoeffName(n2pRing->cf);
1588  STATIC_VAR char s[200];
1589  s[0]='\0';
1590  snprintf(s,strlen(cf_s)+2,"%s",cf_s);
1591  char tt[2];
1592  tt[0]='[';
1593  tt[1]='\0';
1594  strcat(s,tt);
1595  tt[0]=',';
1596  for(i=0; i<rVar(n2pRing);i++)
1597  {
1598  strcat(s,p[i]);
1599  if (i+1!=rVar(n2pRing)) strcat(s,tt);
1600  else { tt[0]=']'; strcat(s,tt); }
1601  }
1602  return s;
1603 }
1604 
1605 void n2pCoeffWrite(const coeffs cf, BOOLEAN details)
1606 {
1607  assume( cf != NULL );
1608 
1609  const ring A = cf->extRing;
1610 
1611  assume( A != NULL );
1612  PrintS("// polynomial ring as coefficient ring :\n");
1613  rWrite(A);
1614  PrintLn();
1615 }
1616 
1617 number n2pInvers(number a, const coeffs cf)
1618 {
1619  poly aa=(poly)a;
1620  if(p_IsConstant(aa, n2pRing))
1621  {
1622  poly p=p_Init(n2pRing);
1624  return (number)p;
1625  }
1626  else
1627  {
1628  WerrorS("not invertible");
1629  return NULL;
1630  }
1631 }
1632 
1633 BOOLEAN n2pInitChar(coeffs cf, void * infoStruct)
1634 {
1635  assume( infoStruct != NULL );
1636 
1637  AlgExtInfo *e = (AlgExtInfo *)infoStruct;
1638  /// first check whether cf->extRing != NULL and delete old ring???
1639 
1640  assume(e->r != NULL); // extRing;
1641  assume(e->r->cf != NULL); // extRing->cf;
1642 
1643  assume( cf != NULL );
1644 
1645  rIncRefCnt(e->r); // increase the ref.counter for the ground poly. ring!
1646  const ring R = e->r; // no copy!
1647  cf->extRing = R;
1648 
1649  /* propagate characteristic up so that it becomes
1650  directly accessible in cf: */
1651  cf->ch = R->cf->ch;
1652  cf->is_field=FALSE;
1653  cf->is_domain=TRUE;
1654 
1655  cf->cfCoeffName = n2pCoeffName;
1656 
1657  cf->cfGreaterZero = naGreaterZero;
1658  cf->cfGreater = naGreater;
1659  cf->cfEqual = naEqual;
1660  cf->cfIsZero = naIsZero;
1661  cf->cfIsOne = naIsOne;
1662  cf->cfIsMOne = naIsMOne;
1663  cf->cfInit = naInit;
1664  cf->cfInitMPZ = naInitMPZ;
1665  cf->cfFarey = naFarey;
1666  cf->cfChineseRemainder= naChineseRemainder;
1667  cf->cfInt = naInt;
1668  cf->cfInpNeg = naNeg;
1669  cf->cfAdd = naAdd;
1670  cf->cfSub = naSub;
1671  cf->cfMult = n2pMult;
1672  cf->cfDiv = n2pDiv;
1673  cf->cfPower = n2pPower;
1674  cf->cfCopy = naCopy;
1675 
1676  cf->cfWriteLong = naWriteLong;
1677 
1678  if( rCanShortOut(n2pRing) )
1679  cf->cfWriteShort = naWriteShort;
1680  else
1681  cf->cfWriteShort = naWriteLong;
1682 
1683  cf->cfRead = n2pRead;
1684  cf->cfDelete = naDelete;
1685  cf->cfSetMap = naSetMap;
1686  cf->cfGetDenom = naGetDenom;
1687  cf->cfGetNumerator = naGetNumerator;
1688  cf->cfRePart = naCopy;
1689  cf->cfCoeffWrite = n2pCoeffWrite;
1690  cf->cfNormalize = n2pNormalize;
1691  cf->cfKillChar = naKillChar;
1692 #ifdef LDEBUG
1693  cf->cfDBTest = naDBTest;
1694 #endif
1695  cf->cfGcd = naGcd;
1696  cf->cfNormalizeHelper = naLcmContent;
1697  cf->cfSize = naSize;
1698  cf->nCoeffIsEqual = n2pCoeffIsEqual;
1699  cf->cfInvers = n2pInvers;
1700  cf->convFactoryNSingN=naConvFactoryNSingN;
1701  cf->convSingNFactoryN=naConvSingNFactoryN;
1702  cf->cfParDeg = naParDeg;
1703 
1704  cf->iNumberOfParameters = rVar(R);
1705  cf->pParameterNames = (const char**)R->names;
1706  cf->cfParameter = naParameter;
1707  cf->has_simple_Inverse=FALSE;
1708  /* cf->has_simple_Alloc= FALSE; */
1709 
1710  if( nCoeff_is_Q(R->cf) )
1711  {
1712  cf->cfClearContent = naClearContent;
1713  cf->cfClearDenominators = naClearDenominators;
1714  }
1715 
1716  return FALSE;
1717 }
Rational pow(const Rational &a, int e)
Definition: GMPrat.cc:411
Concrete implementation of enumerators over polynomials.
number n2pDiv(number a, number b, const coeffs cf)
Definition: algext.cc:1533
BOOLEAN naGreater(number a, number b, const coeffs cf)
Definition: algext.cc:363
void heuristicReduce(poly &p, poly reducer, const coeffs cf)
Definition: algext.cc:565
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
number naNeg(number a, const coeffs cf)
this is in-place, modifies a
Definition: algext.cc:331
number n2pMult(number a, number b, const coeffs cf)
Definition: algext.cc:1525
long naInt(number &a, const coeffs cf)
Definition: algext.cc:350
number naMap00(number a, const coeffs src, const coeffs dst)
Definition: algext.cc:853
number naCopy(number a, const coeffs cf)
Definition: algext.cc:296
#define naMinpoly
Definition: algext.cc:70
BOOLEAN naIsOne(number a, const coeffs cf)
Definition: algext.cc:314
CanonicalForm naConvSingNFactoryN(number n, BOOLEAN, const coeffs cf)
Definition: algext.cc:761
number naGcd(number a, number b, const coeffs cf)
Definition: algext.cc:775
void naClearDenominators(ICoeffsEnumerator &numberCollectionEnumerator, number &c, const coeffs cf)
Definition: algext.cc:1312
BOOLEAN naDBTest(number a, const char *f, const int l, const coeffs r)
Definition: algext.cc:233
number naInit(long i, const coeffs cf)
Definition: algext.cc:338
BOOLEAN naIsZero(number a, const coeffs cf)
Definition: algext.cc:272
const char * n2pRead(const char *s, number *a, const coeffs cf)
Definition: algext.cc:1549
number naGetNumerator(number &a, const coeffs cf)
Definition: algext.cc:303
static void naClearContent(ICoeffsEnumerator &numberCollectionEnumerator, number &c, const coeffs cf)
Definition: algext.cc:1107
number naGenMap(number a, const coeffs cf, const coeffs dst)
Definition: algext.cc:977
number naSub(number a, number b, const coeffs cf)
Definition: algext.cc:453
number naCopyTrans2AlgExt(number a, const coeffs src, const coeffs dst)
Definition: algext.cc:895
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
BOOLEAN naEqual(number a, number b, const coeffs cf)
Definition: algext.cc:287
void naNormalize(number &a, const coeffs cf)
Definition: algext.cc:747
void naWriteShort(number a, const coeffs cf)
Definition: algext.cc:593
number napNormalizeHelper(number b, const coeffs cf)
Definition: algext.cc:634
void naPower(number a, int exp, number *b, const coeffs cf)
Definition: algext.cc:498
number naChineseRemainder(number *x, number *q, int rl, BOOLEAN, CFArray &inv_cache, const coeffs cf)
Definition: algext.cc:1358
BOOLEAN n2pDBTest(number a, const char *f, const int l, const coeffs r)
Definition: algext.cc:1511
#define n2pRing
Definition: algext.cc:1502
void naKillChar(coeffs cf)
Definition: algext.cc:1328
number naMap0P(number a, const coeffs src, const coeffs dst)
Definition: algext.cc:943
number naInvers(number a, const coeffs cf)
Definition: algext.cc:823
void naWriteLong(number a, const coeffs cf)
Definition: algext.cc:575
void naDelete(number *a, const coeffs cf)
Definition: algext.cc:278
void naCoeffWrite(const coeffs cf, BOOLEAN details)
Definition: algext.cc:392
#define n2pCoeffs
Definition: algext.cc:1508
number naDiv(number a, number b, const coeffs cf)
Definition: algext.cc:474
number naGenTrans2AlgExt(number a, const coeffs cf, const coeffs dst)
Definition: algext.cc:992
number naLcmContent(number a, number b, const coeffs cf)
Definition: algext.cc:648
char * naCoeffName(const coeffs r)
Definition: algext.cc:1335
number naMult(number a, number b, const coeffs cf)
Definition: algext.cc:464
static number naInitMPZ(mpz_t m, const coeffs r)
Definition: algext.cc:344
const char * naRead(const char *s, number *a, const coeffs cf)
Definition: algext.cc:611
number naGetDenom(number &a, const coeffs cf)
Definition: algext.cc:308
static BOOLEAN n2pCoeffIsEqual(const coeffs cf, n_coeffType n, void *param)
Definition: algext.cc:1558
char * n2pCoeffName(const coeffs cf)
Definition: algext.cc:1578
void definiteReduce(poly &p, poly reducer, const coeffs cf)
Definition: algext.cc:735
number naConvFactoryNSingN(const CanonicalForm n, const coeffs cf)
Definition: algext.cc:755
#define naCoeffs
Definition: algext.cc:67
static BOOLEAN naCoeffIsEqual(const coeffs cf, n_coeffType n, void *param)
Definition: algext.cc:683
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:1022
static poly p_ExtGcdHelper(poly &p, poly &pFactor, poly &q, poly &qFactor, ring r)
Definition: algext.cc:183
#define naRing
Definition: algext.cc:61
BOOLEAN naInitChar(coeffs cf, void *infoStruct)
Initialize the coeffs object.
Definition: algext.cc:1378
#define naTest(a)
Definition: algext.cc:54
number naMapPP(number a, const coeffs src, const coeffs dst)
Definition: algext.cc:956
BOOLEAN n2pInitChar(coeffs cf, void *infoStruct)
Definition: algext.cc:1633
number n2pInvers(number a, const coeffs cf)
Definition: algext.cc:1617
int naParDeg(number a, const coeffs cf)
Definition: algext.cc:1073
int naIsParam(number m, const coeffs cf)
if m == var(i)/1 => return i,
Definition: algext.cc:1096
number naAdd(number a, number b, const coeffs cf)
Definition: algext.cc:442
int naSize(number a, const coeffs cf)
Definition: algext.cc:717
number naParameter(const int iParameter, const coeffs cf)
return the specified parameter as a number in the given alg. field
Definition: algext.cc:1081
BOOLEAN naGreaterZero(number a, const coeffs cf)
forward declarations
Definition: algext.cc:383
void n2pCoeffWrite(const coeffs cf, BOOLEAN details)
Definition: algext.cc:1605
#define n2pTest(a)
ABSTRACT: numbers as polys in the ring K[a] Assuming that we have a coeffs object cf,...
Definition: algext.cc:1495
void n2pNormalize(number &a, const coeffs cf)
Definition: algext.cc:1518
number naFarey(number p, number n, const coeffs cf)
Definition: algext.cc:1370
number naMapP0(number a, const coeffs src, const coeffs dst)
Definition: algext.cc:875
static coeffs nCoeff_bottom(const coeffs r, int &height)
Definition: algext.cc:258
number naMapZ0(number a, const coeffs src, const coeffs dst)
Definition: algext.cc:863
number naMapUP(number a, const coeffs src, const coeffs dst)
Definition: algext.cc:966
BOOLEAN naIsMOne(number a, const coeffs cf)
Definition: algext.cc:322
void n2pPower(number a, int exp, number *b, const coeffs cf)
Definition: algext.cc:1542
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:255
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:4390
#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:387
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:165
const char *const nDivBy0
Definition: numbers.h:87
#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:4195
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:3879
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:4721
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:4577
static poly p_Neg(poly p, const ring r)
Definition: p_polys.h:1107
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:936
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1114
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:488
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:233
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:412
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:469
static BOOLEAN p_IsConstant(const poly p, const ring r)
Definition: p_polys.h:2011
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:901
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:1151
static poly p_Init(const ring r, omBin bin)
Definition: p_polys.h:1320
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:846
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1507
#define p_Test(p, r)
Definition: p_polys.h:162
#define __p_Mult_nn(p, n, r)
Definition: p_polys.h:971
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