My Project
Loading...
Searching...
No Matches
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
32static
33void 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
42static
43int 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
55static
56void swap (int** points, int i, int j)
57{
58 int* tmp= points[i];
59 points[i]= points[j];
60 points[j]= tmp;
61}
62
63static
64bool 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
76static
77void 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
99static
100void sort (int** points, int sizePoints)
101{
102 quickSort (1, sizePoints - 1, points);
103}
104
105// check whether p2 is convex
106static
107bool 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
122static
123bool isConvex (int** points, int i)
124{
125 return isConvex (points[i - 1], points [i], points [i + 1]);
126}
127
128int 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
172int polygon (int** points, int sizePoints)
173{
174 if (sizePoints < 3) return sizePoints;
175 return grahamScan (points, sizePoints);
176}
177
178static
179int* 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
197int ** 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
229int **
230merge (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
282int ** 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
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
383bool 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
449void 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
455void 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
461void 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
467void 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
478void 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
502void 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
535void 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
558void 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
706compress (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;
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
853decompress (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;
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
1071int* 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';
1177 if (GF)
1178 {
1179 d= getGFDegree();
1180 bufGFName=gf_name;
1181 }
1182
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
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
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);
1253 return true;
1254 }
1255 }
1256 }
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);
1277 return true;
1278 }
1279 }
1280 }
1282 }
1283 }
1284
1285 if (isRat)
1286 On (SW_RATIONAL);
1287
1288 return false;
1289}
1290
1291bool
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
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);
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);
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);
1382 return true;
1383 }
1384 }
1385 }
1386 }
1387 }
1388
1390 if (isRat)
1391 On (SW_RATIONAL);
1392
1393 return false;
1394}
1395
1396
Rational abs(const Rational &a)
Definition: GMPrat.cc:436
#define swap(_i, _j)
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Header for factory's main class CanonicalForm.
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
int degree(const CanonicalForm &f)
int getGFDegree()
Definition: cf_char.cc:75
void FACTORY_PUBLIC setCharacteristic(int c)
Definition: cf_char.cc:28
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:679
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
Variable x
Definition: cfModGcd.cc:4082
int p
Definition: cfModGcd.cc:4078
g
Definition: cfModGcd.cc:4090
CanonicalForm b
Definition: cfModGcd.cc:4103
static void quickSort(int lo, int hi, int **points)
void lambda(int **points, int sizePoints)
static bool isLess(int *point1, int *point2)
bool modularIrredTest(const CanonicalForm &F)
modular absolute irreducibility test as described in "Modular Las Vegas Algorithms for Polynomial Abs...
void lambdaInverse(int **points, int sizePoints)
void mpz_mat_inv(mpz_t *&M)
static bool isConvex(int *point1, int *point2, int *point3)
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...
void convexDense(int **points, int sizePoints, mpz_t *&M, mpz_t *&A)
Algorithm 5 as described in Convex-Dense Bivariate Polynomial Factorization by Berthomieu,...
static void sort(int **points, int sizePoints)
bool modularIrredTestWithShift(const CanonicalForm &F)
modular absolute irreducibility test with shift as described in "Modular Las Vegas Algorithms for Pol...
bool irreducibilityTest(const CanonicalForm &F)
computes the Newton polygon of F and checks if it satisfies the irreducibility criterion from S....
void getMaxMin(int **points, int sizePoints, int &minDiff, int &minSum, int &maxDiff, int &maxSum, int &maxX, int &maxY)
bool absIrredTest(const CanonicalForm &F)
absolute irreducibility test as described in "Modular Las Vegas Algorithms for Polynomial Absolute Fa...
bool isInPolygon(int **points, int sizePoints, int *point)
check if point is inside a polygon described by points
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
void tau(int **points, int sizePoints, int k)
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
void mu(int **points, int sizePoints)
void mpz_mat_mul(const mpz_t *N, mpz_t *&M)
int ** getPoints(const CanonicalForm &F, int &n)
static int * getDegrees(const CanonicalForm &F, int &sizeOfOutput)
int grahamScan(int **points, int sizePoints)
CanonicalForm compress(const CanonicalForm &F, mpz_t *&M, mpz_t *&A, bool computeMA)
compress a bivariate poly
int polygon(int **points, int sizePoints)
compute a polygon
static void translate(int **points, int *point, int sizePoints)
static int smallestPointIndex(int **points, int sizePoints)
This file provides functions to compute the Newton polygon of a bivariate polynomial.
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
declarations of higher level algorithms.
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:405
assertions for Factory
#define ASSERT(expression, message)
Definition: cf_assert.h:99
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:31
#define GaloisFieldDomain
Definition: cf_defs.h:18
Interface to generate InternalCF's over various domains from intrinsic types or mpz_t's.
Iterators for CanonicalForm's.
int cf_getPrime(int i)
Definition: cf_primes.cc:14
int cf_getNumPrimes()
Definition: cf_primes.cc:23
int cf_getNumSmallPrimes()
Definition: cf_primes.cc:34
int cf_getSmallPrime(int i)
Definition: cf_primes.cc:28
access to prime tables
generate random evaluation points
FILE * f
Definition: checklibs.c:9
static int gettype()
Definition: cf_factory.h:28
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
factory's main class
Definition: canonicalform.h:86
bool inPolyDomain() const
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
CanonicalForm mapinto() const
bool isUnivariate() const
generate random elements in F_p
Definition: cf_random.h:44
int length() const
Definition: ftmpl_list.cc:273
T getLast() const
Definition: ftmpl_list.cc:309
class to generate random evaluation points
Definition: cf_reval.h:26
void nextpoint()
Definition: cf_reval.cc:46
factory's class for variables
Definition: variable.h:33
Variable alpha
Definition: facAbsBiFact.cc:51
return result
Definition: facAbsBiFact.cc:75
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53
REvaluation E(1, terms.length(), IntRandom(25))
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
int j
Definition: facHensel.cc:110
static int min(int a, int b)
Definition: fast_mult.cc:268
some useful template functions.
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
VAR char gf_name
Definition: gfops.cc:52
Operations in GF, where GF is a finite field of size less than 2^16 represented by a root of Conway p...
STATIC_VAR coordinates * points
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
STATIC_VAR TreeM * G
Definition: janet.cc:31
STATIC_VAR Poly * h
Definition: janet.cc:971
STATIC_VAR gmp_float * diff
Definition: mpr_complex.cc:45
#define NULL
Definition: omList.c:12
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
int status int void size_t count
Definition: si_signals.h:59
int status int void * buf
Definition: si_signals.h:59
#define A
Definition: sirandom.c:24
#define M
Definition: sirandom.c:25
int tdeg(poly p)
Definition: walkSupport.cc:35
int gcd(int a, int b)
Definition: walkSupport.cc:836