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