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