transext.cc
Go to the documentation of this file.
1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 /*
5 * ABSTRACT: numbers in a rational function field K(t_1, .., t_s) with
6 * transcendental variables t_1, ..., t_s, where s >= 1.
7 * Denoting the implemented coeffs object by cf, then these numbers
8 * are represented as quotients of polynomials living in the
9 * polynomial ring K[t_1, .., t_s] represented by cf->extring.
10 *
11 * An element of K(t_1, .., t_s) may have numerous representations,
12 * due to the possibility of common polynomial factors in the
13 * numerator and denominator. This problem is handled by a
14 * cancellation heuristic: Each number "knows" its complexity
15 * which is 0 if and only if common factors have definitely been
16 * cancelled, and some positive integer otherwise.
17 * Each arithmetic operation of two numbers with complexities c1
18 * and c2 will result in a number of complexity c1 + c2 + some
19 * penalty (specific for each arithmetic operation; see constants
20 * in the *.h file). Whenever the resulting complexity exceeds a
21 * certain threshold (see constant in the *.h file), then the
22 * cancellation heuristic will call 'factory' to compute the gcd
23 * and cancel it out in the given number.
24 * For the special case of K = Q (i.e., when computing over the
25 * rationals), this definite cancellation procedure will also take
26 * care of nested fractions: If there are fractional coefficients
27 * in the numerator or denominator of a number, then this number
28 * is being replaced by a quotient of two polynomials over Z, or
29 * - if the denominator is a constant - by a polynomial over Q.
30 *
31 * TODO: the description above needs a major update!!!
32 */
33 #define TRANSEXT_PRIVATES
34 
35 #include <misc/auxiliary.h>
36 
37 #include <omalloc/omalloc.h>
38 #include <factory/factory.h>
39 
40 #include <reporter/reporter.h>
41 
42 #include <coeffs/coeffs.h>
43 #include <coeffs/numbers.h>
44 
45 #include <coeffs/longrat.h>
46 
47 #include <polys/monomials/ring.h>
49 #include <polys/simpleideals.h>
50 
51 #include <polys/clapsing.h>
52 #include <polys/clapconv.h>
53 
54 #include <polys/prCopy.h>
55 #include "transext.h"
56 #include "algext.h"
57 
58 #include <polys/PolyEnumerator.h>
59 
60 
61 /* constants for controlling the complexity of numbers */
62 #define ADD_COMPLEXITY 1 /**< complexity increase due to + and - */
63 #define MULT_COMPLEXITY 2 /**< complexity increase due to * and / */
64 #define DIFF_COMPLEXITY 2 /**< complexity increase due to * and / */
65 #define BOUND_COMPLEXITY 10 /**< maximum complexity of a number */
66 
67 /// TRUE iff num. represents 1
68 #define NUMIS1(f) (p_IsOne(NUM(f), cf->extRing))
69 
70 #define COM(f) (f)->complexity
71 
72 
73 #ifdef LDEBUG
74 static BOOLEAN ntDBTest(number a, const char *f, const int l, const coeffs r);
75 #endif
76 
77 #define ntTest(a) n_Test(a, cf)
78 
79 /* polynomial ring in which the numerators and denominators of our
80  numbers live */
81 #define ntRing cf->extRing
82 
83 /* coeffs object in which the coefficients of our numbers live;
84  * methods attached to ntCoeffs may be used to compute with the
85  * coefficients of our numbers, e.g., use ntCoeffs->nAdd to add
86  * coefficients of our numbers */
87 #define ntCoeffs cf->extRing->cf
88 
89 
90 omBin fractionObjectBin = omGetSpecBin(sizeof(fractionObject));
91 
92 /// forward declarations
93 static void heuristicGcdCancellation(number a, const coeffs cf);
94 static void definiteGcdCancellation(number a, const coeffs cf,
95  BOOLEAN simpleTestsHaveAlreadyBeenPerformed);
96 
97 /* test routine, usualy disabled *
98  * if want to activate it, activate also the calls to check_N *
99  *
100 void check_normalized(number t,const coeffs cf, const char *f, int l)
101 {
102  if (IS0(t)) return;
103  if(rField_is_Q(ntRing))
104  {
105  poly pp=NUM(t);
106  while(pp!=NULL)
107  {
108  if (((SR_HDL(pGetCoeff(pp)) & SR_INT)==0)&&(SR_HDL(pGetCoeff(pp))!=NULL))
109  {
110  if (pGetCoeff(pp)->s==0)
111  {
112  Print("NUM not normalized in %s:%d\n",f,l);
113  p_Normalize(pp,ntRing);
114  }
115  else if (pGetCoeff(pp)->s==1)
116  Print("NUM is rational in %s:%d\n",f,l);
117  }
118  pIter(pp);
119  }
120  pp=DEN(t);
121  while(pp!=NULL)
122  {
123  if (((SR_HDL(pGetCoeff(pp)) & SR_INT)==0)&&(SR_HDL(pGetCoeff(pp))!=NULL))
124  {
125  if (pGetCoeff(pp)->s==0)
126  {
127  Print("NUM not normalized in %s:%d\n",f,l);
128  p_Normalize(pp,ntRing);
129  }
130  else if (pGetCoeff(pp)->s==1)
131  Print("DEN is rational in %s:%d\n",f,l);
132  }
133  pIter(pp);
134  }
135  }
136 }
137 #define check_N(A,B) check_normalized(A,B,__FILE__,__LINE__)
138 */
139 
140 #ifdef LDEBUG
141 static BOOLEAN ntDBTest(number a, const char *f, const int l, const coeffs cf)
142 {
144 
145  if (IS0(a)) return TRUE;
146 
147  const fraction t = (fraction)a;
148 
149  //check_N(a,cf);
150  const poly num = NUM(t);
151  assume(num != NULL); ///< t != 0 ==> numerator(t) != 0
152 
153  p_Test(num, ntRing);
154 
155  if (getCoeffType(ntCoeffs)==n_Q)
156  for( poly p = num; p != NULL; pIter(p) )
157  if (! nlIsInteger( p_GetCoeff(p, ntRing), ntCoeffs) )
158  {
159  Print("ERROR in %s:%d: non-integer Q coeff in num. poly\n",f,l);
160  Print("TERM: "); p_wrp(p, ntRing); PrintLn();
161  return FALSE;
162  }
163 
164  const poly den = DEN(t);
165 
166  if (den != NULL) // !DENIS1(f)
167  {
168  p_Test(den, ntRing);
169 
170  if (getCoeffType(ntCoeffs)==n_Q)
171  for( poly p = den; p != NULL; pIter(p) )
172  if (! nlIsInteger( p_GetCoeff(p, ntRing), ntCoeffs) )
173  {
174  Print("ERROR in %s:%d: non-integer Q coeff in den. poly\n",f,l);
175  Print("TERM: "); p_wrp(p, ntRing); PrintLn();
176  return FALSE;
177  }
178 
179  if (getCoeffType(ntCoeffs)==n_Zp)
180  {
181  if( p_IsConstant(den, ntRing) )
182  {
183  Print("ERROR in %s:%d: constant den. poly / Zp\n",f,l);
184  PrintS("NUM: "); p_Write(num, ntRing);
185  PrintS("DEN: "); p_Write(den, ntRing);
186  return FALSE;
187  }
188 
189  if( !n_IsOne(pGetCoeff(den), ntCoeffs) )
190  {
191  Print("ERROR in %s:%d: non-monic den. poly / Zp\n",f,l);
192  PrintS("NUM: "); p_Write(num, ntRing);
193  PrintS("DEN: "); p_Write(den, ntRing);
194  return FALSE;
195  }
196  }
197 
198  if (COM(t)==0)
199  {
200  poly gcd = singclap_gcd_r( num, den, ntRing );
201  if(gcd!=NULL)
202  {
203  if((gcd!=NULL) && !p_IsOne(gcd, ntRing) )
204  {
205  Print("ERROR in %s:%d: 1 != GCD between num. & den. poly\n",f,l);
206  PrintS("GCD: "); p_Write(gcd, ntRing);
207  PrintS("NUM: "); p_Write(num, ntRing);
208  PrintS("DEN: "); p_Write(den, ntRing);
209  return FALSE;
210  }
211  p_Delete( &gcd, ntRing );
212  }
213  }
214  return TRUE;
215 
216  if(p_IsConstant(den, ntRing) && (n_IsOne(pGetCoeff(den), ntCoeffs)))
217  {
218  Print("?/1 in %s:%d\n",f,l);
219  return FALSE;
220  }
221  if( !n_GreaterZero(pGetCoeff(den), ntCoeffs) )
222  {
223  Print("negative sign of DEN. of a fraction in %s:%d\n",f,l);
224  return FALSE;
225  }
226  // test that den is over integers!?
227  }
228  else
229  {
230  return TRUE;
231 
232  // num != NULL // den == NULL
233 // if( COM(t) != 0 )
234 // {
235 // Print("?//NULL with non-zero complexity: %d in %s:%d\n", COM(t), f, l);
236 // return FALSE;
237 // }
238  // test that nume is over integers!?
239  }
240  if (getCoeffType(ntCoeffs)==n_Q)
241  {
242  poly p=num; // !=NULL
243  do
244  {
245  number n=pGetCoeff(p);
246  n_Test(n,ntCoeffs);
247  if ((!(SR_HDL(n) & SR_INT))&&(n->s==0))
248  /* not normalized, just do for the following test*/
249  {
251  n=pGetCoeff(p);
252  }
253  if (!(SR_HDL(n) & SR_INT))
254  {
255  if (n->s<2)
256  Print("rational coeff in num: %s:%d\n",f,l);
257  }
258  pIter(p);
259  } while(p!=NULL);
260  p=den;
261  while(p!=NULL)
262  {
263  number n=pGetCoeff(p);
264  if (!(SR_HDL(n) & SR_INT))
265  {
266  if (n->s!=3)
267  Print("rational coeff in den.:%s:%d\n",f,l);
268  }
269  pIter(p);
270  }
271  }
272  return TRUE;
273 }
274 #endif
275 
276 /* returns the bottom field in this field extension tower; if the tower
277  is flat, i.e., if there is no extension, then r itself is returned;
278  as a side-effect, the counter 'height' is filled with the height of
279  the extension tower (in case the tower is flat, 'height' is zero) */
280 static coeffs nCoeff_bottom(const coeffs r, int &height)
281 {
282  assume(r != NULL);
283  coeffs cf = r;
284  height = 0;
285  while (nCoeff_is_Extension(cf))
286  {
287  assume(cf->extRing != NULL); assume(cf->extRing->cf != NULL);
288  cf = cf->extRing->cf;
289  height++;
290  }
291  return cf;
292 }
293 
294 static BOOLEAN ntIsZero(number a, const coeffs cf)
295 {
296  //check_N(a,cf);
297  ntTest(a); // !!!
298  return (IS0(a));
299 }
300 
301 static void ntDelete(number * a, const coeffs cf)
302 {
303  //check_N(*a,cf);
304  ntTest(*a); // !!!
305 
306  fraction f = (fraction)(*a);
307  if (IS0(f)) return;
308  p_Delete(&NUM(f), ntRing);
309  if (!DENIS1(f)) p_Delete(&DEN(f), ntRing);
311  *a = NULL;
312 }
313 
314 static BOOLEAN ntEqual(number a, number b, const coeffs cf)
315 {
316  //check_N(a,cf);
317  //check_N(b,cf);
318  ntTest(a);
319  ntTest(b);
320 
321  /// simple tests
322  if (a == b) return TRUE;
323  if ((IS0(a)) && (!IS0(b))) return FALSE;
324  if ((IS0(b)) && (!IS0(a))) return FALSE;
325 
326  /// cheap test if gcd's have been cancelled in both numbers
327  fraction fa = (fraction)a;
328  fraction fb = (fraction)b;
329  if ((COM(fa) == 1) && (COM(fb) == 1))
330  {
331  poly f = p_Add_q(p_Copy(NUM(fa), ntRing),
332  p_Neg(p_Copy(NUM(fb), ntRing), ntRing),
333  ntRing);
334  if (f != NULL) { p_Delete(&f, ntRing); return FALSE; }
335  if (DENIS1(fa) && DENIS1(fb)) return TRUE;
336  if (DENIS1(fa) && !DENIS1(fb)) return FALSE;
337  if (!DENIS1(fa) && DENIS1(fb)) return FALSE;
338  f = p_Add_q(p_Copy(DEN(fa), ntRing),
339  p_Neg(p_Copy(DEN(fb), ntRing), ntRing),
340  ntRing);
341  if (f != NULL) { p_Delete(&f, ntRing); return FALSE; }
342  return TRUE;
343  }
344 
345  /* default: the more expensive multiplication test
346  a/b = c/d <==> a*d = b*c */
347  poly f = p_Copy(NUM(fa), ntRing);
348  if (!DENIS1(fb)) f = p_Mult_q(f, p_Copy(DEN(fb), ntRing), ntRing);
349  poly g = p_Copy(NUM(fb), ntRing);
350  if (!DENIS1(fa)) g = p_Mult_q(g, p_Copy(DEN(fa), ntRing), ntRing);
351  poly h = p_Add_q(f, p_Neg(g, ntRing), ntRing);
352  if (h == NULL) return TRUE;
353  else
354  {
355  p_Delete(&h, ntRing);
356  return FALSE;
357  }
358 }
359 
360 static number ntCopy(number a, const coeffs cf)
361 {
362  //check_N(a,cf);
363  ntTest(a); // !!!
364  if (IS0(a)) return NULL;
365  fraction f = (fraction)a;
366  poly g = NUM(f);
367  poly h = NULL;
368  h =DEN(f);
369  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
370  NUM(result) = p_Copy(g,cf->extRing);
371  DEN(result) = p_Copy(h,cf->extRing);
372  COM(result) = COM(f);
373  ntTest((number)result);
374  return (number)result;
375 }
376 
377 /* assumes that cf represents the rationals, i.e. Q, and will only
378  be called in that case;
379  assumes furthermore that f != NULL and that the denominator of f != 1;
380  generally speaking, this method removes denominators in the rational
381  coefficients of the numerator and denominator of 'a';
382  more concretely, the following normalizations will be performed,
383  where t^alpha denotes a monomial in the transcendental variables t_k
384  (1) if 'a' is of the form
385  (sum_alpha a_alpha/b_alpha * t^alpha)
386  -------------------------------------
387  (sum_beta c_beta/d_beta * t^beta)
388  with integers a_alpha, b_alpha, c_beta, d_beta, then both the
389  numerator and the denominator will be multiplied by the LCM of
390  the b_alpha's and the d_beta's (if this LCM is != 1),
391  (2) if 'a' is - e.g. after having performed step (1) - of the form
392  (sum_alpha a_alpha * t^alpha)
393  -----------------------------
394  (sum_beta c_beta * t^beta)
395  with integers a_alpha, c_beta, and with a non-constant denominator,
396  then both the numerator and the denominator will be divided by the
397  GCD of the a_alpha's and the c_beta's (if this GCD is != 1),
398  this procedure does not alter COM(f) (this has to be done by the
399  calling procedure);
400  modifies f */
401 static void handleNestedFractionsOverQ(fraction f, const coeffs cf)
402 {
404  assume(!IS0(f));
405  assume(!DENIS1(f));
406 
407  { /* step (1); see documentation of this procedure above */
408  number lcmOfDenominators = n_Init(1, ntCoeffs);
409  number c; number tmp;
410  poly p = NUM(f);
411  /* careful when using n_NormalizeHelper!!! It computes the lcm of the numerator
412  of the 1st argument and the denominator of the 2nd!!! */
413  while (p != NULL)
414  {
415  c = p_GetCoeff(p, ntRing);
416  tmp = n_NormalizeHelper(lcmOfDenominators, c, ntCoeffs);
417  n_Delete(&lcmOfDenominators, ntCoeffs);
418  lcmOfDenominators = tmp;
419  pIter(p);
420  }
421  p = DEN(f);
422  while (p != NULL)
423  {
424  c = p_GetCoeff(p, ntRing);
425  tmp = n_NormalizeHelper(lcmOfDenominators, c, ntCoeffs);
426  n_Delete(&lcmOfDenominators, ntCoeffs);
427  lcmOfDenominators = tmp;
428  pIter(p);
429  }
430  if (!n_IsOne(lcmOfDenominators, ntCoeffs))
431  { /* multiply NUM(f) and DEN(f) with lcmOfDenominators */
432  NUM(f) = p_Mult_nn(NUM(f), lcmOfDenominators, ntRing);
433  p_Normalize(NUM(f), ntRing);
434  DEN(f) = p_Mult_nn(DEN(f), lcmOfDenominators, ntRing);
435  p_Normalize(DEN(f), ntRing);
436  }
437  n_Delete(&lcmOfDenominators, ntCoeffs);
438  if (DEN(f)!=NULL)
439  { /* step (2); see documentation of this procedure above */
440  p = NUM(f);
441  number gcdOfCoefficients = n_Copy(p_GetCoeff(p, ntRing), ntCoeffs);
442  pIter(p);
443  while ((p != NULL) && (!n_IsOne(gcdOfCoefficients, ntCoeffs)))
444  {
445  c = p_GetCoeff(p, ntRing);
446  tmp = n_Gcd(c, gcdOfCoefficients, ntCoeffs);
447  n_Delete(&gcdOfCoefficients, ntCoeffs);
448  gcdOfCoefficients = tmp;
449  pIter(p);
450  }
451  p = DEN(f);
452  while ((p != NULL) && (!n_IsOne(gcdOfCoefficients, ntCoeffs)))
453  {
454  c = p_GetCoeff(p, ntRing);
455  tmp = n_Gcd(c, gcdOfCoefficients, ntCoeffs);
456  n_Delete(&gcdOfCoefficients, ntCoeffs);
457  gcdOfCoefficients = tmp;
458  pIter(p);
459  }
460  if (!n_IsOne(gcdOfCoefficients, ntCoeffs))
461  { /* divide NUM(f) and DEN(f) by gcdOfCoefficients */
462  number inverseOfGcdOfCoefficients = n_Invers(gcdOfCoefficients,
463  ntCoeffs);
464  NUM(f) = p_Mult_nn(NUM(f), inverseOfGcdOfCoefficients, ntRing);
465  p_Normalize(NUM(f), ntRing);
466  DEN(f) = p_Mult_nn(DEN(f), inverseOfGcdOfCoefficients, ntRing);
467  p_Normalize(DEN(f), ntRing);
468  n_Delete(&inverseOfGcdOfCoefficients, ntCoeffs);
469  }
470  n_Delete(&gcdOfCoefficients, ntCoeffs);
471  }
472  }
473 
474  /* Now, due to the above computations, DEN(f) may have become the
475  1-polynomial which needs to be represented by NULL: */
476  if ((DEN(f) != NULL) &&
477  p_IsConstant(DEN(f), ntRing) &&
478  n_IsOne(p_GetCoeff(DEN(f), ntRing), ntCoeffs))
479  {
480  p_Delete(&DEN(f), ntRing); DEN(f) = NULL;
481  }
482 
483  if( DEN(f) != NULL )
484  if( !n_GreaterZero(pGetCoeff(DEN(f)), ntCoeffs) )
485  {
486  NUM(f) = p_Neg(NUM(f), ntRing);
487  DEN(f) = p_Neg(DEN(f), ntRing);
488  }
489  COM(f)=BOUND_COMPLEXITY+1;
490  ntTest((number)f); // TODO!
491 }
492 
493 /// TODO: normalization of a!?
494 static number ntGetNumerator(number &a, const coeffs cf)
495 {
496  //check_N(a,cf);
497  ntTest(a);
498  if (IS0(a)) return NULL;
499 
501 
502  fraction f = (fraction)a;
503  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
504 
505  const BOOLEAN denis1= DENIS1 (f);
506 
507  if (getCoeffType (ntCoeffs) == n_Q && !denis1)
509 
510  if (getCoeffType (ntCoeffs) == n_Q && denis1)
511  {
512  assume( DEN (f) == NULL );
513 
514  number g;
515  // TODO/NOTE: the following should not be necessary (due to
516  // Hannes!) as NUM (f) should be over Z!!!
517  CPolyCoeffsEnumerator itr(NUM(f));
518 
519 
520  n_ClearDenominators(itr, g, ntCoeffs);
521 
522  if( !n_GreaterZero(g, ntCoeffs) )
523  {
524  NUM (f) = p_Neg(NUM (f), ntRing);
525  g = n_InpNeg(g, ntCoeffs);
526  }
527 
528  // g should be a positive integer now!
530 
531  if( !n_IsOne(g, ntCoeffs) )
532  {
533  DEN (f) = p_NSet(g, ntRing);
534  COM (f) ++;
535  assume( DEN (f) != NULL );
536  }
537  else
538  n_Delete(&g, ntCoeffs);
539 
540  ntTest(a);
541  }
542 
543  // Call ntNormalize instead of above?!?
544 
545  NUM (result) = p_Copy (NUM (f), ntRing); // ???
546  //DEN (result) = NULL; // done by ..Alloc0..
547  //COM (result) = 0; // done by ..Alloc0..
548 
549  ntTest((number)result);
550  //check_N((number)result,cf);
551  return (number)result;
552 }
553 
554 /// TODO: normalization of a!?
555 static number ntGetDenom(number &a, const coeffs cf)
556 {
557  //check_N(a,cf);
558  ntTest(a);
559 
560  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
561  //DEN (result)= NULL; // done by ..Alloc0..
562  //COM (result)= 0; // done by ..Alloc0..
563 
564  if (IS0(a))
565  {
566  NUM (result) = p_One(ntRing);
567  return (number)result;
568  }
569 
571 
572  fraction f = (fraction)a;
573 
574  assume( !IS0(f) );
575 
576  const BOOLEAN denis1 = DENIS1 (f);
577 
578  if( denis1 && (getCoeffType (ntCoeffs) != n_Q) ) // */1 or 0
579  {
580  NUM (result)= p_One(ntRing);
581  ntTest((number)result);
582  return (number)result;
583  }
584 
585  if (!denis1) // */* / Q
586  {
587  assume( DEN (f) != NULL );
588 
589  if (getCoeffType (ntCoeffs) == n_Q)
591 
592  ntTest(a);
593 
594  if( DEN (f) != NULL ) // is it ?? // 1 now???
595  {
596  assume( !p_IsOne(DEN (f), ntRing) );
597 
598  NUM (result) = p_Copy (DEN (f), ntRing);
599  ntTest((number)result);
600  return (number)result;
601  }
602 // NUM (result) = p_One(ntRing); // NOTE: just in order to be sure...
603  }
604 
605  // */1 / Q
607  assume( DEN (f) == NULL );
608 
609  number g;
610 // poly num= p_Copy (NUM (f), ntRing); // ???
611 
612 
613  // TODO/NOTE: the following should not be necessary (due to
614  // Hannes!) as NUM (f) should be over Z!!!
615  CPolyCoeffsEnumerator itr(NUM(f));
616 
617  n_ClearDenominators(itr, g, ntCoeffs); // may return -1 :(((
618 
619  if( !n_GreaterZero(g, ntCoeffs) )
620  {
621 // NUM (f) = p_Neg(NUM (f), ntRing); // Ugly :(((
622 // g = n_InpNeg(g, ntCoeffs);
623  NUM (f) = p_Neg(NUM (f), ntRing); // Ugly :(((
624  g = n_InpNeg(g, ntCoeffs);
625  }
626 
627  // g should be a positive integer now!
629 
630  if( !n_IsOne(g, ntCoeffs) )
631  {
633  assume( !n_IsOne(g, ntCoeffs) );
634 
635  DEN (f) = p_NSet(g, ntRing); // update COM(f)???
636  assume( DEN (f) != NULL );
637  COM (f) ++;
638 
639  NUM (result)= p_Copy (DEN (f), ntRing);
640  }
641  else
642  { // common denom == 1?
643  NUM (result)= p_NSet(g, ntRing); // p_Copy (DEN (f), ntRing);
644 // n_Delete(&g, ntCoeffs);
645  }
646 
647 // if (!p_IsConstant (num, ntRing) && pNext(num) != NULL)
648 // else
649 // g= p_GetAllDenom (num, ntRing);
650 // result= (fraction) ntSetMap (ntCoeffs, cf) (g, ntCoeffs, cf);
651 
652  ntTest((number)result);
653  //check_N((number)result,cf);
654  return (number)result;
655 }
656 
657 static BOOLEAN ntIsOne(number a, const coeffs cf)
658 {
659  //check_N(a,cf);
660  ntTest(a); // !!!
662  fraction f = (fraction)a;
663  return (f!=NULL) && DENIS1(f) && NUMIS1(f);
664 }
665 
666 static BOOLEAN ntIsMOne(number a, const coeffs cf)
667 {
668  //check_N(a,cf);
669  ntTest(a);
671  fraction f = (fraction)a;
672  if ((f==NULL) || (!DENIS1(f))) return FALSE;
673  poly g = NUM(f);
674  if (!p_IsConstant(g, ntRing)) return FALSE;
675  return n_IsMOne(p_GetCoeff(g, ntRing), ntCoeffs);
676 }
677 
678 /// this is in-place, modifies a
679 static number ntNeg(number a, const coeffs cf)
680 {
681  //check_N(a,cf);
682  ntTest(a);
683  if (!IS0(a))
684  {
685  fraction f = (fraction)a;
686  NUM(f) = p_Neg(NUM(f), ntRing);
687  }
688  ntTest(a);
689  return a;
690 }
691 
692 number ntInit(long i, const coeffs cf)
693 {
694  if (i != 0)
695  {
696  poly p=p_ISet(i, ntRing);
697  if (p!=NULL)
698  {
699  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
700  NUM(result) = p;
701  //DEN(result) = NULL; // done by omAlloc0Bin
702  //COM(result) = 0; // done by omAlloc0Bin
703  ntTest((number)result);
704  //check_N((number)result,cf);
705  return (number)result;
706  }
707  }
708  return NULL;
709 }
710 
711 
712 /// takes over p!
713 number ntInit(poly p, const coeffs cf)
714 {
715  if (p == NULL) return NULL;
716 
717  p_Test( p, ntRing);
718  fraction f = (fraction)omAlloc0Bin(fractionObjectBin);
719 
720  if (nCoeff_is_Q(ntCoeffs))
721  {
722  number g;
723  // the following is necessary because
724  // NUM (f) should be over Z,
725  // while p may be over Q
726  CPolyCoeffsEnumerator itr(p);
727 
728  n_ClearDenominators(itr, g, ntCoeffs);
729 
730  if( !n_GreaterZero(g, ntCoeffs) )
731  {
732  p = p_Neg(p, ntRing);
733  g = n_InpNeg(g, ntCoeffs);
734  }
735 
736  // g should be a positive integer now!
738 
739  if( !n_IsOne(g, ntCoeffs) )
740  {
741  DEN (f) = p_NSet(g, ntRing);
742  p_Normalize(DEN(f), ntRing);
743  assume( DEN (f) != NULL );
744  }
745  else
746  {
747  //DEN(f) = NULL; // done by omAlloc0
748  n_Delete(&g, ntCoeffs);
749  }
750  }
751 
752  p_Normalize(p, ntRing);
753  NUM(f) = p;
754  //COM(f) = 0; // done by omAlloc0
755 
756  //check_N((number)f,cf);
757  ntTest((number)f);
758  return (number)f;
759 }
760 
761 static long ntInt(number &a, const coeffs cf)
762 {
763  //check_N(a,cf);
764  ntTest(a);
765  if (IS0(a)) return 0;
767  fraction f = (fraction)a;
768  if (!DENIS1(f)) return 0;
769 
770  const poly aAsPoly = NUM(f);
771 
772  if(aAsPoly == NULL)
773  return 0;
774 
775  if (!p_IsConstant(aAsPoly, ntRing))
776  return 0;
777 
778  assume( aAsPoly != NULL );
779 
780  return n_Int(p_GetCoeff(aAsPoly, ntRing), ntCoeffs);
781 }
782 
783 /* return FALSE, if a is a constant <=0 */
784 static BOOLEAN ntGreaterZero(number a, const coeffs cf)
785 {
786  //check_N(a,cf);
787  ntTest(a);
788  if (IS0(a)) return FALSE;
789  fraction f = (fraction)a;
790  poly g = NUM(f);
792 }
793 
794 static BOOLEAN ntGreater(number a, number b, const coeffs cf)
795 {
796  //check_N(a,cf);
797  //check_N(b,cf);
798  ntTest(a);
799  ntTest(b);
800  number aNumCoeff = NULL; int aNumDeg = 0;
801  number aDenCoeff = NULL; int aDenDeg = 0;
802  number bNumCoeff = NULL; int bNumDeg = 0;
803  number bDenCoeff = NULL; int bDenDeg = 0;
804  if (IS0(a))
805  {
806  if (IS0(b)) return FALSE;
807  fraction fb = (fraction)b;
808  return (!n_GreaterZero(pGetCoeff(NUM(fb)), ntCoeffs));
809  }
810  if (IS0(b))
811  {
812  fraction fa = (fraction)a;
813  return (n_GreaterZero(pGetCoeff(NUM(fa)), ntCoeffs));
814  }
815  // now: a!=0, b!=0
816  fraction fa = (fraction)a;
817  aNumDeg = p_Totaldegree(NUM(fa), ntRing);
818  aNumCoeff = p_GetCoeff(NUM(fa), ntRing);
819  if (DEN(fa)!=NULL)
820  {
821  aDenDeg = p_Totaldegree(DEN(fa), ntRing);
822  aDenCoeff=p_GetCoeff(DEN(fa),ntRing);
823  }
824  fraction fb = (fraction)b;
825  bNumDeg = p_Totaldegree(NUM(fb), ntRing);
826  bNumCoeff = p_GetCoeff(NUM(fb), ntRing);
827  if (DEN(fb)!=NULL)
828  {
829  bDenDeg = p_Totaldegree(DEN(fb), ntRing);
830  bDenCoeff=p_GetCoeff(DEN(fb),ntRing);
831  }
832  if (aNumDeg-aDenDeg > bNumDeg-bDenDeg) return TRUE;
833  if (aNumDeg-aDenDeg < bNumDeg-bDenDeg) return FALSE;
834  number aa;
835  number bb;
836  if (bDenCoeff==NULL) aa=n_Copy(aNumCoeff,ntCoeffs);
837  else aa=n_Mult(aNumCoeff,bDenCoeff,ntCoeffs);
838  if (aDenCoeff==NULL) bb=n_Copy(bNumCoeff,ntCoeffs);
839  else bb=n_Mult(bNumCoeff,aDenCoeff,ntCoeffs);
840  BOOLEAN rr= n_Greater(aa, bb, ntCoeffs);
841  n_Delete(&aa,ntCoeffs);
842  n_Delete(&bb,ntCoeffs);
843  return rr;
844 }
845 
846 static void ntCoeffWrite(const coeffs cf, BOOLEAN details)
847 {
848  assume( cf != NULL );
849 
850  const ring A = cf->extRing;
851 
852  assume( A != NULL );
853  assume( A->cf != NULL );
854 
855  n_CoeffWrite(A->cf, details);
856 
857 // rWrite(A);
858 
859  const int P = rVar(A);
860  assume( P > 0 );
861 
862  PrintS("(");
863 
864  for (int nop=0; nop < P; nop ++)
865  {
866  Print("%s", rRingVar(nop, A));
867  if (nop!=P-1) PrintS(", ");
868  }
869 
870  PrintS(")");
871 
872  assume( A->qideal == NULL );
873 
874 /*
875  PrintS("// Coefficients live in the rational function field\n");
876  Print("// K(");
877  for (int i = 0; i < rVar(ntRing); i++)
878  {
879  if (i > 0) PrintS(" ");
880  Print("%s", rRingVar(i, ntRing));
881  }
882  PrintS(") with\n");
883  PrintS("// K: "); n_CoeffWrite(cf->extRing->cf);
884 */
885 }
886 
887 number ntDiff(number a, number d, const coeffs cf)
888 {
889  //check_N(a,cf);
890  //check_N(d,cf);
891  ntTest(a);
892  ntTest(d);
893 
894  if (IS0(d))
895  {
896  WerrorS("ringvar expected");
897  return NULL;
898  }
899  fraction t = (fraction) d;
900  if (!DENIS1(t))
901  {
902  WerrorS("expected differentiation by a variable");
903  return NULL;
904  }
905  int k=p_Var(NUM(t),ntRing);
906  if (k==0)
907  {
908  WerrorS("expected differentiation by a variable");
909  return NULL;
910  }
911 
912  if (IS0(a)) return ntCopy(a, cf);
913 
914  fraction fa = (fraction)a;
915  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
916  if (DENIS1(fa))
917  {
918  NUM(result) = p_Diff(NUM(fa),k,ntRing);
919  //DEN(result) = NULL; // done by ..Alloc0..
920  if (NUM(result)==NULL)
921  {
923  return(NULL);
924  }
925  COM(result) = COM(fa)+DIFF_COMPLEXITY;
926  //check_N((number)result,cf);
927  ntTest((number)result);
928  return (number)result;
929  }
930 
931  poly fg = p_Mult_q(p_Copy(DEN(fa),ntRing),p_Diff(NUM(fa),k,ntRing),ntRing);
932  poly gf = p_Mult_q(p_Copy(NUM(fa),ntRing),p_Diff(DEN(fa),k,ntRing),ntRing);
933  NUM(result) = p_Sub(fg,gf,ntRing);
934  if (NUM(result)==NULL) return(NULL);
935  DEN(result) = pp_Mult_qq(DEN(fa), DEN(fa), ntRing);
936  COM(result) = COM(fa) + COM(fa) + DIFF_COMPLEXITY;
937  heuristicGcdCancellation((number)result, cf);
938 
939  //check_N((number)result,cf);
940  ntTest((number)result);
941  return (number)result;
942 }
943 
944 static number ntAdd(number a, number b, const coeffs cf)
945 {
946  //check_N(a,cf);
947  //check_N(b,cf);
948  ntTest(a);
949  ntTest(b);
950  if (IS0(a)) return ntCopy(b, cf);
951  if (IS0(b)) return ntCopy(a, cf);
952 
953  fraction fa = (fraction)a;
954  fraction fb = (fraction)b;
955 
956  poly g = p_Copy(NUM(fa), ntRing);
957  if (!DENIS1(fb)) g = p_Mult_q(g, p_Copy(DEN(fb), ntRing), ntRing);
958  poly h = p_Copy(NUM(fb), ntRing);
959  if (!DENIS1(fa)) h = p_Mult_q(h, p_Copy(DEN(fa), ntRing), ntRing);
960  g = p_Add_q(g, h, ntRing);
961 
962  if (g == NULL) return NULL;
963 
964  poly f;
965  if (DENIS1(fa) && DENIS1(fb)) f = NULL;
966  else if (!DENIS1(fa) && DENIS1(fb)) f = p_Copy(DEN(fa), ntRing);
967  else if (DENIS1(fa) && !DENIS1(fb)) f = p_Copy(DEN(fb), ntRing);
968  else /* both denom's are != 1 */ f = p_Mult_q(p_Copy(DEN(fa), ntRing),
969  p_Copy(DEN(fb), ntRing),
970  ntRing);
971 
972  fraction result = (fraction)omAllocBin(fractionObjectBin);
973  NUM(result) = g;
974  DEN(result) = f;
975  COM(result) = COM(fa) + COM(fb) + ADD_COMPLEXITY;
976  heuristicGcdCancellation((number)result, cf);
977 
978 // ntTest((number)result);
979 
980  //check_N((number)result,cf);
981  ntTest((number)result);
982  return (number)result;
983 }
984 
985 static number ntSub(number a, number b, const coeffs cf)
986 {
987  //check_N(a,cf);
988  //check_N(b,cf);
989  ntTest(a);
990  ntTest(b);
991  if (IS0(a)) return ntNeg(ntCopy(b, cf), cf);
992  if (IS0(b)) return ntCopy(a, cf);
993 
994  fraction fa = (fraction)a;
995  fraction fb = (fraction)b;
996 
997  poly g = p_Copy(NUM(fa), ntRing);
998  if (!DENIS1(fb)) g = p_Mult_q(g, p_Copy(DEN(fb), ntRing), ntRing);
999  poly h = p_Copy(NUM(fb), ntRing);
1000  if (!DENIS1(fa)) h = p_Mult_q(h, p_Copy(DEN(fa), ntRing), ntRing);
1001  g = p_Add_q(g, p_Neg(h, ntRing), ntRing);
1002 
1003  if (g == NULL) return NULL;
1004 
1005  poly f;
1006  if (DENIS1(fa) && DENIS1(fb)) f = NULL;
1007  else if (!DENIS1(fa) && DENIS1(fb)) f = p_Copy(DEN(fa), ntRing);
1008  else if (DENIS1(fa) && !DENIS1(fb)) f = p_Copy(DEN(fb), ntRing);
1009  else /* both den's are != 1 */ f = p_Mult_q(p_Copy(DEN(fa), ntRing),
1010  p_Copy(DEN(fb), ntRing),
1011  ntRing);
1012 
1013  fraction result = (fraction)omAllocBin(fractionObjectBin);
1014  NUM(result) = g;
1015  DEN(result) = f;
1016  COM(result) = COM(fa) + COM(fb) + ADD_COMPLEXITY;
1017  heuristicGcdCancellation((number)result, cf);
1018 // ntTest((number)result);
1019  //check_N((number)result,cf);
1020  ntTest((number)result);
1021  return (number)result;
1022 }
1023 
1024 static number ntMult(number a, number b, const coeffs cf)
1025 {
1026  //check_N(a,cf);
1027  //check_N(b,cf);
1028  ntTest(a); // !!!?
1029  ntTest(b); // !!!?
1030 
1031  if (IS0(a) || IS0(b)) return NULL;
1032 
1033  fraction fa = (fraction)a;
1034  fraction fb = (fraction)b;
1035 
1036  const poly g = pp_Mult_qq(NUM(fa), NUM(fb), ntRing);
1037 
1038  if (g == NULL) return NULL; // may happen due to zero divisors???
1039 
1040  fraction result = (fraction)omAllocBin(fractionObjectBin);
1041 
1042  NUM(result) = g;
1043 
1044  const poly da = DEN(fa);
1045  const poly db = DEN(fb);
1046 
1047 
1048  //check_N((number)result,cf);
1049  if (db == NULL)
1050  {
1051  // b = ? // NULL
1052 
1053  if(da == NULL)
1054  { // both fa && fb are ?? // NULL!
1055  assume (da == NULL && db == NULL);
1056  DEN(result) = NULL;
1057  COM(result) = 0;
1058  }
1059  else
1060  {
1061  assume (da != NULL && db == NULL);
1062  DEN(result) = p_Copy(da, ntRing);
1063  COM(result) = COM(fa) + MULT_COMPLEXITY;
1064  heuristicGcdCancellation((number)result, cf);
1065  //check_N((number)result,cf);
1066  }
1067  }
1068  else
1069  { // b = ?? / ??
1070  if (da == NULL)
1071  { // a == ? // NULL
1072  assume( db != NULL && da == NULL);
1073  DEN(result) = p_Copy(db, ntRing);
1074  COM(result) = COM(fb) + MULT_COMPLEXITY;
1075  heuristicGcdCancellation((number)result, cf);
1076  //check_N((number)result,cf);
1077  }
1078  else /* both den's are != 1 */
1079  {
1080  assume (da != NULL && db != NULL);
1081  DEN(result) = pp_Mult_qq(da, db, ntRing);
1082  COM(result) = COM(fa) + COM(fb) + MULT_COMPLEXITY;
1083  heuristicGcdCancellation((number)result, cf);
1084  //check_N((number)result,cf);
1085  }
1086  }
1087 
1088 // ntTest((number)result);
1089 
1090  //check_N((number)result,cf);
1091  ntTest((number)result);
1092  return (number)result;
1093 }
1094 
1095 static void ntNormalizeDen(fraction result, const ring R)
1096 {
1097  if ((nCoeff_has_simple_inverse(R->cf))
1098  && (result!=NULL)
1099  && (DEN(result)!=NULL))
1100  {
1101  poly n=DEN(result);
1102  if (!n_IsOne(pGetCoeff(n),R->cf))
1103  {
1104  number inv=n_Invers(pGetCoeff(n),R->cf);
1105  DEN(result)=p_Mult_nn(n,inv,R);
1106  NUM(result)=p_Mult_nn(NUM(result),inv,R);
1107  n_Delete(&inv,R->cf);
1108  if (p_IsOne(DEN(result), R))
1109  {
1110  n=DEN(result);
1111  DEN(result)=NULL;
1112  COM(result) = 0;
1113  p_Delete(&n,R);
1114  }
1115  }
1116  }
1117 }
1118 
1119 static number ntDiv(number a, number b, const coeffs cf)
1120 {
1121  //check_N(a,cf);
1122  //check_N(b,cf);
1123  ntTest(a);
1124  ntTest(b);
1125  if (IS0(a)) return NULL;
1126  if (IS0(b)) WerrorS(nDivBy0);
1127 
1128  fraction fa = (fraction)a;
1129  fraction fb = (fraction)b;
1130 
1131  poly g = p_Copy(NUM(fa), ntRing);
1132  if (!DENIS1(fb)) g = p_Mult_q(g, p_Copy(DEN(fb), ntRing), ntRing);
1133 
1134  if (g == NULL) return NULL; /* may happen due to zero divisors */
1135 
1136  poly f = p_Copy(NUM(fb), ntRing);
1137  if (!DENIS1(fa)) f = p_Mult_q(f, p_Copy(DEN(fa), ntRing), ntRing);
1138 
1139  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
1140  NUM(result) = g;
1141  if (!n_GreaterZero(pGetCoeff(f),ntCoeffs))
1142  {
1143  g=p_Neg(g,ntRing);
1144  f=p_Neg(f,ntRing);
1145  NUM(result) = g;
1146  }
1147  if (!p_IsConstant(f,ntRing) || !n_IsOne(pGetCoeff(f),ntCoeffs))
1148  {
1149  DEN(result) = f;
1150  }
1151  COM(result) = COM(fa) + COM(fb) + MULT_COMPLEXITY;
1152 // definiteGcdCancellation((number)result, cf,FALSE);
1153  heuristicGcdCancellation((number)result, cf);
1154 // ntTest((number)result);
1155  //check_N((number)result,cf);
1156  ntNormalizeDen(result,ntRing);
1157  ntTest((number)result);
1158  return (number)result;
1159 }
1160 
1161 static number ntInvers(number a, const coeffs cf)
1162 {
1163  //check_N(a,cf);
1164  ntTest(a);
1165  if (IS0(a))
1166  {
1167  WerrorS(nDivBy0);
1168  return NULL;
1169  }
1170  fraction f = (fraction)a;
1171  assume( f != NULL );
1172 
1173  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
1174 
1175  assume( NUM(f) != NULL );
1176  const poly den = DEN(f);
1177 
1178  if (den == NULL)
1179  NUM(result) = p_One(ntRing);
1180  else
1181  NUM(result) = p_Copy(den, ntRing);
1182 
1183  if( !NUMIS1(f) )
1184  {
1185  poly num_f=NUM(f);
1186  BOOLEAN neg= !n_GreaterZero(pGetCoeff(num_f),ntCoeffs);
1187  if (neg)
1188  {
1189  num_f=p_Neg(p_Copy(num_f, ntRing), ntRing);
1190  NUM(result)=p_Neg(NUM(result), ntRing);
1191  }
1192  else
1193  {
1194  num_f=p_Copy(num_f, ntRing);
1195  }
1196  DEN(result) = num_f;
1197  COM(result) = COM(f);
1198  if (neg)
1199  {
1200  if (p_IsOne(num_f, ntRing))
1201  {
1202  DEN(result)=NULL;
1203  //COM(result) = 0;
1204  p_Delete(&num_f,ntRing);
1205  }
1206  }
1207  }
1208  //else// Alloc0
1209  //{
1210  // DEN(result) = NULL;
1211  // COM(result) = 0;
1212  //}
1213  ntNormalizeDen(result,ntRing);
1214  ntTest((number)result); // !!!!
1215  //check_N((number)result,cf);
1216  return (number)result;
1217 }
1218 
1219 /* 0^0 = 0;
1220  for |exp| <= 7 compute power by a simple multiplication loop;
1221  for |exp| >= 8 compute power along binary presentation of |exp|, e.g.
1222  p^13 = p^1 * p^4 * p^8, where we utilise that
1223  p^(2^(k+1)) = p^(2^k) * p^(2^k);
1224  intermediate cancellation is controlled by the in-place method
1225  heuristicGcdCancellation; see there.
1226 */
1227 static void ntPower(number a, int exp, number *b, const coeffs cf)
1228 {
1229  ntTest(a);
1230 
1231  /* special cases first */
1232  if (IS0(a))
1233  {
1234  if (exp >= 0) *b = NULL;
1235  else WerrorS(nDivBy0);
1236  }
1237  else if (exp == 0) { *b = ntInit(1, cf); return;}
1238  else if (exp == 1) { *b = ntCopy(a, cf); return;}
1239  else if (exp == -1) { *b = ntInvers(a, cf); return;}
1240 
1241  int expAbs = exp; if (expAbs < 0) expAbs = -expAbs;
1242 
1243  /* now compute a^expAbs */
1244  number pow; number t;
1245  if (expAbs <= 7)
1246  {
1247  pow = ntCopy(a, cf);
1248  for (int i = 2; i <= expAbs; i++)
1249  {
1250  t = ntMult(pow, a, cf);
1251  ntDelete(&pow, cf);
1252  pow = t;
1253  heuristicGcdCancellation(pow, cf);
1254  }
1255  }
1256  else
1257  {
1258  pow = ntInit(1, cf);
1259  number factor = ntCopy(a, cf);
1260  while (expAbs != 0)
1261  {
1262  if (expAbs & 1)
1263  {
1264  t = ntMult(pow, factor, cf);
1265  ntDelete(&pow, cf);
1266  pow = t;
1267  heuristicGcdCancellation(pow, cf);
1268  }
1269  expAbs = expAbs / 2;
1270  if (expAbs != 0)
1271  {
1272  t = ntMult(factor, factor, cf);
1273  ntDelete(&factor, cf);
1274  factor = t;
1275  heuristicGcdCancellation(factor, cf);
1276  }
1277  }
1278  ntDelete(&factor, cf);
1279  }
1280 
1281  /* invert if original exponent was negative */
1282  if (exp < 0)
1283  {
1284  t = ntInvers(pow, cf);
1285  ntDelete(&pow, cf);
1286  pow = t;
1287  }
1288  *b = pow;
1289  ntTest(*b);
1290  //check_N(*b,cf);
1291 }
1292 
1293 /* modifies a */
1294 /* this is an intermediate simplification routine - not a comple "normalize" */
1295 static void heuristicGcdCancellation(number a, const coeffs cf)
1296 {
1297  if (IS0(a)) return;
1298 
1299  fraction f = (fraction)a;
1300  p_Normalize(NUM(f),ntRing);
1301  if (DENIS1(f) || NUMIS1(f)) { COM(f) = 0; return; }
1302 
1303  assume( DEN(f) != NULL );
1304  p_Normalize(DEN(f),ntRing);
1305 
1306  /* check whether NUM(f) = DEN(f), and - if so - replace 'a' by 1 */
1307  if (p_EqualPolys(NUM(f), DEN(f), ntRing))
1308  { /* numerator and denominator are both != 1 */
1309  p_Delete(&NUM(f), ntRing); NUM(f) = p_ISet(1, ntRing);
1310  p_Delete(&DEN(f), ntRing); DEN(f) = NULL;
1311  COM(f) = 0;
1312  }
1313  else
1314  {
1315  if (COM(f) > BOUND_COMPLEXITY)
1316  definiteGcdCancellation(a, cf, TRUE);
1317 
1318  // TODO: check if it is enough to put the following into definiteGcdCancellation?!
1319  if( DEN(f) != NULL )
1320  {
1321  if( !n_GreaterZero(pGetCoeff(DEN(f)), ntCoeffs) )
1322  {
1323  NUM(f) = p_Neg(NUM(f), ntRing);
1324  DEN(f) = p_Neg(DEN(f), ntRing);
1325  }
1326  if (ntCoeffs->has_simple_Inverse)
1327  {
1328  if (!n_IsOne(pGetCoeff(DEN(f)),ntCoeffs))
1329  {
1330  number inv=n_Invers(pGetCoeff(DEN(f)),ntCoeffs);
1331  DEN(f)=p_Mult_nn(DEN(f),inv,ntRing);
1332  NUM(f)=p_Mult_nn(NUM(f),inv,ntRing);
1333  }
1334  if(p_LmIsConstant(DEN(f),ntRing))
1335  {
1336  p_Delete(&DEN(f),ntRing);
1337  COM(f)=0;
1338  }
1339  }
1340  if ((DEN(f)!=NULL)
1341  && (pNext(DEN(f))==NULL))
1342  {
1343  poly den_f=DEN(f);
1344  poly h=NUM(f);
1345  loop
1346  {
1347  if (h==NULL)
1348  {
1349  h=NUM(f);
1350  do
1351  {
1352  p_ExpVectorDiff(h,h,den_f,ntRing);
1353  pIter(h);
1354  } while(h!=NULL);
1355  p_ExpVectorDiff(den_f,den_f,den_f,ntRing);
1356  break;
1357  }
1358  int i=0;
1359  do
1360  {
1361  i++;
1362  if (p_GetExp(den_f,i,ntRing) > p_GetExp(h,i,ntRing)) return;
1363  } while(i<ntRing->N);
1364  pIter(h);
1365  }
1366  }
1367  }
1368  }
1369  if ((DEN(f)!=NULL)
1370  && (pNext(DEN(f))==NULL)
1371  && (p_LmIsConstantComp(DEN(f),ntRing))
1372  && (n_IsOne(pGetCoeff(DEN(f)),ntCoeffs)))
1373  {
1374  p_Delete(&DEN(f),ntRing);
1375  COM(f)=0;
1376  }
1377 }
1378 
1379 /// modifies a
1380 static void definiteGcdCancellation(number a, const coeffs cf,
1381  BOOLEAN simpleTestsHaveAlreadyBeenPerformed)
1382 {
1383 // ntTest(a); // !!!!
1384 
1385  fraction f = (fraction)a;
1386 
1387  if (IS0(a)) return;
1388  if (COM(f)==0) return;
1389  if (DENIS1(f) || NUMIS1(f)) { COM(f) = 0; ntTest(a); return; }
1390  if (!simpleTestsHaveAlreadyBeenPerformed)
1391  {
1392 
1393  /* check whether NUM(f) = DEN(f), and - if so - replace 'a' by 1 */
1394  if (p_EqualPolys(NUM(f), DEN(f), ntRing))
1395  { /* numerator and denominator are both != 1 */
1396  p_Delete(&NUM(f), ntRing); NUM(f) = p_ISet(1, ntRing);
1397  p_Delete(&DEN(f), ntRing); DEN(f) = NULL;
1398  COM(f) = 0;
1399  ntTest(a);
1400  return;
1401  }
1402  }
1403  /*if (rField_is_Q(ntRing))
1404  {
1405  number c=n_Copy(pGetCoeff(NUM(f)),ntCoeffs);
1406  poly p=pNext(NUM(f));
1407  while((p!=NULL)&&(!n_IsOne(c,ntCoeffs)))
1408  {
1409  number cc=n_Gcd(c,pGetCoeff(p),ntCoeffs);
1410  n_Delete(&c,ntCoeffs);
1411  c=cc;
1412  pIter(p);
1413  };
1414  p=DEN(f);
1415  while((p!=NULL)&&(!n_IsOne(c,ntCoeffs)))
1416  {
1417  number cc=n_Gcd(c,pGetCoeff(p),ntCoeffs);
1418  n_Delete(&c,ntCoeffs);
1419  c=cc;
1420  pIter(p);
1421  };
1422  if(!n_IsOne(c,ntCoeffs))
1423  {
1424  p=NUM(f);
1425  do
1426  {
1427  number cc=n_Div(pGetCoeff(p),c,ntCoeffs);
1428  n_Normalize(cc,ntCoeffs);
1429  p_SetCoeff(p,cc,ntRing);
1430  pIter(p);
1431  } while(p!=NULL);
1432  p=DEN(f);
1433  do
1434  {
1435  number cc=n_Div(pGetCoeff(p),c,ntCoeffs);
1436  n_Normalize(cc,ntCoeffs);
1437  p_SetCoeff(p,cc,ntRing);
1438  pIter(p);
1439  } while(p!=NULL);
1440  n_Delete(&c,ntCoeffs);
1441  if(pNext(DEN(f))==NULL)
1442  {
1443  if (p_IsOne(DEN(f),ntRing))
1444  {
1445  p_LmDelete(&DEN(f),ntRing);
1446  COM(f)=0;
1447  return;
1448  }
1449  else
1450  {
1451  return;
1452  }
1453  }
1454  }
1455  }*/
1456 
1457  /* here we assume: NUM(f), DEN(f) !=NULL, in Z_a reqp. Z/p_a */
1458  //StringSetS("");ntWriteLong(a,cf);
1459  poly pGcd = singclap_gcd_and_divide(NUM(f), DEN(f), ntRing);
1460  //PrintS("gcd= ");p_wrp(pGcd,ntRing);PrintLn();
1461  if (p_IsConstant(pGcd, ntRing)
1462  && n_IsOne(p_GetCoeff(pGcd, ntRing), ntCoeffs)
1463  )
1464  { /* gcd = 1; nothing to cancel;
1465  Suppose the given rational function field is over Q. Although the
1466  gcd is 1, we may have produced fractional coefficients in NUM(f),
1467  DEN(f), or both, due to previous arithmetics. The next call will
1468  remove those nested fractions, in case there are any. */
1469  if (nCoeff_is_Zp(ntCoeffs))
1470  {
1471  NUM (f) = p_Div_nn (NUM (f), p_GetCoeff (DEN(f),ntRing), ntRing);
1472  if (p_IsConstant (DEN (f), ntRing))
1473  {
1474  p_Delete(&DEN (f), ntRing);
1475  DEN (f) = NULL;
1476  }
1477  else
1478  {
1479  p_Norm (DEN (f),ntRing);
1480  }
1481  } else if (nCoeff_is_Q(ntCoeffs)) handleNestedFractionsOverQ(f, cf);
1482  }
1483  else
1484  { /* We divide both NUM(f) and DEN(f) by the gcd which is known
1485  to be != 1. */
1486  if (p_IsConstant(DEN(f), ntRing) &&
1487  n_IsOne(p_GetCoeff(DEN(f), ntRing), ntCoeffs))
1488  {
1489  /* DEN(f) = 1 needs to be represented by NULL! */
1490  p_Delete(&DEN(f), ntRing);
1491  DEN(f) = NULL;
1492  }
1493  else
1494  {
1495  if (nCoeff_is_Zp(ntCoeffs))
1496  {
1497  NUM (f) = p_Div_nn (NUM (f), p_GetCoeff (DEN(f),ntRing), ntRing);
1498  if (p_IsConstant (DEN (f), ntRing))
1499  {
1500  p_Delete(&DEN (f), ntRing);
1501  DEN (f) = NULL;
1502  }
1503  else
1504  {
1505  p_Norm (DEN (f),ntRing);
1506  }
1507  }
1508  }
1509  }
1510  p_Delete(&pGcd, ntRing);
1511 // StringAppendS(" -> ");ntWriteLong(a,cf);StringAppendS("\n");{ char* s = StringEndS(); Print("%s", s); omFree(s); }
1512  COM(f) = 0;
1513 
1514  if( DEN(f) != NULL )
1515  {
1516  if( !n_GreaterZero(pGetCoeff(DEN(f)), ntCoeffs) )
1517  {
1518  NUM(f) = p_Neg(NUM(f), ntRing);
1519  DEN(f) = p_Neg(DEN(f), ntRing);
1520  if (p_IsConstant(DEN(f), ntRing) &&
1521  n_IsOne(p_GetCoeff(DEN(f), ntRing), ntCoeffs))
1522  {
1523  /* DEN(f) = 1 needs to be represented by NULL! */
1524  p_Delete(&DEN(f), ntRing);
1525  DEN (f) = NULL;
1526  }
1527  }
1528  }
1529  ntTest(a); // !!!!
1530 }
1531 
1532 static void ntWriteLong(number a, const coeffs cf)
1533 {
1534  ntTest(a);
1535  if (IS0(a))
1536  StringAppendS("0");
1537  else
1538  {
1539  fraction f = (fraction)a;
1540  // stole logic from napWrite from kernel/longtrans.cc of legacy singular
1541  BOOLEAN omitBrackets = p_IsConstant(NUM(f), ntRing);
1542  if (!omitBrackets) StringAppendS("(");
1543  p_String0Long(NUM(f), ntRing, ntRing);
1544  if (!omitBrackets) StringAppendS(")");
1545  if (!DENIS1(f))
1546  {
1547  StringAppendS("/");
1548  omitBrackets = p_IsConstant(DEN(f), ntRing);
1549  if (!omitBrackets) StringAppendS("(");
1550  p_String0Long(DEN(f), ntRing, ntRing);
1551  if (!omitBrackets) StringAppendS(")");
1552  }
1553  }
1554  ntTest(a); // !!!!
1555 }
1556 
1557 static void ntWriteShort(number a, const coeffs cf)
1558 {
1559  ntTest(a);
1560  if (IS0(a))
1561  StringAppendS("0");
1562  else
1563  {
1564  fraction f = (fraction)a;
1565  // stole logic from napWrite from kernel/longtrans.cc of legacy singular
1566  BOOLEAN omitBrackets = p_IsConstant(NUM(f), ntRing);
1567  if (!omitBrackets) StringAppendS("(");
1568  p_String0Short(NUM(f), ntRing, ntRing);
1569  if (!omitBrackets) StringAppendS(")");
1570  if (!DENIS1(f))
1571  {
1572  StringAppendS("/");
1573  omitBrackets = p_IsConstant(DEN(f), ntRing);
1574  if (!omitBrackets) StringAppendS("(");
1575  p_String0Short(DEN(f), ntRing, ntRing);
1576  if (!omitBrackets) StringAppendS(")");
1577  }
1578  }
1579  ntTest(a);
1580 }
1581 
1582 static const char * ntRead(const char *s, number *a, const coeffs cf)
1583 {
1584  poly p;
1585  const char * result = p_Read(s, p, ntRing);
1586  if (p == NULL) *a = NULL;
1587  else *a = ntInit(p, cf);
1588  ntTest(*a);
1589  return result;
1590 }
1591 
1592 static void ntNormalize (number &a, const coeffs cf)
1593 {
1594  if ( /*(*/ a!=NULL /*)*/ )
1595  {
1596  //PrintS("num=");p_wrp(NUM(a),ntRing);
1597  //PrintS(" den=");p_wrp(DEN(a),ntRing);PrintLn();
1598  if (COM((fraction)a)>0) definiteGcdCancellation(a, cf, FALSE);
1599  if ((DEN((fraction)a)!=NULL)
1600  &&(!n_GreaterZero(pGetCoeff(DEN((fraction)a)),ntCoeffs)))
1601  {
1602  NUM((fraction)a)=p_Neg(NUM((fraction)a),ntRing);
1603  DEN((fraction)a)=p_Neg(DEN((fraction)a),ntRing);
1604  }
1605  }
1606  ntNormalizeDen((fraction)a,ntRing);
1607  ntTest(a); // !!!!
1608 }
1609 
1610 /* expects *param to be castable to TransExtInfo */
1611 static BOOLEAN ntCoeffIsEqual(const coeffs cf, n_coeffType n, void * param)
1612 {
1613  if (n_transExt != n) return FALSE;
1614  TransExtInfo *e = (TransExtInfo *)param;
1615  /* for rational function fields we expect the underlying
1616  polynomial rings to be IDENTICAL, i.e. the SAME OBJECT;
1617  this expectation is based on the assumption that we have properly
1618  registered cf and perform reference counting rather than creating
1619  multiple copies of the same coefficient field/domain/ring */
1620  if (ntRing == e->r)
1621  return TRUE;
1622 
1623  // NOTE: Q(a)[x] && Q(a)[y] should better share the _same_ Q(a)...
1624  if( rEqual(ntRing, e->r, TRUE) )
1625  {
1626  rDelete(e->r);
1627  return TRUE;
1628  }
1629 
1630  return FALSE;
1631 }
1632 
1633 static number ntNormalizeHelper(number a, number b, const coeffs cf)
1634 {
1635  ntTest(a);
1636  ntTest(b);
1637  fraction fb = (fraction)b;
1638  if ((b==NULL)||(DEN(fb)==NULL)) return ntCopy(a,cf);
1639  fraction fa = (fraction)a;
1640  /* singclap_gcd destroys its arguments; we hence need copies: */
1641  poly pa = p_Copy(NUM(fa), ntRing);
1642  poly pb = p_Copy(DEN(fb), ntRing);
1643 
1644  poly pGcd;
1645  if (nCoeff_is_Q(ntCoeffs))
1646  {
1647  if (p_IsConstant(pa,ntRing) && p_IsConstant(pb,ntRing))
1648  {
1649  pGcd = pa;
1650  p_SetCoeff (pGcd, n_Gcd (pGetCoeff(pGcd), pGetCoeff(pb), ntCoeffs), ntRing);
1651  }
1652  else
1653  {
1654  number contentpa, contentpb, tmp;
1655 
1656  contentpb= p_GetCoeff(pb, ntRing);
1657  pIter(pb);
1658  while (pb != NULL)
1659  {
1660  tmp = n_SubringGcd(contentpb, p_GetCoeff(pb, ntRing) , ntCoeffs);
1661  n_Delete(&contentpb, ntCoeffs);
1662  contentpb = tmp;
1663  pIter(pb);
1664  }
1665 
1666  contentpa= p_GetCoeff(pa, ntRing);
1667  pIter(pa);
1668  while (pa != NULL)
1669  {
1670  tmp = n_SubringGcd(contentpa, p_GetCoeff(pa, ntRing), ntCoeffs);
1671  n_Delete(&contentpa, ntCoeffs);
1672  contentpa = tmp;
1673  pIter(pa);
1674  }
1675 
1676  tmp= n_SubringGcd (contentpb, contentpa, ntCoeffs);
1677  n_Delete(&contentpa, ntCoeffs);
1678  n_Delete(&contentpb, ntCoeffs);
1679  contentpa= tmp;
1680  p_Delete(&pb, ntRing);
1681  p_Delete(&pa, ntRing);
1682 
1683  /* singclap_gcd destroys its arguments; we hence need copies: */
1684  pGcd = singclap_gcd(p_Copy(NUM(fa),ntRing), p_Copy(DEN(fb),ntRing), ntRing);
1685  pGcd= p_Mult_nn (pGcd, contentpa, ntRing);
1686  n_Delete(&contentpa, ntCoeffs);
1687  }
1688  }
1689  else
1690  pGcd = singclap_gcd(pa, pb, cf->extRing);
1691 
1692  /* Note that, over Q, singclap_gcd will remove the denominators in all
1693  rational coefficients of pa and pb, before starting to compute
1694  the gcd. Thus, we do not need to ensure that the coefficients of
1695  pa and pb live in Z; they may well be elements of Q\Z. */
1696 
1697  if (p_IsConstant(pGcd, ntRing) &&
1698  n_IsOne(p_GetCoeff(pGcd, ntRing), ntCoeffs))
1699  { /* gcd = 1; return pa*pb*/
1700  p_Delete(&pGcd,ntRing);
1701  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
1702  NUM(result) = pp_Mult_qq(NUM(fa),DEN(fb),ntRing);
1703 
1704  ntTest((number)result); // !!!!
1705 
1706  return (number)result;
1707  }
1708 
1709 
1710  /* return pa*pb/gcd */
1711  poly newNum = singclap_pdivide(NUM(fa), pGcd, ntRing);
1712  p_Delete(&pGcd,ntRing);
1713  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
1714  NUM(result) = p_Mult_q(p_Copy(DEN(fb),ntRing),newNum,ntRing);
1715  ntTest((number)result); // !!!!
1716  return (number)result;
1717 
1718  return NULL;
1719 }
1720 
1721 static number ntGcd(number a, number b, const coeffs cf)
1722 {
1723  ntTest(a);
1724  ntTest(b);
1725  if (a==NULL) return ntCopy(b,cf);
1726  if (b==NULL) return ntCopy(a,cf);
1727  fraction fa = (fraction)a;
1728  fraction fb = (fraction)b;
1729 
1730  poly pa = p_Copy(NUM(fa), ntRing);
1731  poly pb = p_Copy(NUM(fb), ntRing);
1732 
1733  poly pGcd;
1734  if (nCoeff_is_Q(ntCoeffs))
1735  {
1736  if (p_IsConstant(pa,ntRing) && p_IsConstant(pb,ntRing))
1737  {
1738  pGcd = pa;
1739  p_SetCoeff (pGcd, n_SubringGcd (pGetCoeff(pGcd), pGetCoeff(pb), ntCoeffs), ntRing);
1740  }
1741  else
1742  {
1743  number contentpa, contentpb, tmp;
1744 
1745  contentpb= p_GetCoeff(pb, ntRing);
1746  pIter(pb);
1747  while (pb != NULL)
1748  {
1749  tmp = n_SubringGcd(contentpb, p_GetCoeff(pb, ntRing) , ntCoeffs);
1750  n_Delete(&contentpb, ntCoeffs);
1751  contentpb = tmp;
1752  pIter(pb);
1753  }
1754 
1755  contentpa= p_GetCoeff(pa, ntRing);
1756  pIter(pa);
1757  while (pa != NULL)
1758  {
1759  tmp = n_SubringGcd(contentpa, p_GetCoeff(pa, ntRing), ntCoeffs);
1760  n_Delete(&contentpa, ntCoeffs);
1761  contentpa = tmp;
1762  pIter(pa);
1763  }
1764 
1765  tmp= n_SubringGcd (contentpb, contentpa, ntCoeffs);
1766  n_Delete(&contentpa, ntCoeffs);
1767  n_Delete(&contentpb, ntCoeffs);
1768  contentpa= tmp;
1769  p_Delete(&pb, ntRing);
1770  p_Delete(&pa, ntRing);
1771 
1772  /* singclap_gcd destroys its arguments; we hence need copies: */
1773  pGcd = singclap_gcd(p_Copy(NUM(fa),ntRing), p_Copy(NUM(fb),ntRing), ntRing);
1774  pGcd= p_Mult_nn (pGcd, contentpa, ntRing);
1775  n_Delete(&contentpa, ntCoeffs);
1776  }
1777  }
1778  else
1779  pGcd = singclap_gcd(pa, pb, cf->extRing);
1780  /* Note that, over Q, singclap_gcd will remove the denominators in all
1781  rational coefficients of pa and pb, before starting to compute
1782  the gcd. Thus, we do not need to ensure that the coefficients of
1783  pa and pb live in Z; they may well be elements of Q\Z. */
1784 
1785  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
1786  NUM(result) = pGcd;
1787  ntTest((number)result); // !!!!
1788  return (number)result;
1789 }
1790 //number ntGcd_dummy(number a, number b, const coeffs cf)
1791 //{
1792 // extern char my_yylinebuf[80];
1793 // Print("ntGcd in >>%s<<\n",my_yylinebuf);
1794 // return ntGcd(a,b,cf);
1795 //}
1796 
1797 static int ntSize(number a, const coeffs cf)
1798 {
1799  ntTest(a);
1800  if (IS0(a)) return -1;
1801  /* this has been taken from the old implementation of field extensions,
1802  where we computed the sum of the degrees and the numbers of terms in
1803  the numerator and denominator of a; so we leave it at that, for the
1804  time being */
1805  fraction f = (fraction)a;
1806  poly p = NUM(f);
1807  int noOfTerms = 0;
1808  int numDegree = 0;
1809  if (p!=NULL)
1810  {
1811  numDegree = p_Totaldegree(p,ntRing);
1812  noOfTerms = pLength(p);
1813  }
1814  int denDegree = 0;
1815  if (!DENIS1(f))
1816  {
1817  denDegree = p_Totaldegree(DEN(f),ntRing);
1818  noOfTerms += pLength(DEN(f));
1819  }
1820  ntTest(a); // !!!!
1821  return numDegree + denDegree + noOfTerms;
1822 }
1823 
1824 /* assumes that src = Q or Z, dst = Q(t_1, ..., t_s) */
1825 static number ntMap00(number a, const coeffs src, const coeffs dst)
1826 {
1827  n_Test(a, src);
1828 
1829  if (n_IsZero(a, src)) return NULL;
1830  assume(src->rep == dst->extRing->cf->rep);
1831  if ((SR_HDL(a) & SR_INT) || (a->s==3))
1832  {
1833  number res=ntInit(p_NSet(n_Copy(a, src), dst->extRing), dst);
1834  n_Test(res, dst);
1835  return res;
1836  }
1837  number nn=n_GetDenom(a,src);
1838  number zz=n_GetNumerator(a,src);
1839  number res=ntInit(p_NSet(zz,dst->extRing), dst);
1840  fraction ff=(fraction)res;
1841  if (n_IsOne(nn,src)) DEN(ff)=NULL;
1842  else DEN(ff)=p_NSet(nn,dst->extRing);
1843 
1844  n_Test((number)ff,dst);
1845  //check_N((number)ff,dst);
1846  return (number)ff;
1847 }
1848 
1849 static number ntMapZ0(number a, const coeffs src, const coeffs dst)
1850 {
1851  n_Test(a, src);
1852  if (n_IsZero(a, src)) return NULL;
1853  nMapFunc nMap=n_SetMap(src,dst->extRing->cf);
1854  poly p=p_NSet(nMap(a, src,dst->extRing->cf), dst->extRing);
1855  if (n_IsZero(pGetCoeff(p),dst->extRing->cf))
1856  p_Delete(&p,dst->extRing);
1857  number res=ntInit(p, dst);
1858  n_Test(res,dst);
1859  return res;
1860 }
1861 
1862 /* assumes that src = Z/p, dst = Q(t_1, ..., t_s) */
1863 static number ntMapP0(number a, const coeffs src, const coeffs dst)
1864 {
1865  n_Test(a, src);
1866  if (n_IsZero(a, src)) return NULL;
1867  /* mapping via intermediate int: */
1868  int n = n_Int(a, src);
1869  number q = n_Init(n, dst->extRing->cf);
1870  if (n_IsZero(q, dst->extRing->cf))
1871  {
1872  n_Delete(&q, dst->extRing->cf);
1873  return NULL;
1874  }
1875  return ntInit(p_NSet(q, dst->extRing), dst);
1876 }
1877 
1878  /* assumes that either src = K(t_1, ..., t_s), dst = K(t_1, ..., t_s) */
1879 static number ntCopyMap(number a, const coeffs cf, const coeffs dst)
1880 {
1881  ntTest(a);
1882  if (IS0(a)) return NULL;
1883 
1884  const ring rSrc = cf->extRing;
1885  const ring rDst = dst->extRing;
1886 
1887  if( rSrc == rDst )
1888  return ntCopy(a, dst); // USUALLY WRONG!
1889 
1890  fraction f = (fraction)a;
1891  poly g = prCopyR(NUM(f), rSrc, rDst);
1892 
1893  poly h = NULL;
1894 
1895  if (!DENIS1(f))
1896  h = prCopyR(DEN(f), rSrc, rDst);
1897 
1898  fraction result = (fraction)omAllocBin(fractionObjectBin);
1899 
1900  NUM(result) = g;
1901  DEN(result) = h;
1902  COM(result) = COM(f);
1903  //check_N((number)result,dst);
1904  n_Test((number)result, dst);
1905  return (number)result;
1906 }
1907 
1908 static number ntGenMap(number a, const coeffs cf, const coeffs dst)
1909 {
1910  ntTest(a);
1911  if (IS0(a)) return NULL;
1912 
1913  const ring rSrc = cf->extRing;
1914  const ring rDst = dst->extRing;
1915 
1916  const nMapFunc nMap=n_SetMap(rSrc->cf,rDst->cf);
1917  fraction f = (fraction)a;
1918  poly g = prMapR(NUM(f), nMap, rSrc, rDst);
1919  /* g may contain summands with coeff 0 */
1920  poly hh=g;
1921  poly prev=NULL;
1922  while(hh!=NULL)
1923  {
1924  if (n_IsZero(pGetCoeff(hh),rDst->cf))
1925  {
1926  if (prev==NULL)
1927  {
1928  g=p_LmFreeAndNext(g,rDst);
1929  hh=g;
1930  }
1931  else
1932  {
1933  prev->next=p_LmFreeAndNext(prev->next,rDst);
1934  hh=prev->next;
1935  }
1936  }
1937  else
1938  {
1939  prev=hh;
1940  pIter(hh);
1941  }
1942  }
1943  if (g==NULL) return NULL;
1944 
1945  poly h = NULL;
1946 
1947  if (!DENIS1(f))
1948  {
1949  h = prMapR(DEN(f), nMap, rSrc, rDst);
1950  /* h may contain summands with coeff 0 */
1951  hh=h;
1952  prev=NULL;
1953  while(hh!=NULL)
1954  {
1955  if (n_IsZero(pGetCoeff(hh),rDst->cf))
1956  {
1957  if (prev==NULL)
1958  {
1959  h=p_LmFreeAndNext(h,rDst);
1960  hh=h;
1961  }
1962  else
1963  {
1964  prev->next=p_LmFreeAndNext(prev->next,rDst);
1965  hh=prev->next;
1966  }
1967  }
1968  else
1969  {
1970  prev=hh;
1971  pIter(hh);
1972  }
1973  }
1974  if (h==NULL) WerrorS("mapping to */0");
1975  }
1976 
1977  fraction result = (fraction)omAllocBin(fractionObjectBin);
1978 
1979  NUM(result) = g;
1980  DEN(result) = h;
1981  COM(result) = COM(f);
1982  //check_N((number)result,dst);
1983  n_Test((number)result, dst);
1984  return (number)result;
1985 }
1986 
1987 static number ntCopyAlg(number a, const coeffs cf, const coeffs dst)
1988 {
1989  n_Test(a, cf) ;
1990  if (n_IsZero(a, cf)) return NULL;
1991  return ntInit(prCopyR((poly)a, cf->extRing, dst->extRing),dst);
1992 }
1993 
1994 static number ntGenAlg(number a, const coeffs cf, const coeffs dst)
1995 {
1996  n_Test(a, cf) ;
1997  if (n_IsZero(a, cf)) return NULL;
1998 
1999  const nMapFunc nMap=n_SetMap(cf->extRing->cf,dst->extRing->cf);
2000  return ntInit(prMapR((poly)a, nMap, cf->extRing, dst->extRing),dst);
2001 }
2002 
2003 /* assumes that src = Q, dst = Z/p(t_1, ..., t_s) */
2004 static number ntMap0P(number a, const coeffs src, const coeffs dst)
2005 {
2006  n_Test(a, src) ;
2007  if (n_IsZero(a, src)) return NULL;
2008  // int p = rChar(dst->extRing);
2009 
2010  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 Zp
2011 
2012  if (n_IsZero(q, dst->extRing->cf))
2013  {
2014  n_Delete(&q, dst->extRing->cf);
2015  return NULL;
2016  }
2017 
2018  poly g = p_NSet(q, dst->extRing);
2019 
2020  fraction f = (fraction)omAlloc0Bin(fractionObjectBin);
2021  NUM(f) = g; // DEN(f) = NULL; COM(f) = 0;
2022  n_Test((number)f, dst);
2023  //check_N((number)f,dst);
2024  return (number)f;
2025 }
2026 
2027 /* assumes that src = Z/p, dst = Z/p(t_1, ..., t_s) */
2028 static number ntMapPP(number a, const coeffs src, const coeffs dst)
2029 {
2030  n_Test(a, src) ;
2031  if (n_IsZero(a, src)) return NULL;
2032  assume(src == dst->extRing->cf);
2033  poly p = p_One(dst->extRing);
2034  p_SetCoeff(p, n_Copy(a, src), dst->extRing);
2035  fraction f = (fraction)omAlloc0Bin(fractionObjectBin);
2036  NUM(f) = p; // DEN(f) = NULL; COM(f) = 0;
2037  n_Test((number)f, dst);
2038  //check_N((number)f,dst);
2039  return (number)f;
2040 }
2041 
2042 /* assumes that src = Z/u, dst = Z/p(t_1, ..., t_s), where u != p */
2043 static number ntMapUP(number a, const coeffs src, const coeffs dst)
2044 {
2045  n_Test(a, src) ;
2046  if (n_IsZero(a, src)) return NULL;
2047  /* mapping via intermediate int: */
2048  int n = n_Int(a, src);
2049  number q = n_Init(n, dst->extRing->cf);
2050  poly p;
2051  if (n_IsZero(q, dst->extRing->cf))
2052  {
2053  n_Delete(&q, dst->extRing->cf);
2054  return NULL;
2055  }
2056  p = p_One(dst->extRing);
2057  p_SetCoeff(p, q, dst->extRing);
2058  fraction f = (fraction)omAlloc0Bin(fractionObjectBin);
2059  NUM(f) = p; // DEN(f) = NULL; COM(f) = 0;
2060  n_Test((number)f, dst);
2061  //check_N((number)f,dst);
2062  return (number)f;
2063 }
2064 
2065 nMapFunc ntSetMap(const coeffs src, const coeffs dst)
2066 {
2067  /* dst is expected to be a rational function field */
2068  assume(getCoeffType(dst) == n_transExt);
2069 
2070  if( src == dst ) return ndCopyMap;
2071 
2072  int h = 0; /* the height of the extension tower given by dst */
2073  coeffs bDst = nCoeff_bottom(dst, h); /* the bottom field in the tower dst */
2074  coeffs bSrc = nCoeff_bottom(src, h); /* the bottom field in the tower src */
2075 
2076  /* for the time being, we only provide maps if h = 1 and if b is Q or
2077  some field Z/pZ: */
2078  if (h==0)
2079  {
2080  if ((src->rep==n_rep_gap_rat) && nCoeff_is_Q(bDst))
2081  return ntMap00; /// Q or Z --> Q(T)
2082  if (src->rep==n_rep_gap_gmp)
2083  return ntMapZ0; /// Z --> K(T)
2084  if (nCoeff_is_Zp(src) && nCoeff_is_Q(bDst))
2085  return ntMapP0; /// Z/p --> Q(T)
2086  if (nCoeff_is_Q_or_BI(src) && nCoeff_is_Zp(bDst))
2087  return ntMap0P; /// Q --> Z/p(T)
2088  if (nCoeff_is_Zp(src) && nCoeff_is_Zp(bDst))
2089  {
2090  if (src->ch == dst->ch) return ntMapPP; /// Z/p --> Z/p(T)
2091  else return ntMapUP; /// Z/u --> Z/p(T)
2092  }
2093  }
2094  if (h != 1) return NULL;
2095  //if ((!nCoeff_is_Zp(bDst)) && (!nCoeff_is_Q(bDst))) return NULL;
2096 
2097  /* Let T denote the sequence of transcendental extension variables, i.e.,
2098  K[t_1, ..., t_s] =: K[T];
2099  Let moreover, for any such sequence T, T' denote any subsequence of T
2100  of the form t_1, ..., t_w with w <= s. */
2101 
2102  if (rVar(src->extRing) > rVar(dst->extRing))
2103  return NULL;
2104 
2105  for (int i = 0; i < rVar(src->extRing); i++)
2106  if (strcmp(rRingVar(i, src->extRing), rRingVar(i, dst->extRing)) != 0)
2107  return NULL;
2108 
2109  if (src->type==n_transExt)
2110  {
2111  if (src->extRing->cf==dst->extRing->cf)
2112  return ntCopyMap; /// K(T') --> K(T)
2113  else
2114  return ntGenMap; /// K(T') --> K'(T)
2115  }
2116  else
2117  {
2118  if (src->extRing->cf==dst->extRing->cf)
2119  return ntCopyAlg; /// K(T') --> K(T)
2120  else
2121  return ntGenAlg; /// K(T') --> K'(T)
2122  }
2123 
2124  return NULL; /// default
2125 }
2126 #if 0
2127 nMapFunc ntSetMap_T(const coeffs src, const coeffs dst)
2128 {
2129  nMapFunc n=ntSetMap(src,dst);
2130  if (n==ntCopyAlg) printf("n=ntCopyAlg\n");
2131  else if (n==ntCopyMap) printf("n=ntCopyMap\n");
2132  else if (n==ntMapUP) printf("n=ntMapUP\n");
2133  else if (n==ntMap0P) printf("n=ntMap0P\n");
2134  else if (n==ntMapP0) printf("n=ntMapP0\n");
2135  else if (n==ntMap00) printf("n=ntMap00\n");
2136  else if (n==NULL) printf("n=NULL\n");
2137  else printf("n=?\n");
2138  return n;
2139 }
2140 #endif
2141 
2142 static void ntKillChar(coeffs cf)
2143 {
2144  if ((--cf->extRing->ref) == 0)
2145  rDelete(cf->extRing);
2146 }
2147 static number ntConvFactoryNSingN( const CanonicalForm n, const coeffs cf)
2148 {
2149  if (n.isZero()) return NULL;
2151  p_Normalize(p,ntRing);
2152  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
2153  NUM(result) = p;
2154  //DEN(result) = NULL; // done by omAlloc0Bin
2155  //COM(result) = 0; // done by omAlloc0Bin
2156  ntTest((number)result);
2157  return (number)result;
2158 }
2159 static CanonicalForm ntConvSingNFactoryN( number n, BOOLEAN /*setChar*/, const coeffs cf )
2160 {
2161  ntTest(n);
2162  if (IS0(n)) return CanonicalForm(0);
2163 
2164  fraction f = (fraction)n;
2165  return convSingPFactoryP(NUM(f),ntRing);
2166 }
2167 
2168 static int ntParDeg(number a, const coeffs cf)
2169 {
2170  ntTest(a);
2171  if (IS0(a)) return -1;
2172  fraction fa = (fraction)a;
2173  return cf->extRing->pFDeg(NUM(fa),cf->extRing);
2174 }
2175 
2176 /// return the specified parameter as a number in the given trans.ext.
2177 static number ntParameter(const int iParameter, const coeffs cf)
2178 {
2179  assume(getCoeffType(cf) == n_transExt);
2180 
2181  const ring R = cf->extRing;
2182  assume( R != NULL );
2183  assume( 0 < iParameter && iParameter <= rVar(R) );
2184 
2185  poly p = p_One(R); p_SetExp(p, iParameter, 1, R); p_Setm(p, R);
2186  p_Test(p,R);
2187 
2188  fraction f = (fraction)omAlloc0Bin(fractionObjectBin);
2189  NUM(f) = p;
2190  //DEN(f) = NULL;
2191  //COM(f) = 0;
2192 
2193  ntTest((number)f);
2194 
2195  return (number)f;
2196 }
2197 
2198 /// if m == var(i)/1 => return i,
2199 int ntIsParam(number m, const coeffs cf)
2200 {
2201  ntTest(m);
2202  assume(getCoeffType(cf) == n_transExt);
2203 
2204  const ring R = cf->extRing;
2205  assume( R != NULL );
2206 
2207  fraction f = (fraction)m;
2208 
2209  if( DEN(f) != NULL )
2210  return 0;
2211 
2212  return p_Var( NUM(f), R );
2213 }
2214 
2216 {
2217  static inline poly convert(const number& n)
2218  {
2219  // suitable for trans. ext. numbers that are fractions of polys
2220  return NUM((fraction)n); // return the numerator
2221  }
2222 };
2223 
2224 
2225 static void ntClearContent(ICoeffsEnumerator& numberCollectionEnumerator, number& c, const coeffs cf)
2226 {
2227  assume(cf != NULL);
2228  assume(getCoeffType(cf) == n_transExt);
2229  // all coeffs are given by fractions of polynomails over integers!!!
2230  // without denominators!!!
2231 
2232  const ring R = cf->extRing;
2233  assume(R != NULL);
2234  const coeffs Q = R->cf;
2235  assume(Q != NULL);
2236  assume(nCoeff_is_Q(Q));
2237 
2238 
2239  numberCollectionEnumerator.Reset();
2240 
2241  if( !numberCollectionEnumerator.MoveNext() ) // empty zero polynomial?
2242  {
2243  c = ntInit(1, cf);
2244  return;
2245  }
2246 
2247  // all coeffs are given by integers after returning from this routine
2248 
2249  // part 1, collect product of all denominators /gcds
2250  poly cand = NULL;
2251 
2252  do
2253  {
2254  number &n = numberCollectionEnumerator.Current();
2255 
2256  ntNormalize(n, cf);
2257 
2258  fraction f = (fraction)n;
2259 
2260  assume( f != NULL );
2261 
2262  const poly den = DEN(f);
2263 
2264  assume( den == NULL ); // ?? / 1 ?
2265 
2266  const poly num = NUM(f);
2267 
2268  if( cand == NULL )
2269  cand = p_Copy(num, R);
2270  else
2271  cand = singclap_gcd(cand, p_Copy(num, R), R); // gcd(cand, num)
2272 
2273  if( p_IsConstant(cand, R) )
2274  break;
2275  }
2276  while( numberCollectionEnumerator.MoveNext() ) ;
2277 
2278 
2279  // part2: all coeffs = all coeffs * cand
2280  if( cand != NULL )
2281  {
2282  if( !p_IsConstant(cand, R) )
2283  {
2284  c = ntInit(cand, cf);
2285  numberCollectionEnumerator.Reset();
2286  while (numberCollectionEnumerator.MoveNext() )
2287  {
2288  number &n = numberCollectionEnumerator.Current();
2289  const number t = ntDiv(n, c, cf); // TODO: rewrite!?
2290  ntDelete(&n, cf);
2291  n = t;
2292  }
2293  } // else NUM (result) = p_One(R);
2294  else { p_Delete(&cand, R); cand = NULL; }
2295  }
2296 
2297  // Quick and dirty fix for constant content clearing: consider numerators???
2298  CRecursivePolyCoeffsEnumerator<NTNumConverter> itr(numberCollectionEnumerator); // recursively treat the NUM(numbers) as polys!
2299  number cc;
2300 
2301  n_ClearContent(itr, cc, Q);
2302  number g = ntInit(p_NSet(cc, R), cf);
2303 
2304  if( cand != NULL )
2305  {
2306  number gg = ntMult(g, c, cf);
2307  ntDelete(&g, cf);
2308  ntDelete(&c, cf); c = gg;
2309  } else
2310  c = g;
2311  ntTest(c);
2312 }
2313 
2314 static void ntClearDenominators(ICoeffsEnumerator& numberCollectionEnumerator, number& c, const coeffs cf)
2315 {
2316  assume(cf != NULL);
2317  assume(getCoeffType(cf) == n_transExt); // both over Q(a) and Zp(a)!
2318  // all coeffs are given by fractions of polynomails over integers!!!
2319 
2320  numberCollectionEnumerator.Reset();
2321 
2322  if( !numberCollectionEnumerator.MoveNext() ) // empty zero polynomial?
2323  {
2324  c = ntInit(1, cf);
2325  return;
2326  }
2327 
2328  // all coeffs are given by integers after returning from this routine
2329 
2330  // part 1, collect product of all denominators /gcds
2331  poly cand = NULL;
2332 
2333  const ring R = cf->extRing;
2334  assume(R != NULL);
2335 
2336  const coeffs Q = R->cf;
2337  assume(Q != NULL);
2338 // assume(nCoeff_is_Q(Q));
2339 
2340  do
2341  {
2342  number &n = numberCollectionEnumerator.Current();
2343 
2344  ntNormalize(n, cf);
2345 
2346  fraction f = (fraction)ntGetDenom (n, cf);
2347 
2348  assume( f != NULL );
2349 
2350  const poly den = NUM(f);
2351 
2352  if( den == NULL ) // ?? / 1 ?
2353  continue;
2354 
2355  if( cand == NULL )
2356  cand = p_Copy(den, R);
2357  else
2358  {
2359  // cand === LCM( cand, den )!!!!
2360  // NOTE: maybe it's better to make the product and clearcontent afterwards!?
2361  // TODO: move the following to factory?
2362  poly gcd = singclap_gcd(p_Copy(cand, R), p_Copy(den, R), R); // gcd(cand, den) is monic no mater leading coeffs! :((((
2363  if (nCoeff_is_Q (Q))
2364  {
2365  number LcGcd= n_SubringGcd (p_GetCoeff (cand, R), p_GetCoeff(den, R), Q);
2366  gcd = p_Mult_nn(gcd, LcGcd, R);
2367  n_Delete(&LcGcd,Q);
2368  }
2369 // assume( n_IsOne(pGetCoeff(gcd), Q) ); // TODO: this may be wrong...
2370  cand = p_Mult_q(cand, p_Copy(den, R), R); // cand *= den
2371  const poly t = singclap_pdivide( cand, gcd, R ); // cand' * den / gcd(cand', den)
2372  p_Delete(&cand, R);
2373  p_Delete(&gcd, R);
2374  cand = t;
2375  }
2376  }
2377  while( numberCollectionEnumerator.MoveNext() );
2378 
2379  if( cand == NULL )
2380  {
2381  c = ntInit(1, cf);
2382  return;
2383  }
2384 
2385  c = ntInit(cand, cf);
2386 
2387  numberCollectionEnumerator.Reset();
2388 
2389  number d = NULL;
2390 
2391  while (numberCollectionEnumerator.MoveNext() )
2392  {
2393  number &n = numberCollectionEnumerator.Current();
2394  number t = ntMult(n, c, cf); // TODO: rewrite!?
2395  ntDelete(&n, cf);
2396 
2397  ntNormalize(t, cf); // TODO: needed?
2398  n = t;
2399 
2400  fraction f = (fraction)t;
2401  assume( f != NULL );
2402 
2403  const poly den = DEN(f);
2404 
2405  if( den != NULL ) // ?? / ?? ?
2406  {
2407  assume( p_IsConstant(den, R) );
2408  assume( pNext(den) == NULL );
2409 
2410  if( d == NULL )
2411  d = n_Copy(pGetCoeff(den), Q);
2412  else
2413  {
2414  number g = n_NormalizeHelper(d, pGetCoeff(den), Q);
2415  n_Delete(&d, Q); d = g;
2416  }
2417  }
2418  }
2419 
2420  if( d != NULL )
2421  {
2422  numberCollectionEnumerator.Reset();
2423  while (numberCollectionEnumerator.MoveNext() )
2424  {
2425  number &n = numberCollectionEnumerator.Current();
2426  fraction f = (fraction)n;
2427 
2428  assume( f != NULL );
2429 
2430  const poly den = DEN(f);
2431 
2432  if( den == NULL ) // ?? / 1 ?
2433  NUM(f) = p_Mult_nn(NUM(f), d, R);
2434  else
2435  {
2436  assume( p_IsConstant(den, R) );
2437  assume( pNext(den) == NULL );
2438 
2439  number ddd = n_Div(d, pGetCoeff(den), Q); // but be an integer now!!!
2440  NUM(f) = p_Mult_nn(NUM(f), ddd, R);
2441  n_Delete(&ddd, Q);
2442 
2443  p_Delete(&DEN(f), R);
2444  DEN(f) = NULL; // TODO: check if this is needed!?
2445  }
2446 
2447  assume( DEN(f) == NULL );
2448  }
2449 
2450  NUM((fraction)c) = p_Mult_nn(NUM((fraction)c), d, R);
2451  n_Delete(&d, Q);
2452  }
2453 
2454 
2455  ntTest(c);
2456 }
2457 
2458 static number ntChineseRemainder(number *x, number *q,int rl, BOOLEAN /*sym*/,CFArray &inv_cache,const coeffs cf)
2459 {
2460  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
2461 
2462  poly *P=(poly*)omAlloc(rl*sizeof(poly*));
2463  number *X=(number *)omAlloc(rl*sizeof(number));
2464 
2465  int i;
2466 
2467  for(i=0;i<rl;i++) P[i]=p_Copy(NUM((fraction)(x[i])),cf->extRing);
2468  NUM(result)=p_ChineseRemainder(P,X,q,rl,inv_cache,cf->extRing);
2469 
2470  for(i=0;i<rl;i++)
2471  {
2472  P[i]=p_Copy(DEN((fraction)(x[i])),cf->extRing);
2473  if (P[i]==NULL) P[i]=p_One(cf->extRing);
2474  }
2475  DEN(result)=p_ChineseRemainder(P,X,q,rl,inv_cache,cf->extRing);
2476 
2477  omFreeSize(X,rl*sizeof(number));
2478  omFreeSize(P,rl*sizeof(poly*));
2479  if (p_IsConstant(DEN(result), ntRing)
2480  && n_IsOne(pGetCoeff(DEN(result)), ntCoeffs))
2481  {
2482  p_Delete(&DEN(result),ntRing);
2483  }
2484  ntTest((number)result);
2485  return ((number)result);
2486 }
2487 
2488 static number ntFarey(number p, number n, const coeffs cf)
2489 {
2490  // n is really a bigint
2491  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
2492  NUM(result)=p_Farey(p_Copy(NUM((fraction)p),cf->extRing),n,cf->extRing);
2493  DEN(result)=p_Farey(p_Copy(DEN((fraction)p),cf->extRing),n,cf->extRing);
2494  ntTest((number)result);
2495  return ((number)result);
2496 }
2497 
2498 BOOLEAN ntInitChar(coeffs cf, void * infoStruct)
2499 {
2500 
2501  assume( infoStruct != NULL );
2502 
2503  TransExtInfo *e = (TransExtInfo *)infoStruct;
2504 
2505  assume( e->r != NULL); // extRing;
2506  assume( e->r->cf != NULL); // extRing->cf;
2507  assume( e->r->qideal == NULL );
2508 
2509  assume( cf != NULL );
2510  assume(getCoeffType(cf) == n_transExt); // coeff type;
2511 
2512  ring R = e->r;
2513  assume(R != NULL);
2514 
2515  R->ref ++; // increase the ref.counter for the ground poly. ring!
2516 
2517  cf->extRing = R;
2518  /* propagate characteristic up so that it becomes
2519  directly accessible in cf: */
2520  cf->ch = R->cf->ch;
2521 
2522  cf->is_field=TRUE;
2523  cf->is_domain=TRUE;
2524  cf->rep=n_rep_rat_fct;
2525 
2526  cf->factoryVarOffset = R->cf->factoryVarOffset + rVar(R);
2527 
2528  cf->cfCoeffString = naCoeffString; // FIXME? TODO? // extern char* naCoeffString(const coeffs r);
2529  cf->cfCoeffName = naCoeffName; // FIXME? TODO? // extern char* naCoeffString(const coeffs r);
2530 
2531  cf->cfGreaterZero = ntGreaterZero;
2532  cf->cfGreater = ntGreater;
2533  cf->cfEqual = ntEqual;
2534  cf->cfIsZero = ntIsZero;
2535  cf->cfIsOne = ntIsOne;
2536  cf->cfIsMOne = ntIsMOne;
2537  cf->cfInit = ntInit;
2538  cf->cfFarey = ntFarey;
2539  cf->cfChineseRemainder = ntChineseRemainder;
2540  cf->cfInt = ntInt;
2541  cf->cfInpNeg = ntNeg;
2542  cf->cfAdd = ntAdd;
2543  cf->cfSub = ntSub;
2544  cf->cfMult = ntMult;
2545  cf->cfDiv = ntDiv;
2546  cf->cfExactDiv = ntDiv;
2547  cf->cfPower = ntPower;
2548  cf->cfCopy = ntCopy;
2549  cf->cfWriteLong = ntWriteLong;
2550  cf->cfRead = ntRead;
2551  cf->cfNormalize = ntNormalize;
2552  cf->cfDelete = ntDelete;
2553  cf->cfSetMap = ntSetMap;
2554  cf->cfGetDenom = ntGetDenom;
2555  cf->cfGetNumerator = ntGetNumerator;
2556  //cf->cfRePart = ntCopy;
2557  //cf->cfImPart = ntImPart;
2558  cf->cfCoeffWrite = ntCoeffWrite;
2559 #ifdef LDEBUG
2560  cf->cfDBTest = ntDBTest;
2561 #endif
2562  //cf->cfGcd = ntGcd_dummy;
2563  cf->cfSubringGcd = ntGcd;
2564  cf->cfNormalizeHelper = ntNormalizeHelper;
2565  cf->cfSize = ntSize;
2566  cf->nCoeffIsEqual = ntCoeffIsEqual;
2567  cf->cfInvers = ntInvers;
2568  cf->cfKillChar = ntKillChar;
2569 
2570  if( rCanShortOut(ntRing) )
2571  cf->cfWriteShort = ntWriteShort;
2572  else
2573  cf->cfWriteShort = ntWriteLong;
2574 
2575  cf->convFactoryNSingN =ntConvFactoryNSingN;
2576  cf->convSingNFactoryN =ntConvSingNFactoryN;
2577  cf->cfParDeg = ntParDeg;
2578 
2579  cf->iNumberOfParameters = rVar(R);
2580  cf->pParameterNames = (const char**)R->names;
2581  cf->cfParameter = ntParameter;
2582  cf->has_simple_Inverse= FALSE;
2583  /* cf->has_simple_Alloc= FALSE; */
2584 
2585 
2586  if( nCoeff_is_Q(R->cf) )
2587  cf->cfClearContent = ntClearContent;
2588 
2589  cf->cfClearDenominators = ntClearDenominators;
2590 
2591  return FALSE;
2592 }
2593 
2595 template class IEnumerator<snumber*>;
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
static FORCE_INLINE BOOLEAN n_Greater(number a, number b, const coeffs r)
ordered fields: TRUE iff &#39;a&#39; is larger than &#39;b&#39;; in Z/pZ: TRUE iff la > lb, where la and lb are the l...
Definition: coeffs.h:515
static FORCE_INLINE number n_GetNumerator(number &n, const coeffs r)
return the numerator of n (if elements of r are by nature not fractional, result is n) ...
Definition: coeffs.h:612
static FORCE_INLINE number n_Gcd(number a, number b, const coeffs r)
in Z: return the gcd of &#39;a&#39; and &#39;b&#39; in Z/nZ, Z/2^kZ: computed as in the case Z in Z/pZ...
Definition: coeffs.h:690
const CanonicalForm int s
Definition: facAbsFact.cc:55
poly p_Diff(poly a, int k, const ring r)
Definition: p_polys.cc:1851
#define BOUND_COMPLEXITY
maximum complexity of a number
Definition: transext.cc:65
poly singclap_gcd_r(poly f, poly g, const ring r)
Definition: clapsing.cc:52
poly singclap_gcd_and_divide(poly &f, poly &g, const ring r)
clears denominators of f and g, divides by gcd(f,g)
Definition: clapsing.cc:105
static BOOLEAN ntIsMOne(number a, const coeffs cf)
Definition: transext.cc:666
static void ntNormalizeDen(fraction result, const ring R)
Definition: transext.cc:1095
static BOOLEAN ntDBTest(number a, const char *f, const int l, const coeffs r)
Definition: transext.cc:141
static BOOLEAN p_LmIsConstantComp(const poly p, const ring r)
Definition: p_polys.h:932
number ntDiff(number a, number d, const coeffs cf)
Definition: transext.cc:887
const poly a
Definition: syzextra.cc:212
omBin_t * omBin
Definition: omStructs.h:12
void PrintLn()
Definition: reporter.cc:310
#define Print
Definition: emacs.cc:83
static FORCE_INLINE BOOLEAN nCoeff_is_Zp(const coeffs r)
Definition: coeffs.h:834
poly prCopyR(poly p, ring src_r, ring dest_r)
Definition: prCopy.cc:36
char * naCoeffName(const coeffs r)
Definition: algext.cc:1363
static poly convert(const number &n)
Definition: transext.cc:2217
CanonicalForm num(const CanonicalForm &f)
loop
Definition: myNF.cc:98
used for all transcendental extensions, i.e., the top-most extension in an extension tower is transce...
Definition: coeffs.h:39
number nlModP(number q, const coeffs, const coeffs Zp)
Definition: longrat.cc:1440
#define DIFF_COMPLEXITY
complexity increase due to * and /
Definition: transext.cc:64
static BOOLEAN ntIsOne(number a, const coeffs cf)
Definition: transext.cc:657
void p_String0Long(const poly p, ring lmRing, ring tailRing)
print p in a long way
Definition: polys0.cc:116
#define FALSE
Definition: auxiliary.h:94
static FORCE_INLINE BOOLEAN nlIsInteger(number q, const coeffs r)
Definition: longrat.h:102
return P p
Definition: myNF.cc:203
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the one element.
Definition: coeffs.h:472
poly p_NSet(number n, const ring r)
returns the poly representing the number n, destroys n
Definition: p_polys.cc:1442
number ndCopyMap(number a, const coeffs aRing, const coeffs r)
Definition: numbers.cc:244
static void ntPower(number a, int exp, number *b, const coeffs cf)
Definition: transext.cc:1227
static void definiteGcdCancellation(number a, const coeffs cf, BOOLEAN simpleTestsHaveAlreadyBeenPerformed)
modifies a
Definition: transext.cc:1380
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
static BOOLEAN ntIsZero(number a, const coeffs cf)
Definition: transext.cc:294
rational (GMP) numbers
Definition: coeffs.h:31
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:542
static FORCE_INLINE BOOLEAN nCoeff_is_Q_or_BI(const coeffs r)
Definition: coeffs.h:846
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
#define ntTest(a)
Definition: transext.cc:77
{p < 2^31}
Definition: coeffs.h:30
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:583
poly singclap_gcd(poly f, poly g, const ring r)
destroys f and g
Definition: clapsing.cc:264
(), see rinteger.h, new impl.
Definition: coeffs.h:112
static FORCE_INLINE BOOLEAN nCoeff_has_simple_inverse(const coeffs r)
TRUE, if the computation of the inverse is fast, i.e. prefer leading coeff. 1 over content...
Definition: coeffs.h:919
poly p_Div_nn(poly p, const number n, const ring r)
Definition: p_polys.cc:1474
#define COM(f)
Definition: transext.cc:70
factory&#39;s main class
Definition: canonicalform.h:75
#define TRUE
Definition: auxiliary.h:98
static number ntFarey(number p, number n, const coeffs cf)
Definition: transext.cc:2488
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1430
static FORCE_INLINE void n_Normalize(number &n, const coeffs r)
inplace-normalization of n; produces some canonical representation of n;
Definition: coeffs.h:582
void * ADDRESS
Definition: auxiliary.h:115
static number ntCopyMap(number a, const coeffs cf, const coeffs dst)
Definition: transext.cc:1879
g
Definition: cfModGcd.cc:4031
void WerrorS(const char *s)
Definition: feFopen.cc:24
int k
Definition: cfEzgcd.cc:93
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:721
(fraction), see transext.h
Definition: coeffs.h:114
nMapFunc ntSetMap(const coeffs src, const coeffs dst)
Get a mapping function from src into the domain of this type (n_transExt)
Definition: transext.cc:2065
void p_Norm(poly p1, const ring r)
Definition: p_polys.cc:3619
#define Q
Definition: sirandom.c:25
static number ntCopy(number a, const coeffs cf)
Definition: transext.cc:360
static FORCE_INLINE BOOLEAN nCoeff_is_Q(const coeffs r)
Definition: coeffs.h:840
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy ...
Definition: monomials.h:51
char * naCoeffString(const coeffs r)
Definition: algext.cc:1340
poly singclap_pdivide(poly f, poly g, const ring r)
Definition: clapsing.cc:534
static BOOLEAN ntGreaterZero(number a, const coeffs cf)
Definition: transext.cc:784
#define omAlloc(size)
Definition: omAllocDecl.h:210
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:407
poly p_Sub(poly p1, poly p2, const ring r)
Definition: p_polys.cc:1943
static coeffs nCoeff_bottom(const coeffs r, int &height)
Definition: transext.cc:280
static BOOLEAN rCanShortOut(const ring r)
Definition: ring.h:577
static number ntConvFactoryNSingN(const CanonicalForm n, const coeffs cf)
Definition: transext.cc:2147
static void ntWriteShort(number a, const coeffs cf)
Definition: transext.cc:1557
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:804
static number ntGcd(number a, number b, const coeffs cf)
Definition: transext.cc:1721
poly prMapR(poly src, nMapFunc nMap, ring src_r, ring dest_r)
Definition: prCopy.cc:47
static BOOLEAN p_LmIsConstant(const poly p, const ring r)
Definition: p_polys.h:949
#define pIter(p)
Definition: monomials.h:44
poly res
Definition: myNF.cc:322
static int ntParDeg(number a, const coeffs cf)
Definition: transext.cc:2168
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of &#39;a&#39; and &#39;b&#39;, i.e., a*b
Definition: coeffs.h:640
virtual void Reset()=0
Sets the enumerator to its initial position: -1, which is before the first element in the collection...
const char * p_Read(const char *st, poly &rc, const ring r)
Definition: p_polys.cc:1347
static number ntMap00(number a, const coeffs src, const coeffs dst)
Definition: transext.cc:1825
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:945
static void ntClearDenominators(ICoeffsEnumerator &numberCollectionEnumerator, number &c, const coeffs cf)
Definition: transext.cc:2314
const ring r
Definition: syzextra.cc:208
Coefficient rings, fields and other domains suitable for Singular polynomials.
static void ntNormalize(number &a, const coeffs cf)
Definition: transext.cc:1592
poly p_Farey(poly p, number N, const ring r)
Definition: p_polys.cc:61
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:551
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
poly p_One(const ring r)
Definition: p_polys.cc:1312
Concrete implementation of enumerators over polynomials.
static number ntAdd(number a, number b, const coeffs cf)
Definition: transext.cc:944
static void ntWriteLong(number a, const coeffs cf)
Definition: transext.cc:1532
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent : the integer VarOffset encodes:
Definition: p_polys.h:464
This is a polynomial enumerator for simple iteration over coefficients of polynomials.
static long ntInt(number &a, const coeffs cf)
Definition: transext.cc:761
number ntInit(long i, const coeffs cf)
Definition: transext.cc:692
#define assume(x)
Definition: mod2.h:394
static BOOLEAN p_IsConstant(const poly p, const ring r)
Definition: p_polys.h:1876
static void ntKillChar(coeffs cf)
Definition: transext.cc:2142
The main handler for Singular numbers which are suitable for Singular polynomials.
static number ntMapZ0(number a, const coeffs src, const coeffs dst)
Definition: transext.cc:1849
Templated enumerator interface for simple iteration over a generic collection of T&#39;s.
Definition: Enumerator.h:124
static poly pp_Mult_qq(poly p, poly q, const ring r)
Definition: p_polys.h:1070
void StringAppendS(const char *st)
Definition: reporter.cc:107
#define A
Definition: sirandom.c:23
poly convFactoryPSingP(const CanonicalForm &f, const ring r)
Definition: clapconv.cc:41
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition: coeffs.h:73
static BOOLEAN ntEqual(number a, number b, const coeffs cf)
Definition: transext.cc:314
const ring R
Definition: DebugPrint.cc:36
virtual reference Current()=0
Gets the current element in the collection (read and write).
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:742
static void ntDelete(number *a, const coeffs cf)
Definition: transext.cc:301
All the auxiliary stuff.
static FORCE_INLINE number n_Invers(number a, const coeffs r)
return the multiplicative inverse of &#39;a&#39;; raise an error if &#39;a&#39; is not invertible ...
Definition: coeffs.h:568
int m
Definition: cfEzgcd.cc:119
static number ntMapUP(number a, const coeffs src, const coeffs dst)
Definition: transext.cc:2043
static FORCE_INLINE number n_InpNeg(number n, const coeffs r)
in-place negation of n MUST BE USED: n = n_InpNeg(n) (no copy is returned)
Definition: coeffs.h:561
static BOOLEAN ntCoeffIsEqual(const coeffs cf, n_coeffType n, void *param)
Definition: transext.cc:1611
#define NUMIS1(f)
TRUE iff num. represents 1.
Definition: transext.cc:68
struct for passing initialization parameters to naInitChar
Definition: transext.h:92
const char *const nDivBy0
Definition: numbers.h:83
FILE * f
Definition: checklibs.c:9
static void ntCoeffWrite(const coeffs cf, BOOLEAN details)
Definition: transext.cc:846
static BOOLEAN p_IsOne(const poly p, const ring R)
either poly(1) or gen(k)?!
Definition: p_polys.h:1884
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:284
static char * rRingVar(short i, const ring r)
Definition: ring.h:568
static poly p_Mult_nn(poly p, number n, const ring r)
Definition: p_polys.h:895
static const char * ntRead(const char *s, number *a, const coeffs cf)
Definition: transext.cc:1582
static poly p_LmFreeAndNext(poly p, ring)
Definition: p_polys.h:698
CanonicalForm factor
Definition: facAbsFact.cc:101
static unsigned pLength(poly a)
Definition: p_polys.h:189
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the zero element.
Definition: coeffs.h:468
BOOLEAN rEqual(ring r1, ring r2, BOOLEAN qr)
returns TRUE, if r1 equals r2 FALSE, otherwise Equality is determined componentwise, if qr == 1, then qrideal equality is tested, as well
Definition: ring.cc:1627
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:725
go into polynomials over an alg. extension recursively
static FORCE_INLINE n_coeffType getCoeffType(const coeffs r)
Returns the type of coeffs domain.
Definition: coeffs.h:425
static number ntChineseRemainder(number *x, number *q, int rl, BOOLEAN, CFArray &inv_cache, const coeffs cf)
Definition: transext.cc:2458
BOOLEAN p_EqualPolys(poly p1, poly p2, const ring r)
Definition: p_polys.cc:4359
#define p_Test(p, r)
Definition: p_polys.h:160
static void ntClearContent(ICoeffsEnumerator &numberCollectionEnumerator, number &c, const coeffs cf)
Definition: transext.cc:2225
static number ntNormalizeHelper(number a, number b, const coeffs cf)
Definition: transext.cc:1633
void p_Normalize(poly p, const ring r)
Definition: p_polys.cc:3672
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:843
#define omAlloc0Bin(bin)
Definition: omAllocDecl.h:206
#define omGetSpecBin(size)
Definition: omBin.h:11
(number), see longrat.h
Definition: coeffs.h:111
static void p_ExpVectorDiff(poly pr, poly p1, poly p2, const ring r)
Definition: p_polys.h:1397
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent : VarOffset encodes the position in p->exp
Definition: p_polys.h:483
n_coeffType
Definition: coeffs.h:27
CanonicalForm cf
Definition: cfModGcd.cc:4024
static FORCE_INLINE void n_CoeffWrite(const coeffs r, BOOLEAN details=TRUE)
output the coeff description
Definition: coeffs.h:745
static void heuristicGcdCancellation(number a, const coeffs cf)
forward declarations
Definition: transext.cc:1295
static number ntMult(number a, number b, const coeffs cf)
Definition: transext.cc:1024
#define NULL
Definition: omList.c:10
CanonicalForm convSingPFactoryP(poly p, const ring r)
Definition: clapconv.cc:88
static void handleNestedFractionsOverQ(fraction f, const coeffs cf)
Definition: transext.cc:401
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of &#39;n&#39;
Definition: coeffs.h:455
static number ntParameter(const int iParameter, const coeffs cf)
return the specified parameter as a number in the given trans.ext.
Definition: transext.cc:2177
CanonicalForm den(const CanonicalForm &f)
void rDelete(ring r)
unconditionally deletes fields in r
Definition: ring.cc:450
static number ntMap0P(number a, const coeffs src, const coeffs dst)
Definition: transext.cc:2004
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of &#39;a&#39; and &#39;b&#39;, i.e., a/b; raises an error if &#39;b&#39; is not invertible in r exceptio...
Definition: coeffs.h:619
static int ntSize(number a, const coeffs cf)
Definition: transext.cc:1797
static number ntInvers(number a, const coeffs cf)
Definition: transext.cc:1161
virtual bool MoveNext()=0
Advances the enumerator to the next element of the collection. returns true if the enumerator was suc...
int gcd(int a, int b)
Definition: walkSupport.cc:839
static number ntNeg(number a, const coeffs cf)
this is in-place, modifies a
Definition: transext.cc:679
#define SR_INT
Definition: longrat.h:68
poly p_ChineseRemainder(poly *xx, number *x, number *q, int rl, CFArray &inv_cache, const ring R)
Definition: p_polys.cc:94
Variable x
Definition: cfModGcd.cc:4023
static FORCE_INLINE number n_GetDenom(number &n, const coeffs r)
return the denominator of n (if elements of r are by nature not fractional, result is 1) ...
Definition: coeffs.h:607
#define pNext(p)
Definition: monomials.h:43
#define ntCoeffs
Definition: transext.cc:87
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:228
#define p_GetCoeff(p, r)
Definition: monomials.h:57
static number ntMapP0(number a, const coeffs src, const coeffs dst)
Definition: transext.cc:1863
static FORCE_INLINE number n_SubringGcd(number a, number b, const coeffs r)
Definition: coeffs.h:692
static number ntDiv(number a, number b, const coeffs cf)
Definition: transext.cc:1119
static FORCE_INLINE BOOLEAN nCoeff_is_Extension(const coeffs r)
Definition: coeffs.h:863
int ntIsParam(number m, const coeffs cf)
if m == var(i)/1 => return i,
Definition: transext.cc:2199
static number ntGetDenom(number &a, const coeffs cf)
TODO: normalization of a!?
Definition: transext.cc:555
p exp[i]
Definition: DebugPrint.cc:39
static poly p_Neg(poly p, const ring r)
Definition: p_polys.h:1013
static number ntGenAlg(number a, const coeffs cf, const coeffs dst)
Definition: transext.cc:1994
#define SR_HDL(A)
Definition: tgb.cc:35
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:459
#define ntRing
Definition: transext.cc:81
void p_wrp(poly p, ring lmRing, ring tailRing)
Definition: polys0.cc:237
static FORCE_INLINE BOOLEAN n_IsMOne(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the additive inverse of the one element, i.e. -1.
Definition: coeffs.h:476
static number ntSub(number a, number b, const coeffs cf)
Definition: transext.cc:985
void p_Write(poly p, ring lmRing, ring tailRing)
Definition: polys0.cc:206
static CanonicalForm ntConvSingNFactoryN(number n, BOOLEAN, const coeffs cf)
Definition: transext.cc:2159
static FORCE_INLINE BOOLEAN n_GreaterZero(number n, const coeffs r)
ordered fields: TRUE iff &#39;n&#39; is positive; in Z/pZ: TRUE iff 0 < m <= roundedBelow(p/2), where m is the long representing n in C: TRUE iff (Im(n) != 0 and Im(n) >= 0) or (Im(n) == 0 and Re(n) >= 0) in K(a)/<p(a)>: TRUE iff (n != 0 and (LC(n) > 0 or deg(n) > 0)) in K(t_1, ..., t_n): TRUE iff (LC(numerator(n) is a constant and > 0) or (LC(numerator(n) is not a constant) in Z/2^kZ: TRUE iff 0 < n <= 2^(k-1) in Z/mZ: TRUE iff the internal mpz is greater than zero in Z: TRUE iff n > 0
Definition: coeffs.h:498
#define ADD_COMPLEXITY
complexity increase due to + and -
Definition: transext.cc:62
kBucketDestroy & P
Definition: myNF.cc:191
polyrec * poly
Definition: hilb.h:10
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:877
static BOOLEAN ntGreater(number a, number b, const coeffs cf)
Definition: transext.cc:794
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
Rational pow(const Rational &a, int e)
Definition: GMPrat.cc:418
static Poly * h
Definition: janet.cc:978
int BOOLEAN
Definition: auxiliary.h:85
static number ntGenMap(number a, const coeffs cf, const coeffs dst)
Definition: transext.cc:1908
const poly b
Definition: syzextra.cc:213
int p_Var(poly m, const ring r)
Definition: p_polys.cc:4503
static number ntCopyAlg(number a, const coeffs cf, const coeffs dst)
Definition: transext.cc:1987
#define MULT_COMPLEXITY
complexity increase due to * and /
Definition: transext.cc:63
static number ntGetNumerator(number &a, const coeffs cf)
TODO: normalization of a!?
Definition: transext.cc:494
poly p_ISet(long i, const ring r)
returns the poly representing the integer i
Definition: p_polys.cc:1296
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1020
void p_String0Short(const poly p, ring lmRing, ring tailRing)
print p in a short way, if possible
Definition: polys0.cc:97
return result
Definition: facAbsBiFact.cc:76
int l
Definition: cfEzgcd.cc:94
const CanonicalForm const CanonicalForm const CanonicalForm const CanonicalForm & cand
Definition: cfModGcd.cc:69
static FORCE_INLINE void n_ClearDenominators(ICoeffsEnumerator &numberCollectionEnumerator, number &d, const coeffs r)
(inplace) Clears denominators on a collection of numbers number d is the LCM of all the coefficient d...
Definition: coeffs.h:952
static number ntMapPP(number a, const coeffs src, const coeffs dst)
Definition: transext.cc:2028
BOOLEAN ntInitChar(coeffs cf, void *infoStruct)
Initialize the coeffs object.
Definition: transext.cc:2498
omBin fractionObjectBin
Definition: transext.cc:90