35 for (
int i= 0;
i < sizePoints;
i++)
37 points[
i] [0] -= point [0];
38 points[
i] [1] -= point [1];
46 for (
int i= 1;
i < sizePoints;
i++)
48 if (points[
i][0] < points[min][0] ||
49 (points[
i] [0] == points[min] [0] && points[
i] [1] < points[min] [1]))
64 bool isLess (
int* point1,
int* point2)
66 long area= point1[0]*point2[1]- point1[1]*point2[0];
67 if (area > 0)
return true;
70 return (
abs (point1[0]) +
abs (point1[1]) >
71 abs (point2[0]) +
abs (point2[1]));
80 int* point=
new int [2];
81 point [0]= points [(lo+hi)/2] [0];
82 point [1]= points [(lo+hi)/2] [1];
85 while (
isLess (points [i], point) && i < hi) i++;
86 while (
isLess (point, points[j]) && j > lo) j--;
107 bool isConvex (
int* point1,
int* point2,
int* point3)
109 long relArea= (point1[0] - point2[0])*(point3[1] - point2[1]) -
110 (point1[1] - point2[1])*(point3[0] - point2[0]);
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])));
125 return isConvex (points[i - 1], points [i], points [i + 1]);
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);
139 delete [] minusPoint;
141 while (
k < sizePoints)
146 swap (points, i - 1, i);
152 if (i + 1 <= sizePoints || i == sizePoints)
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]);
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]))
174 if (sizePoints < 3)
return sizePoints;
188 sizeOfOutput=
size (F);
189 int*
result=
new int [sizeOfOutput];
200 int **
points=
new int* [n];
201 for (
int i= 0;
i < n;
i++)
202 points [
i]=
new int [2];
211 points [
j] [0]=
i.exp();
219 for (
int k= 0;
k < bufSize;
k++, j++)
221 points [
j] [0]=
i.exp();
222 points [
j] [1]= buf [
k];
230 merge (
int ** points1,
int sizePoints1,
int ** points2,
int sizePoints2,
234 sizeResult= sizePoints1+sizePoints2;
235 for (i= 0; i < sizePoints1; i++)
237 for (j= 0; j < sizePoints2; j++)
239 if (points1[i][0] != points2[j][0])
243 if (points1[i][1] != points2[j][1])
257 int **
result=
new int *[sizeResult];
258 for (i= 0; i < sizeResult; i++)
259 result [i]=
new int [2];
262 for (i= 0; i < sizePoints1; i++, k++)
264 result[
k][0]= points1[
i][0];
265 result[
k][1]= points1[
i][1];
267 for (i= 0; i < sizePoints2; i++)
269 if (points2[i][0] < 0)
273 result[
k][0]= points2[
i][0];
274 result[
k][1]= points2[
i][1];
285 int **
points=
new int* [sizeF];
286 for (
int i= 0;
i < sizeF;
i++)
287 points [
i]=
new int [2];
294 for (
int k= 0;
k < bufSize;
k++, j++)
296 points [
j] [0]=
i.exp();
297 points [
j] [1]= buf [
k];
302 int n=
polygon (points, sizeF);
304 int **
result=
new int* [n];
305 for (
int i= 0;
i < n;
i++)
307 result [
i]=
new int [2];
308 result [
i] [0]= points [
i] [0];
309 result [
i] [1]= points [
i] [1];
313 for (
int i= 0;
i < sizeF;
i++)
322 int& sizeOfNewtonPoly)
325 int ** pointsF=
new int* [sizeF];
326 for (
int i= 0;
i < sizeF;
i++)
327 pointsF [
i]=
new int [2];
334 for (
int k= 0;
k < bufSize;
k++, j++)
336 pointsF [
j] [0]=
i.exp();
337 pointsF [
j] [1]= buf [
k];
343 int ** pointsG=
new int* [sizeG];
344 for (
int i= 0;
i < sizeG;
i++)
345 pointsG [
i]=
new int [2];
350 for (
int k= 0;
k < bufSize;
k++, j++)
352 pointsG [
j] [0]=
i.exp();
353 pointsG [
j] [1]= buf [
k];
359 int **
points=
merge (pointsF, sizeF, pointsG, sizeG, sizePoints);
361 int n=
polygon (points, sizePoints);
363 int **
result=
new int* [n];
364 for (
int i= 0;
i < n;
i++)
366 result [
i]=
new int [2];
367 result [
i] [0]= points [
i] [0];
368 result [
i] [1]= points [
i] [1];
372 for (
int i= 0;
i < sizeF;
i++)
373 delete [] pointsF[
i];
375 for (
int i= 0;
i < sizeG;
i++)
376 delete [] pointsG[
i];
385 int **
buf=
new int* [sizePoints + 1];
386 for (
int i= 0;
i < sizePoints;
i++)
388 buf [
i]=
new int [2];
389 buf [
i] [0]= points [
i] [0];
390 buf [
i] [1]= points [
i] [1];
392 buf [sizePoints]=
new int [2];
393 buf [sizePoints] [0]= point [0];
394 buf [sizePoints] [1]= point [1];
395 int sizeBuf= sizePoints + 1;
398 int * minusPoint=
new int [2];
399 minusPoint [0]= buf[0] [0];
400 minusPoint [1]= buf[0] [1];
403 minusPoint[0]= - minusPoint[0];
404 minusPoint[1]= - minusPoint[1];
406 delete [] minusPoint;
408 if (buf [0] [0] == point [0] && buf [0] [1] == point [1])
410 for (
int i= 0;
i < sizeBuf;
i++)
416 for (
int i= 1;
i < sizeBuf-1;
i++)
418 if (buf [
i] [0] == point [0] && buf [
i] [1] == point [1])
421 for (
int i= 0;
i < sizeBuf;
i++)
428 if (buf [sizeBuf - 1] [0] == point [0] && buf [sizeBuf-1] [1] == point [1])
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];
437 for (
int i= 0;
i < sizeBuf;
i++)
442 for (
int i= 0;
i < sizeBuf;
i++)
451 for (
int i= 0;
i < sizePoints;
i++)
452 points [
i] [1]= points [
i] [1] - points [
i] [0];
457 for (
int i= 0;
i < sizePoints;
i++)
458 points [
i] [1]= points [
i] [1] + points [
i] [0];
463 for (
int i= 0;
i < sizePoints;
i++)
464 points [
i] [1]= points [
i] [1] + k;
470 for (
int i= 0;
i < sizePoints;
i++)
473 points [
i] [0]= points [
i] [1];
479 int& maxDiff,
int& maxSum,
int& maxX,
int& maxY
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];
489 for (
int i= 1;
i < sizePoints;
i++)
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]);
504 mpz_t * tmp=
new mpz_t[4];
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]);
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]);
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]);
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]);
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]);
538 mpz_init_set (det, M[0]);
539 mpz_mul (det, det, M[3]);
540 mpz_submul (det, M[1], M[2]);
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);
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);
564 mpz_t u,
v,
g,maxX,maxY;
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])
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);
585 mpz_set (M[3], maxX);
586 mpz_divexact (M[3], M[3], g);
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);
604 else if (sizePoints == 1)
606 mpz_set_si (M[0], 1);
607 mpz_set_si (M[3], 1);
611 mpz_set_si (M[0], 1);
612 mpz_set_si (M[3], 1);
614 mpz_t * Mu=
new mpz_t[4];
615 mpz_init_set_si (Mu[1], 1);
616 mpz_init_set_si (Mu[2], 1);
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]);
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]);
634 int minDiff, minSum, maxDiff, maxSum, maxX, maxY,
b, d,
f,
h;
635 getMaxMin(points, sizePoints, minDiff, minSum, maxDiff, maxSum, maxX, maxY);
640 mu (points, sizePoints);
645 mpz_set (A[0], A[1]);
648 getMaxMin(points, sizePoints, minDiff, minSum, maxDiff, maxSum, maxX, maxY);
650 d= maxX + maxY - maxSum;
655 lambda (points, sizePoints);
656 tau (points, sizePoints, maxY - f);
661 mpz_add_ui (A[0], A[0], maxY-f);
663 mpz_add_ui (A[0], A[0], f-maxY);
664 maxX= maxX + maxY - b -
f;
666 else if (d + h > maxY)
669 tau (points, sizePoints, -h);
674 mpz_add_ui (A[0], A[0], -h);
676 mpz_sub_ui (A[0], A[0], h);
677 maxX= maxX + maxY - d -
h;
688 mpz_clear (Lambda[0]);
689 mpz_clear (Lambda[1]);
690 mpz_clear (Lambda[2]);
691 mpz_clear (Lambda[3]);
694 mpz_clear (InverseLambda[0]);
695 mpz_clear (InverseLambda[1]);
696 mpz_clear (InverseLambda[2]);
697 mpz_clear (InverseLambda[3]);
698 delete [] InverseLambda;
709 int ** newtonPolyg=
NULL;
720 mpz_t expX, expY, minExpX, minExpY;
728 mpz_t * exps=
new mpz_t [2*
size (F)];
734 mpz_set (expX, A[0]);
735 mpz_set (expY, A[1]);
736 mpz_addmul_ui (expX, M[1],
i.exp());
737 mpz_addmul_ui (expY, M[3],
i.exp());
741 mpz_set (minExpX, expX);
742 mpz_set (minExpY, expY);
747 if (mpz_cmp (minExpY, expY) > 0)
748 mpz_set (minExpY, expY);
749 if (mpz_cmp (minExpX, expX) > 0)
750 mpz_set (minExpX, expX);
752 mpz_init_set (exps[count], expX);
754 mpz_init_set (exps[count], expY);
761 mpz_set (expX, A[0]);
762 mpz_addmul_ui (expX, M[1],
i.exp());
763 mpz_addmul_ui (expX, M[0], j.
exp());
765 mpz_set (expY, A[1]);
766 mpz_addmul_ui (expY, M[3],
i.exp());
767 mpz_addmul_ui (expY, M[2], j.
exp());
769 mpz_set (minExpX, expX);
770 mpz_set (minExpY, expY);
771 mpz_init_set (exps[count], expX);
773 mpz_init_set (exps[count], expY);
781 mpz_set (expX, A[0]);
782 mpz_addmul_ui (expX, M[1],
i.exp());
783 mpz_addmul_ui (expX, M[0], j.
exp());
785 mpz_set (expY, A[1]);
786 mpz_addmul_ui (expY, M[3],
i.exp());
787 mpz_addmul_ui (expY, M[2], j.
exp());
789 mpz_init_set (exps[count], expX);
791 mpz_init_set (exps[count], expY);
793 if (mpz_cmp (minExpY, expY) > 0)
794 mpz_set (minExpY, expY);
795 if (mpz_cmp (minExpX, expX) > 0)
796 mpz_set (minExpX, expX);
801 int mExpX= mpz_get_si (minExpX);
802 int mExpY= mpz_get_si (minExpY);
807 result +=
i.coeff()*
power (x, mpz_get_si (exps[count])-mExpX)*
808 power (y, mpz_get_si (exps[count+1])-mExpY);
815 result += j.
coeff()*
power (x, mpz_get_si (exps[count])-mExpX)*
816 power (y, mpz_get_si (exps[count+1])-mExpY);
826 result -= tmp*
power (x, d);
827 result +=
Lc (tmp)*
power (x, d);
832 for (
int i= 0;
i < n;
i++)
833 delete [] newtonPolyg [
i];
834 delete [] newtonPolyg;
854 mpz_t expX, expY, minExpX, minExpY;
860 mpz_t * exps=
new mpz_t [2*
size(F)];
866 mpz_set_si (expX, i.
exp());
867 mpz_sub (expX, expX, A[0]);
868 mpz_mul (expX, expX, inverseM[0]);
869 mpz_submul (expX, inverseM[1], A[1]);
871 mpz_set_si (expY, i.
exp());
872 mpz_sub (expY, expY, A[0]);
873 mpz_mul (expY, expY, inverseM[2]);
874 mpz_submul (expY, inverseM[3], A[1]);
876 mpz_set (minExpX, expX);
877 mpz_set (minExpY, expY);
879 mpz_init_set (exps[count], expX);
880 mpz_init_set (exps[count+1], expY);
886 mpz_set_si (expX, i.
exp());
887 mpz_sub (expX, expX, A[0]);
888 mpz_mul (expX, expX, inverseM[0]);
889 mpz_submul (expX, inverseM[1], A[1]);
891 mpz_set_si (expY, i.
exp());
892 mpz_sub (expY, expY, A[0]);
893 mpz_mul (expY, expY, inverseM[2]);
894 mpz_submul (expY, inverseM[3], A[1]);
896 mpz_init_set (exps[count], expX);
897 mpz_init_set (exps[count+1], expY);
900 if (mpz_cmp (minExpY, expY) > 0)
901 mpz_set (minExpY, expY);
902 if (mpz_cmp (minExpX, expX) > 0)
903 mpz_set (minExpX, expX);
906 int mExpX= mpz_get_si (minExpX);
907 int mExpY= mpz_get_si (minExpY);
911 result += i.
coeff()*
power (x, mpz_get_si (exps[count])-mExpX)*
912 power (y, mpz_get_si (exps[count+1])-mExpY);
922 return result/
Lc (result);
933 mpz_set_si (expX,
i.exp());
934 mpz_sub (expX, expX, A[1]);
935 mpz_mul (expX, expX, inverseM[1]);
936 mpz_submul (expX, A[0], inverseM[0]);
938 mpz_set_si (expY,
i.exp());
939 mpz_sub (expY, expY, A[1]);
940 mpz_mul (expY, expY, inverseM[3]);
941 mpz_submul (expY, A[0], inverseM[2]);
945 mpz_set (minExpX, expX);
946 mpz_set (minExpY, expY);
951 if (mpz_cmp (minExpY, expY) > 0)
952 mpz_set (minExpY, expY);
953 if (mpz_cmp (minExpX, expX) > 0)
954 mpz_set (minExpX, expX);
956 mpz_init_set (exps[count], expX);
957 mpz_init_set (exps[count+1], expY);
964 mpz_set_si (expX, j.
exp());
965 mpz_sub (expX, expX, A[0]);
966 mpz_mul (expX, expX, inverseM[0]);
967 mpz_set_si (tmp,
i.exp());
968 mpz_sub (tmp, tmp, A[1]);
969 mpz_addmul (expX, tmp, inverseM[1]);
971 mpz_set_si (expY, j.
exp());
972 mpz_sub (expY, expY, A[0]);
973 mpz_mul (expY, expY, inverseM[2]);
974 mpz_set_si (tmp,
i.exp());
975 mpz_sub (tmp, tmp, A[1]);
976 mpz_addmul (expY, tmp, inverseM[3]);
978 mpz_set (minExpX, expX);
979 mpz_set (minExpY, expY);
981 mpz_init_set (exps[count], expX);
982 mpz_init_set (exps[count+1], expY);
991 mpz_set_si (expX, j.
exp());
992 mpz_sub (expX, expX, A[0]);
993 mpz_mul (expX, expX, inverseM[0]);
994 mpz_set_si (tmp,
i.exp());
995 mpz_sub (tmp, tmp, A[1]);
996 mpz_addmul (expX, tmp, inverseM[1]);
998 mpz_set_si (expY, j.
exp());
999 mpz_sub (expY, expY, A[0]);
1000 mpz_mul (expY, expY, inverseM[2]);
1001 mpz_set_si (tmp,
i.exp());
1002 mpz_sub (tmp, tmp, A[1]);
1003 mpz_addmul (expY, tmp, inverseM[3]);
1005 mpz_init_set (exps[count], expX);
1006 mpz_init_set (exps[count+1], expY);
1009 if (mpz_cmp (minExpY, expY) > 0)
1010 mpz_set (minExpY, expY);
1011 if (mpz_cmp (minExpX, expX) > 0)
1012 mpz_set (minExpX, expX);
1016 int mExpX= mpz_get_si (minExpX);
1017 int mExpY= mpz_get_si (minExpY);
1023 result +=
i.coeff()*
power (x, mpz_get_si (exps[count])-mExpX)*
1024 power (y, mpz_get_si (exps[count+1])-mExpY);
1030 result +=
j.coeff()*
power (x, mpz_get_si (exps[count])-mExpX)*
1031 power (y, mpz_get_si (exps[count+1])-mExpY);
1038 mpz_clear (minExpX);
1039 mpz_clear (minExpY);
1044 return result/
Lc (result);
1052 int maxY= polygon [0][0];
1054 for (
int i= 1;
i < sizeOfPolygon;
i++)
1056 if (maxY < polygon [
i][0])
1058 maxY= polygon [
i][0];
1061 else if (maxY == polygon [i][0])
1063 if (polygon [indexY][1] < polygon[i][1])
1066 if (maxY > polygon [i][0])
1071 for (
int i= indexY;
i < sizeOfPolygon;
i++)
1073 if (polygon[
i][0] == 0)
1084 result=
new int [sizeOfPolygon - indexY];
1085 sizeOfOutput= sizeOfPolygon - indexY;
1086 count= sizeOfPolygon - indexY - 1;
1087 result [0]= polygon[sizeOfPolygon - 1][0] - polygon [0] [0];
1092 sizeOfOutput=
count;
1093 result=
new int [
count];
1096 for (
int i= indexY + count;
i > indexY;
i--, index++)
1097 result [index]= polygon [
i - 1] [0] - polygon [
i] [0];
1107 int sizeOfNewtonPolygon;
1109 if (sizeOfNewtonPolygon == 3)
1112 (newtonPolyg[0][0]==0 || newtonPolyg[1][0]==0 || newtonPolyg[2][0]==0);
1116 (newtonPolyg[0][1]==0 || newtonPolyg[1][1]==0 || newtonPolyg[2][0]==0);
1123 tmp=
gcd (tmp, newtonPolyg[1][0]);
1124 tmp=
gcd (tmp, newtonPolyg[1][1]);
1125 tmp=
gcd (tmp, newtonPolyg[2][0]);
1126 tmp=
gcd (tmp, newtonPolyg[2][1]);
1129 for (
int i= 0;
i < sizeOfNewtonPolygon;
i++)
1130 delete [] newtonPolyg [
i];
1131 delete [] newtonPolyg;
1136 for (
int i= 0;
i < sizeOfNewtonPolygon;
i++)
1137 delete [] newtonPolyg [
i];
1138 delete [] newtonPolyg;
1145 ASSERT (
factorize (F).length() <= 2,
" expected irreducible polynomial");
1147 int sizeOfNewtonPolygon;
1167 while (!g.
isOne() && i < sizeOfNewtonPolygon)
1169 g=
gcd (g, newtonPolyg[i][0]);
1170 g=
gcd (g, newtonPolyg[i][1]);
1184 for (
int i= 0; i < sizeOfNewtonPolygon; i++)
1185 delete [] newtonPolyg[i];
1187 delete [] newtonPolyg;
1195 ASSERT (
factorize (F).length() <= 2,
" expected irreducible polynomial");
1274 ASSERT (
factorize (F).length() <= 2,
" expected irreducible polynomial");
1344 for (
int j= 0;
j < 3;
j++)
int status int void size_t count
static bool isConvex(int *point1, int *point2, int *point3)
int cf_getSmallPrime(int i)
const CanonicalForm int const CFList const Variable & y
void getMaxMin(int **points, int sizePoints, int &minDiff, int &minSum, int &maxDiff, int &maxSum, int &maxX, int &maxY)
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
void mu(int **points, int sizePoints)
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)
factory's class for variables
static void translate(int **points, int *point, int sizePoints)
static void swap(int **points, int i, int j)
generate random evaluation points
class to generate random evaluation points
static bool isLess(int *point1, int *point2)
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
bool modularIrredTest(const CanonicalForm &F)
modular absolute irreducibility test as described in "Modular Las Vegas Algorithms for Polynomial Abs...
Rational abs(const Rational &a)
void mpz_mat_inv(mpz_t *&M)
CF_NO_INLINE int hasTerms() const
check if iterator has reached < the end of CanonicalForm
static void sort(int **points, int sizePoints)
int ** newtonPolygon(const CanonicalForm &F, int &sizeOfNewtonPoly)
compute the Newton polygon of a bivariate polynomial
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
int ** getPoints(const CanonicalForm &F, int &n)
static void quickSort(int lo, int hi, int **points)
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
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
int status int void * buf
void lambdaInverse(int **points, int sizePoints)
Interface to generate InternalCF's over various domains from intrinsic types or mpz_t's.
static int * getDegrees(const CanonicalForm &F, int &sizeOfOutput)
static const int SW_RATIONAL
set to 1 for computations over Q
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...
Iterators for CanonicalForm's.
void tau(int **points, int sizePoints, int k)
int cf_getNumSmallPrimes()
generate random elements in F_p
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)
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
class to iterate through CanonicalForm's
const Variable & v
< [in] a sqrfree bivariate poly
bool isInPolygon(int **points, int sizePoints, int *point)
check if point is inside a polygon described by points
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 exp() const
get the current exponent
void lambda(int **points, int sizePoints)
#define GaloisFieldDomain
void mpz_mat_mul(const mpz_t *N, mpz_t *&M)
#define ASSERT(expression, message)
bool modularIrredTestWithShift(const CanonicalForm &F)
modular absolute irreducibility test with shift as described in "Modular Las Vegas Algorithms for Pol...
CanonicalForm compress(const CanonicalForm &F, mpz_t *&M, mpz_t *&A, bool computeMA)
compress a bivariate poly
static int smallestPointIndex(int **points, int sizePoints)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)