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