cfNewtonPolygon.cc
Go to the documentation of this file.
1 /*****************************************************************************\
2  * Computer Algebra System SINGULAR
3 \*****************************************************************************/
4 /** @file cfNewtonPolygon.cc
5  *
6  * This file provides functions to compute the Newton polygon of a bivariate
7  * polynomial
8  *
9  * @author Martin Lee
10  *
11  **/
12 /*****************************************************************************/
13 
14 
15 #include "config.h"
16 
17 
18 #include "cf_assert.h"
19 
20 #include <stdlib.h>
21 
22 #include "canonicalform.h"
23 #include "cf_iter.h"
24 #include "cf_algorithm.h"
25 #include "cf_primes.h"
26 #include "cf_reval.h"
27 #include "cf_factory.h"
28 #include "gfops.h"
29 #include "cfNewtonPolygon.h"
31 
32 static
33 void translate (int** points, int* point, int sizePoints) //make point to 0
34 {
35  for (int i= 0; i < sizePoints; i++)
36  {
37  points[i] [0] -= point [0];
38  points[i] [1] -= point [1];
39  }
40 }
41 
42 static
43 int smallestPointIndex (int** points, int sizePoints)
44 {
45  int min= 0;
46  for (int i= 1; i < sizePoints; i++)
47  {
48  if (points[i][0] < points[min][0] ||
49  (points[i] [0] == points[min] [0] && points[i] [1] < points[min] [1]))
50  min= i;
51  }
52  return min;
53 }
54 
55 static
56 void swap (int** points, int i, int j)
57 {
58  int* tmp= points[i];
59  points[i]= points[j];
60  points[j]= tmp;
61 }
62 
63 static
64 bool isLess (int* point1, int* point2)
65 {
66  long area= point1[0]*point2[1]- point1[1]*point2[0];
67  if (area > 0) return true;
68  if (area == 0)
69  {
70  return (abs (point1[0]) + abs (point1[1]) >
71  abs (point2[0]) + abs (point2[1]));
72  }
73  return false;
74 }
75 
76 static
77 void quickSort (int lo, int hi, int** points)
78 {
79  int i= lo, j= hi;
80  int* point= new int [2];
81  point [0]= points [(lo+hi)/2] [0];
82  point [1]= points [(lo+hi)/2] [1];
83  while (i <= j)
84  {
85  while (isLess (points [i], point) && i < hi) i++;
86  while (isLess (point, points[j]) && j > lo) j--;
87  if (i <= j)
88  {
89  swap (points, i, j);
90  i++;
91  j--;
92  }
93  }
94  delete [] point;
95  if (lo < j) quickSort (lo, j, points);
96  if (i < hi) quickSort (i, hi, points);
97 }
98 
99 static
100 void sort (int** points, int sizePoints)
101 {
102  quickSort (1, sizePoints - 1, points);
103 }
104 
105 // check whether p2 is convex
106 static
107 bool isConvex (int* point1, int* point2, int* point3)
108 {
109  long relArea= (point1[0] - point2[0])*(point3[1] - point2[1]) -
110  (point1[1] - point2[1])*(point3[0] - point2[0]);
111  if (relArea < 0)
112  return true;
113  if (relArea == 0)
114  {
115  return !(abs (point1[0] - point3[0]) + abs (point1[1] - point3[1]) >=
116  (abs (point2[0] - point1[0]) + abs (point2[1] - point1[1]) +
117  abs (point2[0] - point3[0]) + abs (point2[1] - point3[1])));
118  }
119  return false;
120 }
121 
122 static
123 bool isConvex (int** points, int i)
124 {
125  return isConvex (points[i - 1], points [i], points [i + 1]);
126 }
127 
128 int grahamScan (int** points, int sizePoints)
129 {
130  swap (points, 0, smallestPointIndex (points, sizePoints));
131  int * minusPoint= new int [2];
132  minusPoint [0]= points[0] [0];
133  minusPoint [1]= points[0] [1];
134  translate (points, minusPoint, sizePoints);
135  sort (points, sizePoints);
136  minusPoint[0]= - minusPoint[0];
137  minusPoint[1]= - minusPoint[1];
138  translate (points, minusPoint, sizePoints); //reverse translation
139  delete [] minusPoint;
140  int i= 3, k= 3;
141  while (k < sizePoints)
142  {
143  swap (points, i, k);
144  while (!isConvex (points, i - 1))
145  {
146  swap (points, i - 1, i);
147  i--;
148  }
149  k++;
150  i++;
151  }
152  if (i + 1 <= sizePoints || i == sizePoints)
153  {
154  long relArea=
155  (points [i-2][0] - points [i-1][0])*(points [0][1] - points [i-1][1])-
156  (points [i-2][1] - points [i-1][1])*(points [0][0] - points [i-1][0]);
157  if (relArea == 0)
158  {
159  if (abs (points [i-2][0] - points [0][0]) +
160  abs (points [i-2][1] - points [0][1]) >=
161  abs (points [i-1][0] - points [i-2][0]) +
162  abs (points [i-1][1] - points [i-2][1]) +
163  abs (points [i-1][0] - points [0][0]) +
164  abs (points [i-1][1] - points [0][1]))
165  i--;
166  }
167  }
168  return i;
169 }
170 
171 //points[i] [0] is x-coordinate, points [i] [1] is y-coordinate
172 int polygon (int** points, int sizePoints)
173 {
174  if (sizePoints < 3) return sizePoints;
175  return grahamScan (points, sizePoints);
176 }
177 
178 static
179 int* getDegrees (const CanonicalForm& F, int& sizeOfOutput)
180 {
181  if (F.inCoeffDomain())
182  {
183  int* result= new int [1];
184  result [0]= 0;
185  sizeOfOutput= 1;
186  return result;
187  }
188  sizeOfOutput= size (F);
189  int* result= new int [sizeOfOutput];
190  int j= 0;
191  for (CFIterator i= F; i.hasTerms(); i++, j++)
192  result [j]= i.exp();
193  return result;
194 }
195 
196 //get points in Z^2 whose convex hull is the Newton polygon
197 int ** getPoints (const CanonicalForm& F, int& n)
198 {
199  n= size (F);
200  int ** points= new int* [n];
201  for (int i= 0; i < n; i++)
202  points [i]= new int [2];
203 
204  int j= 0;
205  int * buf;
206  int bufSize;
207  if (F.isUnivariate() && F.level() == 1)
208  {
209  for (CFIterator i= F; i.hasTerms(); i++, j++)
210  {
211  points [j] [0]= i.exp();
212  points [j] [1]= 0;
213  }
214  return points;
215  }
216  for (CFIterator i= F; i.hasTerms(); i++)
217  {
218  buf= getDegrees (i.coeff(), bufSize);
219  for (int k= 0; k < bufSize; k++, j++)
220  {
221  points [j] [0]= i.exp();
222  points [j] [1]= buf [k];
223  }
224  delete [] buf;
225  }
226  return points;
227 }
228 
229 int **
230 merge (int ** points1, int sizePoints1, int ** points2, int sizePoints2,
231  int& sizeResult)
232 {
233  int i, j;
234  sizeResult= sizePoints1+sizePoints2;
235  for (i= 0; i < sizePoints1; i++)
236  {
237  for (j= 0; j < sizePoints2; j++)
238  {
239  if (points1[i][0] != points2[j][0])
240  continue;
241  else
242  {
243  if (points1[i][1] != points2[j][1])
244  continue;
245  else
246  {
247  points2[j][0]= -1;
248  points2[j][1]= -1;
249  sizeResult--;
250  }
251  }
252  }
253  }
254  if (sizeResult == 0)
255  return points1;
256 
257  int ** result= new int *[sizeResult];
258  for (i= 0; i < sizeResult; i++)
259  result [i]= new int [2];
260 
261  int k= 0;
262  for (i= 0; i < sizePoints1; i++, k++)
263  {
264  result[k][0]= points1[i][0];
265  result[k][1]= points1[i][1];
266  }
267  for (i= 0; i < sizePoints2; i++)
268  {
269  if (points2[i][0] < 0)
270  continue;
271  else
272  {
273  result[k][0]= points2[i][0];
274  result[k][1]= points2[i][1];
275  k++;
276  }
277  }
278  return result;
279 }
280 
281 // assumes a bivariate poly as input
282 int ** newtonPolygon (const CanonicalForm& F, int& sizeOfNewtonPoly)
283 {
284  int sizeF= size (F);
285  int ** points= new int* [sizeF];
286  for (int i= 0; i < sizeF; i++)
287  points [i]= new int [2];
288  int j= 0;
289  int * buf;
290  int bufSize;
291  for (CFIterator i= F; i.hasTerms(); i++)
292  {
293  buf= getDegrees (i.coeff(), bufSize);
294  for (int k= 0; k < bufSize; k++, j++)
295  {
296  points [j] [0]= i.exp();
297  points [j] [1]= buf [k];
298  }
299  delete [] buf;
300  }
301 
302  int n= polygon (points, sizeF);
303 
304  int ** result= new int* [n];
305  for (int i= 0; i < n; i++)
306  {
307  result [i]= new int [2];
308  result [i] [0]= points [i] [0];
309  result [i] [1]= points [i] [1];
310  }
311 
312  sizeOfNewtonPoly= n;
313  for (int i= 0; i < sizeF; i++)
314  delete [] points[i];
315  delete [] points;
316 
317  return result;
318 }
319 
320 // assumes a bivariate polys as input
321 int ** newtonPolygon (const CanonicalForm& F, const CanonicalForm& G,
322  int& sizeOfNewtonPoly)
323 {
324  int sizeF= size (F);
325  int ** pointsF= new int* [sizeF];
326  for (int i= 0; i < sizeF; i++)
327  pointsF [i]= new int [2];
328  int j= 0;
329  int * buf;
330  int bufSize;
331  for (CFIterator i= F; i.hasTerms(); i++)
332  {
333  buf= getDegrees (i.coeff(), bufSize);
334  for (int k= 0; k < bufSize; k++, j++)
335  {
336  pointsF [j] [0]= i.exp();
337  pointsF [j] [1]= buf [k];
338  }
339  delete [] buf;
340  }
341 
342  int sizeG= size (G);
343  int ** pointsG= new int* [sizeG];
344  for (int i= 0; i < sizeG; i++)
345  pointsG [i]= new int [2];
346  j= 0;
347  for (CFIterator i= G; i.hasTerms(); i++)
348  {
349  buf= getDegrees (i.coeff(), bufSize);
350  for (int k= 0; k < bufSize; k++, j++)
351  {
352  pointsG [j] [0]= i.exp();
353  pointsG [j] [1]= buf [k];
354  }
355  delete [] buf;
356  }
357 
358  int sizePoints;
359  int ** points= merge (pointsF, sizeF, pointsG, sizeG, sizePoints);
360 
361  int n= polygon (points, sizePoints);
362 
363  int ** result= new int* [n];
364  for (int i= 0; i < n; i++)
365  {
366  result [i]= new int [2];
367  result [i] [0]= points [i] [0];
368  result [i] [1]= points [i] [1];
369  }
370 
371  sizeOfNewtonPoly= n;
372  for (int i= 0; i < sizeF; i++)
373  delete [] pointsF[i];
374  delete [] pointsF;
375  for (int i= 0; i < sizeG; i++)
376  delete [] pointsG[i];
377  delete [] pointsG;
378 
379  return result;
380 }
381 
382 // assumes first sizePoints entries of points form a Newton polygon
383 bool isInPolygon (int ** points, int sizePoints, int* point)
384 {
385  int ** buf= new int* [sizePoints + 1];
386  for (int i= 0; i < sizePoints; i++)
387  {
388  buf [i]= new int [2];
389  buf [i] [0]= points [i] [0];
390  buf [i] [1]= points [i] [1];
391  }
392  buf [sizePoints]= new int [2];
393  buf [sizePoints] [0]= point [0];
394  buf [sizePoints] [1]= point [1];
395  int sizeBuf= sizePoints + 1;
396 
397  swap (buf, 0, smallestPointIndex (buf, sizeBuf));
398  int * minusPoint= new int [2];
399  minusPoint [0]= buf[0] [0];
400  minusPoint [1]= buf[0] [1];
401  translate (buf, minusPoint, sizeBuf);
402  sort (buf, sizeBuf);
403  minusPoint[0]= - minusPoint[0];
404  minusPoint[1]= - minusPoint[1];
405  translate (buf, minusPoint, sizeBuf); //reverse translation
406  delete [] minusPoint;
407 
408  if (buf [0] [0] == point [0] && buf [0] [1] == point [1])
409  {
410  for (int i= 0; i < sizeBuf; i++)
411  delete [] buf[i];
412  delete [] buf;
413  return false;
414  }
415 
416  for (int i= 1; i < sizeBuf-1; i++)
417  {
418  if (buf [i] [0] == point [0] && buf [i] [1] == point [1])
419  {
420  bool result= !isConvex (buf, i);
421  for (int i= 0; i < sizeBuf; i++)
422  delete [] buf [i];
423  delete [] buf;
424  return result;
425  }
426  }
427 
428  if (buf [sizeBuf - 1] [0] == point [0] && buf [sizeBuf-1] [1] == point [1])
429  {
430  buf [1] [0]= point [0];
431  buf [1] [1]= point [1];
432  buf [2] [0]= buf [0] [0];
433  buf [2] [1]= buf [0] [1];
434  buf [0] [0]= buf [sizeBuf-2] [0];
435  buf [0] [1]= buf [sizeBuf-2] [1];
436  bool result= !isConvex (buf, 1);
437  for (int i= 0; i < sizeBuf; i++)
438  delete [] buf [i];
439  delete [] buf;
440  return result;
441  }
442  for (int i= 0; i < sizeBuf; i++)
443  delete [] buf [i];
444  delete [] buf;
445 
446  return false;
447 }
448 
449 void lambda (int** points, int sizePoints)
450 {
451  for (int i= 0; i < sizePoints; i++)
452  points [i] [1]= points [i] [1] - points [i] [0];
453 }
454 
455 void lambdaInverse (int** points, int sizePoints)
456 {
457  for (int i= 0; i < sizePoints; i++)
458  points [i] [1]= points [i] [1] + points [i] [0];
459 }
460 
461 void tau (int** points, int sizePoints, int k)
462 {
463  for (int i= 0; i < sizePoints; i++)
464  points [i] [1]= points [i] [1] + k;
465 }
466 
467 void mu (int** points, int sizePoints)
468 {
469  int tmp;
470  for (int i= 0; i < sizePoints; i++)
471  {
472  tmp= points [i] [0];
473  points [i] [0]= points [i] [1];
474  points [i] [1]= tmp;
475  }
476 }
477 
478 void getMaxMin (int** points, int sizePoints, int& minDiff, int& minSum,
479  int& maxDiff, int& maxSum, int& maxX, int& maxY
480  )
481 {
482  minDiff= points [0] [1] - points [0] [0];
483  minSum= points [0] [1] + points [0] [0];
484  maxDiff= points [0] [1] - points [0] [0];
485  maxSum= points [0] [1] + points [0] [0];
486  maxX= points [0] [1];
487  maxY= points [0] [0];
488  int diff, sum;
489  for (int i= 1; i < sizePoints; i++)
490  {
491  diff= points [i] [1] - points [i] [0];
492  sum= points [i] [1] + points [i] [0];
493  minDiff= tmin (minDiff, diff);
494  minSum= tmin (minSum, sum);
495  maxDiff= tmax (maxDiff, diff);
496  maxSum= tmax (maxSum, sum);
497  maxX= tmax (maxX, points [i] [1]);
498  maxY= tmax (maxY, points [i] [0]);
499  }
500 }
501 
502 void mpz_mat_mul (const mpz_t* N, mpz_t*& M)
503 {
504  mpz_t * tmp= new mpz_t[4];
505 
506  mpz_init_set (tmp[0], N[0]);
507  mpz_mul (tmp[0], tmp[0], M[0]);
508  mpz_addmul (tmp[0], N[1], M[2]);
509 
510  mpz_init_set (tmp[1], N[0]);
511  mpz_mul (tmp[1], tmp[1], M[1]);
512  mpz_addmul (tmp[1], N[1], M[3]);
513 
514  mpz_init_set (tmp[2], N[2]);
515  mpz_mul (tmp[2], tmp[2], M[0]);
516  mpz_addmul (tmp[2], N[3], M[2]);
517 
518  mpz_init_set (tmp[3], N[2]);
519  mpz_mul (tmp[3], tmp[3], M[1]);
520  mpz_addmul (tmp[3], N[3], M[3]);
521 
522  mpz_set (M[0], tmp[0]);
523  mpz_set (M[1], tmp[1]);
524  mpz_set (M[2], tmp[2]);
525  mpz_set (M[3], tmp[3]);
526 
527  mpz_clear (tmp[0]);
528  mpz_clear (tmp[1]);
529  mpz_clear (tmp[2]);
530  mpz_clear (tmp[3]);
531 
532  delete [] tmp;
533 }
534 
535 void mpz_mat_inv (mpz_t*& M)
536 {
537  mpz_t det;
538  mpz_init_set (det, M[0]);
539  mpz_mul (det, det, M[3]);
540  mpz_submul (det, M[1], M[2]);
541 
542  mpz_t tmp;
543  mpz_init_set (tmp, M[0]);
544  mpz_divexact (tmp, tmp, det);
545  mpz_set (M[0], M[3]);
546  mpz_divexact (M[0], M[0], det);
547  mpz_set (M[3], tmp);
548 
549  mpz_neg (M[1], M[1]);
550  mpz_divexact (M[1], M[1], det);
551  mpz_neg (M[2], M[2]);
552  mpz_divexact (M[2], M[2], det);
553 
554  mpz_clear (det);
555  mpz_clear (tmp);
556 }
557 
558 void convexDense(int** points, int sizePoints, mpz_t*& M, mpz_t*& A)
559 {
560  if (sizePoints < 3)
561  {
562  if (sizePoints == 2)
563  {
564  mpz_t u,v,g,maxX,maxY;
565  mpz_init (u);
566  mpz_init (v);
567  mpz_init (g);
568  mpz_init_set_si (maxX,
569  (points[1][1] < points[0][1])?points[0][1]:points[1][1]);
570  mpz_init_set_si (maxY,
571  (points[1][0] < points[0][0])?points[0][0]:points[1][0]);
572  mpz_gcdext (g, u, v, maxX, maxY);
573  if (points [0] [1] != points [0] [0] && points [1] [0] != points [1] [1])
574  {
575  mpz_set (A[0], u);
576  mpz_mul (A[0], A[0], maxX);
577  mpz_set (M[2], maxY);
578  mpz_divexact (M[2], M[2], g);
579  mpz_set (A[1], M[2]);
580  mpz_neg (A[1], A[1]);
581  mpz_mul (A[1], A[1], maxX);
582  mpz_neg (u, u);
583  mpz_set (M[0], u);
584  mpz_set (M[1], v);
585  mpz_set (M[3], maxX);
586  mpz_divexact (M[3], M[3], g);
587  }
588  else
589  {
590  mpz_set (M[0], u);
591  mpz_set (M[1], v);
592  mpz_set (M[2], maxY);
593  mpz_divexact (M[2], M[2], g);
594  mpz_neg (M[2], M[2]);
595  mpz_set (M[3], maxX);
596  mpz_divexact (M[3], M[3], g);
597  }
598  mpz_clear (u);
599  mpz_clear (v);
600  mpz_clear (g);
601  mpz_clear (maxX);
602  mpz_clear (maxY);
603  }
604  else if (sizePoints == 1)
605  {
606  mpz_set_si (M[0], 1);
607  mpz_set_si (M[3], 1);
608  }
609  return;
610  }
611  mpz_set_si (M[0], 1);
612  mpz_set_si (M[3], 1);
613 
614  mpz_t * Mu= new mpz_t[4];
615  mpz_init_set_si (Mu[1], 1);
616  mpz_init_set_si (Mu[2], 1);
617  mpz_init (Mu[0]);
618  mpz_init (Mu[3]);
619 
620  mpz_t * Lambda= new mpz_t[4];
621  mpz_init_set_si (Lambda[0], 1);
622  mpz_init_set_si (Lambda[1], -1);
623  mpz_init_set_si (Lambda[3], 1);
624  mpz_init (Lambda[2]);
625 
626  mpz_t * InverseLambda= new mpz_t[4];
627  mpz_init_set_si (InverseLambda[0], 1);
628  mpz_init_set_si (InverseLambda[1], 1);
629  mpz_init_set_si (InverseLambda[3], 1);
630  mpz_init (InverseLambda[2]);
631 
632  mpz_t tmp;
633  mpz_init (tmp);
634  int minDiff, minSum, maxDiff, maxSum, maxX, maxY, b, d, f, h;
635  getMaxMin(points, sizePoints, minDiff, minSum, maxDiff, maxSum, maxX, maxY);
636  do
637  {
638  if (maxX < maxY)
639  {
640  mu (points, sizePoints);
641 
642  mpz_mat_mul (Mu, M);
643 
644  mpz_set (tmp, A[0]);
645  mpz_set (A[0], A[1]);
646  mpz_set (A[1], tmp);
647  }
648  getMaxMin(points, sizePoints, minDiff, minSum, maxDiff, maxSum, maxX, maxY);
649  b= maxX - maxDiff;
650  d= maxX + maxY - maxSum;
651  f= maxY + minDiff;
652  h= minSum;
653  if (b + f > maxY)
654  {
655  lambda (points, sizePoints);
656  tau (points, sizePoints, maxY - f);
657 
658  mpz_mat_mul (Lambda, M);
659 
660  if (maxY-f > 0)
661  mpz_add_ui (A[0], A[0], maxY-f);
662  else
663  mpz_add_ui (A[0], A[0], f-maxY);
664  maxX= maxX + maxY - b - f;
665  }
666  else if (d + h > maxY)
667  {
668  lambdaInverse (points, sizePoints);
669  tau (points, sizePoints, -h);
670 
671  mpz_mat_mul (InverseLambda, M);
672 
673  if (h < 0)
674  mpz_add_ui (A[0], A[0], -h);
675  else
676  mpz_sub_ui (A[0], A[0], h);
677  maxX= maxX + maxY - d - h;
678  }
679  else
680  {
681  mpz_clear (tmp);
682  mpz_clear (Mu[0]);
683  mpz_clear (Mu[1]);
684  mpz_clear (Mu[2]);
685  mpz_clear (Mu[3]);
686  delete [] Mu;
687 
688  mpz_clear (Lambda[0]);
689  mpz_clear (Lambda[1]);
690  mpz_clear (Lambda[2]);
691  mpz_clear (Lambda[3]);
692  delete [] Lambda;
693 
694  mpz_clear (InverseLambda[0]);
695  mpz_clear (InverseLambda[1]);
696  mpz_clear (InverseLambda[2]);
697  mpz_clear (InverseLambda[3]);
698  delete [] InverseLambda;
699 
700  return;
701  }
702  } while (1);
703 }
704 
706 compress (const CanonicalForm& F, mpz_t*& M, mpz_t*& A, bool computeMA)
707 {
708  int n;
709  int ** newtonPolyg= NULL;
710  if (computeMA)
711  {
712  newtonPolyg= newtonPolygon (F, n);
713  convexDense (newtonPolyg, n, M, A);
714  }
715 
717  Variable x= Variable (1);
718  Variable y= Variable (2);
719 
720  mpz_t expX, expY, minExpX, minExpY;
721  mpz_init (expX);
722  mpz_init (expY);
723  mpz_init (minExpX);
724  mpz_init (minExpY);
725 
726  int k= 0;
727  Variable alpha;
728  mpz_t * exps= new mpz_t [2*size (F)];
729  int exps_maxcount=0;
730  int count= 0;
731  for (CFIterator i= F; i.hasTerms(); i++)
732  {
733  if (i.coeff().inCoeffDomain() && hasFirstAlgVar (i.coeff(), alpha))
734  {
735  mpz_set (expX, A[0]);
736  mpz_set (expY, A[1]);
737  mpz_addmul_ui (expX, M[1], i.exp());
738  mpz_addmul_ui (expY, M[3], i.exp());
739 
740  if (k == 0)
741  {
742  mpz_set (minExpX, expX);
743  mpz_set (minExpY, expY);
744  k= 1;
745  }
746  else
747  {
748  if (mpz_cmp (minExpY, expY) > 0)
749  mpz_set (minExpY, expY);
750  if (mpz_cmp (minExpX, expX) > 0)
751  mpz_set (minExpX, expX);
752  }
753  mpz_init_set (exps[count], expX);
754  count++;
755  mpz_init_set (exps[count], expY);
756  exps_maxcount=count;
757  count++;
758  continue;
759  }
760  CFIterator j= i.coeff();
761  if (k == 0)
762  {
763  mpz_set (expX, A[0]);
764  mpz_addmul_ui (expX, M[1], i.exp());
765  mpz_addmul_ui (expX, M[0], j.exp());
766 
767  mpz_set (expY, A[1]);
768  mpz_addmul_ui (expY, M[3], i.exp());
769  mpz_addmul_ui (expY, M[2], j.exp());
770 
771  mpz_set (minExpX, expX);
772  mpz_set (minExpY, expY);
773  mpz_init_set (exps[count], expX);
774  count++;
775  mpz_init_set (exps[count], expY);
776  exps_maxcount=count;
777  count++;
778  j++;
779  k= 1;
780  }
781 
782  for (; j.hasTerms(); j++)
783  {
784  mpz_set (expX, A[0]);
785  mpz_addmul_ui (expX, M[1], i.exp());
786  mpz_addmul_ui (expX, M[0], j.exp());
787 
788  mpz_set (expY, A[1]);
789  mpz_addmul_ui (expY, M[3], i.exp());
790  mpz_addmul_ui (expY, M[2], j.exp());
791 
792  mpz_init_set (exps[count], expX);
793  count++;
794  mpz_init_set (exps[count], expY);
795  exps_maxcount=count;
796  count++;
797  if (mpz_cmp (minExpY, expY) > 0)
798  mpz_set (minExpY, expY);
799  if (mpz_cmp (minExpX, expX) > 0)
800  mpz_set (minExpX, expX);
801  }
802  }
803 
804  count= 0;
805  int mExpX= mpz_get_si (minExpX);
806  int mExpY= mpz_get_si (minExpY);
807  for (CFIterator i= F; i.hasTerms(); i++)
808  {
809  if (i.coeff().inCoeffDomain() && hasFirstAlgVar (i.coeff(), alpha))
810  {
811  result += i.coeff()*power (x, mpz_get_si (exps[count])-mExpX)*
812  power (y, mpz_get_si (exps[count+1])-mExpY);
813  count += 2;
814  continue;
815  }
816  CFIterator j= i.coeff();
817  for (; j.hasTerms(); j++)
818  {
819  result += j.coeff()*power (x, mpz_get_si (exps[count])-mExpX)*
820  power (y, mpz_get_si (exps[count+1])-mExpY);
821  count += 2;
822  }
823  }
824 
825  CanonicalForm tmp= LC (result);
826  if (tmp.inPolyDomain() && degree (tmp) <= 0)
827  {
828  int d= degree (result);
829  Variable x= result.mvar();
830  result -= tmp*power (x, d);
831  result += Lc (tmp)*power (x, d);
832  }
833 
834  if (computeMA)
835  {
836  for (int i= 0; i < n; i++)
837  delete [] newtonPolyg [i];
838  delete [] newtonPolyg;
839  mpz_mat_inv (M);
840  }
841 
842  for(int tt=exps_maxcount;tt>=0;tt--) mpz_clear(exps[tt]);
843  delete [] exps;
844  mpz_clear (expX);
845  mpz_clear (expY);
846  mpz_clear (minExpX);
847  mpz_clear (minExpY);
848 
849  return result;
850 }
851 
853 decompress (const CanonicalForm& F, const mpz_t* inverseM, const mpz_t * A)
854 {
856  Variable x= Variable (1);
857  Variable y= Variable (2);
858 
859  mpz_t expX, expY, minExpX, minExpY;
860  mpz_init (expX);
861  mpz_init (expY);
862  mpz_init (minExpX);
863  mpz_init (minExpY);
864 
865  mpz_t * exps= new mpz_t [2*size(F)];
866  int max_exps=0;
867  int count= 0;
868  if (F.isUnivariate() && F.level() == 1)
869  {
870  CFIterator i= F;
871 
872  mpz_set_si (expX, i.exp());
873  mpz_sub (expX, expX, A[0]);
874  mpz_mul (expX, expX, inverseM[0]);
875  mpz_submul (expX, inverseM[1], A[1]);
876 
877  mpz_set_si (expY, i.exp());
878  mpz_sub (expY, expY, A[0]);
879  mpz_mul (expY, expY, inverseM[2]);
880  mpz_submul (expY, inverseM[3], A[1]);
881 
882  mpz_set (minExpX, expX);
883  mpz_set (minExpY, expY);
884 
885  mpz_init_set (exps[count], expX);
886  count++;
887  mpz_init_set (exps[count], expY);
888  count++;
889  max_exps=count;
890 
891  i++;
892  for (; i.hasTerms(); i++)
893  {
894  mpz_set_si (expX, i.exp());
895  mpz_sub (expX, expX, A[0]);
896  mpz_mul (expX, expX, inverseM[0]);
897  mpz_submul (expX, inverseM[1], A[1]);
898 
899  mpz_set_si (expY, i.exp());
900  mpz_sub (expY, expY, A[0]);
901  mpz_mul (expY, expY, inverseM[2]);
902  mpz_submul (expY, inverseM[3], A[1]);
903 
904  mpz_init_set (exps[count], expX);
905  count++;
906  mpz_init_set (exps[count], expY);
907  max_exps=count;
908  count++;
909 
910  if (mpz_cmp (minExpY, expY) > 0)
911  mpz_set (minExpY, expY);
912  if (mpz_cmp (minExpX, expX) > 0)
913  mpz_set (minExpX, expX);
914  }
915 
916  int mExpX= mpz_get_si (minExpX);
917  int mExpY= mpz_get_si (minExpY);
918  count= 0;
919  for (i= F; i.hasTerms(); i++)
920  {
921  result += i.coeff()*power (x, mpz_get_si (exps[count])-mExpX)*
922  power (y, mpz_get_si (exps[count+1])-mExpY);
923  max_exps=count+1;
924  count += 2;
925  }
926 
927  mpz_clear (expX);
928  mpz_clear (expY);
929  mpz_clear (minExpX);
930  mpz_clear (minExpY);
931 
932  for(int tt=max_exps;tt>=0;tt--) mpz_clear(exps[tt]);
933  delete [] exps;
934  return result/ Lc (result); //normalize
935  }
936 
937  mpz_t tmp;
938  mpz_init (tmp);
939  int k= 0;
940  Variable alpha;
941  for (CFIterator i= F; i.hasTerms(); i++)
942  {
943  if (i.coeff().inCoeffDomain() && hasFirstAlgVar (i.coeff(), alpha))
944  {
945  mpz_set_si (expX, i.exp());
946  mpz_sub (expX, expX, A[1]);
947  mpz_mul (expX, expX, inverseM[1]);
948  mpz_submul (expX, A[0], inverseM[0]);
949 
950  mpz_set_si (expY, i.exp());
951  mpz_sub (expY, expY, A[1]);
952  mpz_mul (expY, expY, inverseM[3]);
953  mpz_submul (expY, A[0], inverseM[2]);
954 
955  if (k == 0)
956  {
957  mpz_set (minExpX, expX);
958  mpz_set (minExpY, expY);
959  k= 1;
960  }
961  else
962  {
963  if (mpz_cmp (minExpY, expY) > 0)
964  mpz_set (minExpY, expY);
965  if (mpz_cmp (minExpX, expX) > 0)
966  mpz_set (minExpX, expX);
967  }
968  mpz_init_set (exps[count], expX);
969  count++;
970  mpz_init_set (exps[count], expY);
971  max_exps=count;
972  count++;
973  continue;
974  }
975  CFIterator j= i.coeff();
976  if (k == 0)
977  {
978  mpz_set_si (expX, j.exp());
979  mpz_sub (expX, expX, A[0]);
980  mpz_mul (expX, expX, inverseM[0]);
981  mpz_set_si (tmp, i.exp());
982  mpz_sub (tmp, tmp, A[1]);
983  mpz_addmul (expX, tmp, inverseM[1]);
984 
985  mpz_set_si (expY, j.exp());
986  mpz_sub (expY, expY, A[0]);
987  mpz_mul (expY, expY, inverseM[2]);
988  mpz_set_si (tmp, i.exp());
989  mpz_sub (tmp, tmp, A[1]);
990  mpz_addmul (expY, tmp, inverseM[3]);
991 
992  mpz_set (minExpX, expX);
993  mpz_set (minExpY, expY);
994 
995  mpz_init_set (exps[count], expX);
996  count++;
997  mpz_init_set (exps[count], expY);
998  max_exps=count;
999  count++;
1000 
1001  j++;
1002  k= 1;
1003  }
1004 
1005  for (; j.hasTerms(); j++)
1006  {
1007  mpz_set_si (expX, j.exp());
1008  mpz_sub (expX, expX, A[0]);
1009  mpz_mul (expX, expX, inverseM[0]);
1010  mpz_set_si (tmp, i.exp());
1011  mpz_sub (tmp, tmp, A[1]);
1012  mpz_addmul (expX, tmp, inverseM[1]);
1013 
1014  mpz_set_si (expY, j.exp());
1015  mpz_sub (expY, expY, A[0]);
1016  mpz_mul (expY, expY, inverseM[2]);
1017  mpz_set_si (tmp, i.exp());
1018  mpz_sub (tmp, tmp, A[1]);
1019  mpz_addmul (expY, tmp, inverseM[3]);
1020 
1021  mpz_init_set (exps[count], expX);
1022  count++;
1023  mpz_init_set (exps[count], expY);
1024  max_exps=count;
1025  count++;
1026 
1027  if (mpz_cmp (minExpY, expY) > 0)
1028  mpz_set (minExpY, expY);
1029  if (mpz_cmp (minExpX, expX) > 0)
1030  mpz_set (minExpX, expX);
1031  }
1032  }
1033 
1034  int mExpX= mpz_get_si (minExpX);
1035  int mExpY= mpz_get_si (minExpY);
1036  count= 0;
1037  for (CFIterator i= F; i.hasTerms(); i++)
1038  {
1039  if (i.coeff().inCoeffDomain() && hasFirstAlgVar (i.coeff(), alpha))
1040  {
1041  result += i.coeff()*power (x, mpz_get_si (exps[count])-mExpX)*
1042  power (y, mpz_get_si (exps[count+1])-mExpY);
1043  max_exps=count+1;
1044  count += 2;
1045  continue;
1046  }
1047  for (CFIterator j= i.coeff(); j.hasTerms(); j++)
1048  {
1049  result += j.coeff()*power (x, mpz_get_si (exps[count])-mExpX)*
1050  power (y, mpz_get_si (exps[count+1])-mExpY);
1051  max_exps=count+1;
1052  count += 2;
1053  }
1054  }
1055 
1056  mpz_clear (expX);
1057  mpz_clear (expY);
1058  mpz_clear (minExpX);
1059  mpz_clear (minExpY);
1060  mpz_clear (tmp);
1061 
1062  for(int tt=max_exps;tt>=0;tt--) mpz_clear(exps[tt]);
1063  delete [] exps;
1064 
1065  return result/Lc (result); //normalize
1066 }
1067 
1068 //assumes the input is a Newton polygon of a bivariate polynomial which is
1069 //primitive wrt. x and y, i.e. there is at least one point of the polygon lying
1070 //on the x-axis and one lying on the y-axis
1071 int* getRightSide (int** polygon, int sizeOfPolygon, int& sizeOfOutput)
1072 {
1073  int maxY= polygon [0][0];
1074  int indexY= 0;
1075  for (int i= 1; i < sizeOfPolygon; i++)
1076  {
1077  if (maxY < polygon [i][0])
1078  {
1079  maxY= polygon [i][0];
1080  indexY= i;
1081  }
1082  else if (maxY == polygon [i][0])
1083  {
1084  if (polygon [indexY][1] < polygon[i][1])
1085  indexY= i;
1086  }
1087  if (maxY > polygon [i][0])
1088  break;
1089  }
1090 
1091  int count= -1;
1092  for (int i= indexY; i < sizeOfPolygon; i++)
1093  {
1094  if (polygon[i][0] == 0)
1095  {
1096  count= i - indexY;
1097  break;
1098  }
1099  }
1100 
1101  int * result;
1102  int index= 0;
1103  if (count < 0)
1104  {
1105  result= new int [sizeOfPolygon - indexY];
1106  sizeOfOutput= sizeOfPolygon - indexY;
1107  count= sizeOfPolygon - indexY - 1;
1108  result [0]= polygon[sizeOfPolygon - 1][0] - polygon [0] [0];
1109  index= 1;
1110  }
1111  else
1112  {
1113  sizeOfOutput= count;
1114  result= new int [count];
1115  }
1116 
1117  for (int i= indexY + count; i > indexY; i--, index++)
1118  result [index]= polygon [i - 1] [0] - polygon [i] [0];
1119 
1120  return result;
1121 }
1122 
1124 {
1125  ASSERT (getNumVars (F) == 2, "expected bivariate polynomial");
1126  ASSERT (getCharacteristic() == 0, "expected polynomial over integers or rationals");
1127 
1128  int sizeOfNewtonPolygon;
1129  int ** newtonPolyg= newtonPolygon (F, sizeOfNewtonPolygon);
1130  if (sizeOfNewtonPolygon == 3)
1131  {
1132  bool check1=
1133  (newtonPolyg[0][0]==0 || newtonPolyg[1][0]==0 || newtonPolyg[2][0]==0);
1134  if (check1)
1135  {
1136  bool check2=
1137  (newtonPolyg[0][1]==0 || newtonPolyg[1][1]==0 || newtonPolyg[2][0]==0);
1138  if (check2)
1139  {
1140  bool isRat= isOn (SW_RATIONAL);
1141  if (isRat)
1142  Off (SW_RATIONAL);
1143  CanonicalForm tmp= gcd (newtonPolyg[0][0],newtonPolyg[0][1]); // maybe it's better to use plain intgcd
1144  tmp= gcd (tmp, newtonPolyg[1][0]);
1145  tmp= gcd (tmp, newtonPolyg[1][1]);
1146  tmp= gcd (tmp, newtonPolyg[2][0]);
1147  tmp= gcd (tmp, newtonPolyg[2][1]);
1148  if (isRat)
1149  On (SW_RATIONAL);
1150  for (int i= 0; i < sizeOfNewtonPolygon; i++)
1151  delete [] newtonPolyg [i];
1152  delete [] newtonPolyg;
1153  return (tmp==1);
1154  }
1155  }
1156  }
1157  for (int i= 0; i < sizeOfNewtonPolygon; i++)
1158  delete [] newtonPolyg [i];
1159  delete [] newtonPolyg;
1160  return false;
1161 }
1162 
1164 {
1165  ASSERT (getNumVars (F) == 2, "expected bivariate polynomial");
1166  ASSERT (factorize (F).length() <= 2, " expected irreducible polynomial");
1167 
1168  int sizeOfNewtonPolygon;
1169  int ** newtonPolyg= newtonPolygon (F, sizeOfNewtonPolygon);
1170  bool isRat= isOn (SW_RATIONAL);
1171  if (isRat)
1172  Off (SW_RATIONAL);
1173  int p=getCharacteristic();
1174  int d=1;
1175  char bufGFName='Z';
1176  bool GF= (CFFactory::gettype()==GaloisFieldDomain);
1177  if (GF)
1178  {
1179  d= getGFDegree();
1180  bufGFName=gf_name;
1181  }
1182 
1183  setCharacteristic(0);
1184 
1185  CanonicalForm g= gcd (newtonPolyg[0][0], newtonPolyg[0][1]); //maybe it's better to use plain intgcd
1186 
1187  int i= 1;
1188  while (!g.isOne() && i < sizeOfNewtonPolygon)
1189  {
1190  g= gcd (g, newtonPolyg[i][0]);
1191  g= gcd (g, newtonPolyg[i][1]);
1192  i++;
1193  }
1194 
1195  bool result= g.isOne();
1196 
1197  if (GF)
1198  setCharacteristic (p, d, bufGFName);
1199  else
1200  setCharacteristic(p);
1201 
1202  if (isRat)
1203  On (SW_RATIONAL);
1204 
1205  for (int i= 0; i < sizeOfNewtonPolygon; i++)
1206  delete [] newtonPolyg[i];
1207 
1208  delete [] newtonPolyg;
1209 
1210  return result;
1211 }
1212 
1214 {
1215  ASSERT (getNumVars (F) == 2, "expected bivariate polynomial");
1216  ASSERT (factorize (F).length() <= 2, " expected irreducible polynomial");
1217 
1218  bool isRat= isOn (SW_RATIONAL);
1219  if (isRat)
1220  Off (SW_RATIONAL);
1221 
1222  if (isRat)
1223  {
1224  ASSERT (bCommonDen (F).isOne(), "poly over Z expected");
1225  }
1226 
1227  CanonicalForm Fp, N= maxNorm (F);
1228  int tdeg= totaldegree (F);
1229 
1230  int i= 0;
1231  //TODO: maybe it's better to choose the characteristic as large as possible
1232  // as factorization over large finite field will be faster
1233  //TODO: handle those cases where our factory primes are not enough
1234  //TODO: factorize coefficients corresponding to the vertices of the Newton
1235  // polygon and only try the obtained factors
1236  if (N < cf_getSmallPrime (cf_getNumSmallPrimes()-1))
1237  {
1238  while (i < cf_getNumSmallPrimes() && N > cf_getSmallPrime(i))
1239  {
1241  Fp= F.mapinto();
1242  i++;
1243  if (totaldegree (Fp) == tdeg)
1244  {
1245  if (absIrredTest (Fp))
1246  {
1247  CFFList factors= factorize (Fp);
1248  if (factors.length() == 2 && factors.getLast().exp() == 1)
1249  {
1250  if (isRat)
1251  On (SW_RATIONAL);
1252  setCharacteristic (0);
1253  return true;
1254  }
1255  }
1256  }
1257  setCharacteristic (0);
1258  }
1259  }
1260  else
1261  {
1262  while (i < cf_getNumPrimes() && N > cf_getPrime (i))
1263  {
1265  Fp= F.mapinto();
1266  i++;
1267  if (totaldegree (Fp) == tdeg)
1268  {
1269  if (absIrredTest (Fp))
1270  {
1271  CFFList factors= factorize (Fp);
1272  if (factors.length() == 2 && factors.getLast().exp() == 1)
1273  {
1274  if (isRat)
1275  On (SW_RATIONAL);
1276  setCharacteristic (0);
1277  return true;
1278  }
1279  }
1280  }
1281  setCharacteristic (0);
1282  }
1283  }
1284 
1285  if (isRat)
1286  On (SW_RATIONAL);
1287 
1288  return false;
1289 }
1290 
1291 bool
1293 {
1294  ASSERT (getNumVars (F) == 2, "expected bivariate polynomial");
1295  ASSERT (factorize (F).length() <= 2, " expected irreducible polynomial");
1296 
1297  bool isRat= isOn (SW_RATIONAL);
1298  if (isRat)
1299  Off (SW_RATIONAL);
1300 
1301  if (isRat)
1302  {
1303  ASSERT (bCommonDen (F).isOne(), "poly over Z expected");
1304  }
1305 
1306  Variable x= Variable (1);
1307  Variable y= Variable (2);
1308  CanonicalForm Fp;
1309  int tdeg= totaldegree (F);
1310 
1311  REvaluation E;
1312 
1313  setCharacteristic (2);
1314  Fp= F.mapinto();
1315 
1316  E= REvaluation (1,2, FFRandom());
1317 
1318  E.nextpoint();
1319 
1320  Fp= Fp (x+E[1], x);
1321  Fp= Fp (y+E[2], y);
1322 
1323  if (tdeg == totaldegree (Fp))
1324  {
1325  if (absIrredTest (Fp))
1326  {
1327  CFFList factors= factorize (Fp);
1328  if (factors.length() == 2 && factors.getLast().exp() == 1)
1329  {
1330  if (isRat)
1331  On (SW_RATIONAL);
1332  setCharacteristic (0);
1333  return true;
1334  }
1335  }
1336  }
1337 
1338  E.nextpoint();
1339 
1340  Fp= Fp (x+E[1], x);
1341  Fp= Fp (y+E[2], y);
1342 
1343  if (tdeg == totaldegree (Fp))
1344  {
1345  if (absIrredTest (Fp))
1346  {
1347  CFFList factors= factorize (Fp);
1348  if (factors.length() == 2 && factors.getLast().exp() == 1)
1349  {
1350  if (isRat)
1351  On (SW_RATIONAL);
1352  setCharacteristic (0);
1353  return true;
1354  }
1355  }
1356  }
1357 
1358  int i= 0;
1359  while (cf_getSmallPrime (i) < 102)
1360  {
1362  i++;
1363  E= REvaluation (1, 2, FFRandom());
1364 
1365  for (int j= 0; j < 3; j++)
1366  {
1367  Fp= F.mapinto();
1368  E.nextpoint();
1369  Fp= Fp (x+E[1], x);
1370  Fp= Fp (y+E[2], y);
1371 
1372  if (tdeg == totaldegree (Fp))
1373  {
1374  if (absIrredTest (Fp))
1375  {
1376  CFFList factors= factorize (Fp);
1377  if (factors.length() == 2 && factors.getLast().exp() == 1)
1378  {
1379  if (isRat)
1380  On (SW_RATIONAL);
1381  setCharacteristic (0);
1382  return true;
1383  }
1384  }
1385  }
1386  }
1387  }
1388 
1389  setCharacteristic (0);
1390  if (isRat)
1391  On (SW_RATIONAL);
1392 
1393  return false;
1394 }
1395 
1396 
int status int void size_t count
Definition: si_signals.h:59
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
static bool isConvex(int *point1, int *point2, int *point3)
int cf_getSmallPrime(int i)
Definition: cf_primes.cc:28
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
int j
Definition: facHensel.cc:105
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
void getMaxMin(int **points, int sizePoints, int &minDiff, int &minSum, int &maxDiff, int &maxSum, int &maxX, int &maxY)
static gmp_float * diff
Definition: mpr_complex.cc:45
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
void mu(int **points, int sizePoints)
int cf_getPrime(int i)
Definition: cf_primes.cc:14
void Off(int sw)
switches
bool irreducibilityTest(const CanonicalForm &F)
computes the Newton polygon of F and checks if it satisfies the irreducibility criterion from S...
This file provides functions to compute the Newton polygon of a bivariate polynomial.
some useful template functions.
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
static int min(int a, int b)
Definition: fast_mult.cc:268
factory&#39;s class for variables
Definition: factory.h:117
static void translate(int **points, int *point, int sizePoints)
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
static void swap(int **points, int i, int j)
generate random evaluation points
factory&#39;s main class
Definition: canonicalform.h:77
char gf_name
Definition: gfops.cc:52
class to generate random evaluation points
Definition: cf_reval.h:25
static bool isLess(int *point1, int *point2)
assertions for Factory
int * getRightSide(int **polygon, int sizeOfPolygon, int &sizeOfOutput)
get the y-direction slopes of all edges with positive slope in y-direction of a convex polygon with a...
static coordinates * points
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:92
Variable alpha
Definition: facAbsBiFact.cc:52
static TreeM * G
Definition: janet.cc:31
CanonicalForm Lc(const CanonicalForm &f)
void setCharacteristic(int c)
Definition: cf_char.cc:23
int tdeg(poly p)
Definition: walkSupport.cc:35
int getCharacteristic()
Definition: cf_char.cc:51
bool modularIrredTest(const CanonicalForm &F)
modular absolute irreducibility test as described in "Modular Las Vegas Algorithms for Polynomial Abs...
Rational abs(const Rational &a)
Definition: GMPrat.cc:436
void mpz_mat_inv(mpz_t *&M)
CanonicalForm mapinto() const
static void sort(int **points, int sizePoints)
int ** newtonPolygon(const CanonicalForm &F, int &sizeOfNewtonPoly)
compute the Newton polygon of a bivariate polynomial
#define M
Definition: sirandom.c:24
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
CanonicalForm b
Definition: cfModGcd.cc:4044
int ** getPoints(const CanonicalForm &F, int &n)
static void quickSort(int lo, int hi, int **points)
bool inPolyDomain() const
Operations in GF, where GF is a finite field of size less than 2^16 represented by a root of Conway p...
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:48
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
int status int void * buf
Definition: si_signals.h:59
bool isUnivariate() const
void lambdaInverse(int **points, int sizePoints)
#define A
Definition: sirandom.c:23
Interface to generate InternalCF&#39;s over various domains from intrinsic types or mpz_t&#39;s.
static int * getDegrees(const CanonicalForm &F, int &sizeOfOutput)
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
int polygon(int **points, int sizePoints)
compute a polygon
bool absIrredTest(const CanonicalForm &F)
absolute irreducibility test as described in "Modular Las Vegas Algorithms for Polynomial Absolute Fa...
bool isOn(int sw)
switches
void On(int sw)
switches
Iterators for CanonicalForm&#39;s.
void tau(int **points, int sizePoints, int k)
int cf_getNumSmallPrimes()
Definition: cf_primes.cc:34
FILE * f
Definition: checklibs.c:9
generate random elements in F_p
Definition: cf_random.h:43
int i
Definition: cfEzgcd.cc:125
T getLast() const
Definition: ftmpl_list.cc:309
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
declarations of higher level algorithms.
int grahamScan(int **points, int sizePoints)
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
#define NULL
Definition: omList.c:12
int length() const
Definition: ftmpl_list.cc:273
bool isInPolygon(int **points, int sizePoints, int *point)
check if point is inside a polygon described by points
access to prime tables
static int gettype()
Definition: cf_factory.h:28
REvaluation E(1, terms.length(), IntRandom(25))
void convexDense(int **points, int sizePoints, mpz_t *&M, mpz_t *&A)
Algorithm 5 as described in Convex-Dense Bivariate Polynomial Factorization by Berthomieu, Lecerf.
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
int gcd(int a, int b)
Definition: walkSupport.cc:836
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:263
void lambda(int **points, int sizePoints)
int getGFDegree()
Definition: cf_char.cc:56
void nextpoint()
Definition: cf_reval.cc:46
Variable x
Definition: cfModGcd.cc:4023
#define GaloisFieldDomain
Definition: cf_defs.h:22
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
void mpz_mat_mul(const mpz_t *N, mpz_t *&M)
int level() const
level() returns the level of CO.
#define ASSERT(expression, message)
Definition: cf_assert.h:99
bool modularIrredTestWithShift(const CanonicalForm &F)
modular absolute irreducibility test with shift as described in "Modular Las Vegas Algorithms for Pol...
int p
Definition: cfModGcd.cc:4019
int degree(const CanonicalForm &f)
CF_NO_INLINE int exp() const
get the current exponent
CanonicalForm LC(const CanonicalForm &f)
static Poly * h
Definition: janet.cc:971
CanonicalForm compress(const CanonicalForm &F, mpz_t *&M, mpz_t *&A, bool computeMA)
compress a bivariate poly
static int smallestPointIndex(int **points, int sizePoints)
int cf_getNumPrimes()
Definition: cf_primes.cc:23
return result
Definition: facAbsBiFact.cc:76
Header for factory&#39;s main class CanonicalForm.
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
bool inCoeffDomain() const