1 /** @file exam_polygcd.cpp
3 * Some test with polynomial GCD calculations. See also the checks for
4 * rational function normalization in normalization.cpp. */
7 * GiNaC Copyright (C) 1999-2007 Johannes Gutenberg University Mainz, Germany
9 * This program is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation; either version 2 of the License, or
12 * (at your option) any later version.
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, write to the Free Software
21 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
26 const int MAX_VARIABLES = 3;
28 static symbol x("x"), z("z");
29 static symbol y[MAX_VARIABLES];
32 static unsigned poly_gcd1()
34 for (int v=1; v<=MAX_VARIABLES; v++) {
37 for (int i=0; i<v; i++) {
42 ex f = (e1 + 1) * (e1 + 2);
43 ex g = e2 * (-pow(x, 2) * y[0] * 3 + pow(y[0], 2) - 1);
46 clog << "case 1, gcd(" << f << "," << g << ") = " << r << " (should be 1)" << endl;
53 // Linearly dense quartic inputs with quadratic GCDs
54 static unsigned poly_gcd2()
56 for (int v=1; v<=MAX_VARIABLES; v++) {
59 for (int i=0; i<v; i++) {
64 ex d = pow(e1 + 1, 2);
65 ex f = d * pow(e2 - 2, 2);
66 ex g = d * pow(e1 + 2, 2);
67 ex r = gcd(f.expand(), g.expand());
68 if (!(r - d).expand().is_zero()) {
69 clog << "case 2, gcd(" << f << "," << g << ") = " << r << " (should be " << d << ")" << endl;
76 // Sparse GCD and inputs where degrees are proportional to the number of variables
77 static unsigned poly_gcd3()
79 for (int v=1; v<=MAX_VARIABLES; v++) {
80 ex e1 = pow(x, v + 1);
81 for (int i=0; i<v; i++)
82 e1 += pow(y[i], v + 1);
87 ex r = gcd(f.expand(), g.expand());
88 if (!(r - d).expand().is_zero()) {
89 clog << "case 3, gcd(" << f << "," << g << ") = " << r << " (should be " << d << ")" << endl;
96 // Variation of case 3; major performance degradation with PRS
97 static unsigned poly_gcd3p()
99 for (int v=1; v<=MAX_VARIABLES; v++) {
100 ex e1 = pow(x, v + 1);
102 for (int i=0; i<v; i++) {
103 e1 += pow(y[i], v + 1);
110 ex r = gcd(f.expand(), g.expand());
111 if (!(r - d).expand().is_zero()) {
112 clog << "case 3p, gcd(" << f << "," << g << ") = " << r << " (should be " << d << ")" << endl;
119 // Quadratic non-monic GCD; f and g have other quadratic factors
120 static unsigned poly_gcd4()
122 for (int v=1; v<=MAX_VARIABLES; v++) {
123 ex e1 = pow(x, 2) * pow(y[0], 2);
124 ex e2 = pow(x, 2) - pow(y[0], 2);
126 for (int i=1; i<v; i++) {
134 ex g = d * pow(e3 + 2, 2);
135 ex r = gcd(f.expand(), g.expand());
136 if (!(r - d).expand().is_zero()) {
137 clog << "case 4, gcd(" << f << "," << g << ") = " << r << " (should be " << d << ")" << endl;
144 // Completely dense non-monic quadratic inputs with dense non-monic linear GCDs
145 static unsigned poly_gcd5()
147 for (int v=1; v<=MAX_VARIABLES; v++) {
151 for (int i=0; i<v; i++) {
160 ex r = gcd(f.expand(), g.expand());
161 if (!(r - d).expand().is_zero()) {
162 clog << "case 5, gcd(" << f << "," << g << ") = " << r << " (should be " << d << ")" << endl;
169 // Sparse non-monic quadratic inputs with linear GCDs
170 static unsigned poly_gcd5p()
172 for (int v=1; v<=MAX_VARIABLES; v++) {
174 for (int i=0; i<v; i++)
180 ex r = gcd(f.expand(), g.expand());
181 if (!(r - d).expand().is_zero()) {
182 clog << "case 5p, gcd(" << f << "," << g << ") = " << r << " (should be " << d << ")" << endl;
189 // Trivariate inputs with increasing degrees
190 static unsigned poly_gcd6()
194 for (int j=1; j<=MAX_VARIABLES; j++) {
195 ex d = pow(x, j) * y * (z - 1);
196 ex f = d * (pow(x, j) + pow(y, j + 1) * pow(z, j) + 1);
197 ex g = d * (pow(x, j + 1) + pow(y, j) * pow(z, j + 1) - 7);
198 ex r = gcd(f.expand(), g.expand());
199 if (!(r - d).expand().is_zero()) {
200 clog << "case 6, gcd(" << f << "," << g << ") = " << r << " (should be " << d << ")" << endl;
207 // Trivariate polynomials whose GCD has common factors with its cofactors
208 static unsigned poly_gcd7()
211 ex p = x - y * z + 1;
212 ex q = x - y + z * 3;
214 for (int j=1; j<=MAX_VARIABLES; j++) {
215 for (int k=j+1; k<=4; k++) {
216 ex d = pow(p, j) * pow(q, j);
217 ex f = pow(p, j) * pow(q, k);
218 ex g = pow(p, k) * pow(q, j);
220 if (!(r - d).expand().is_zero() && !(r + d).expand().is_zero()) {
221 clog << "case 7, gcd(" << f << "," << g << ") = " << r << " (should be " << d << ")" << endl;
229 unsigned exam_polygcd()
233 cout << "examining polynomial GCD computation" << flush;
234 clog << "----------polynomial GCD computation:" << endl;
236 result += poly_gcd1(); cout << '.' << flush;
237 result += poly_gcd2(); cout << '.' << flush;
238 result += poly_gcd3(); cout << '.' << flush;
239 result += poly_gcd3p(); cout << '.' << flush; // PRS "worst" case
240 result += poly_gcd4(); cout << '.' << flush;
241 result += poly_gcd5(); cout << '.' << flush;
242 result += poly_gcd5p(); cout << '.' << flush;
243 result += poly_gcd6(); cout << '.' << flush;
244 result += poly_gcd7(); cout << '.' << flush;
247 cout << " passed " << endl;
248 clog << "(no output)" << endl;
250 cout << " failed " << endl;