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