001 /*
002 * $Id: GCDSubresTest.java 2724 2009-07-09 20:16:03Z kredel $
003 */
004
005 package edu.jas.ufd;
006
007
008 //import java.util.Map;
009
010 import junit.framework.Test;
011 import junit.framework.TestCase;
012 import junit.framework.TestSuite;
013
014 import edu.jas.arith.BigInteger;
015 import edu.jas.poly.ExpVector;
016 import edu.jas.poly.GenPolynomial;
017 import edu.jas.poly.GenPolynomialRing;
018 import edu.jas.poly.PolyUtil;
019 import edu.jas.poly.TermOrder;
020
021
022 /**
023 * GCD Subresultant PRS algorithm tests with JUnit.
024 * @author Heinz Kredel.
025 */
026
027 public class GCDSubresTest extends TestCase {
028
029
030 /**
031 * main.
032 */
033 public static void main(String[] args) {
034 junit.textui.TestRunner.run(suite());
035 }
036
037
038 /**
039 * Constructs a <CODE>GCDSubresTest</CODE> object.
040 * @param name String.
041 */
042 public GCDSubresTest(String name) {
043 super(name);
044 }
045
046
047 /**
048 */
049 public static Test suite() {
050 TestSuite suite = new TestSuite(GCDSubresTest.class);
051 return suite;
052 }
053
054
055 //private final static int bitlen = 100;
056
057 GreatestCommonDivisorAbstract<BigInteger> ufd;
058
059
060 TermOrder to = new TermOrder(TermOrder.INVLEX);
061
062
063 GenPolynomialRing<BigInteger> dfac;
064
065
066 GenPolynomialRing<BigInteger> cfac;
067
068
069 GenPolynomialRing<GenPolynomial<BigInteger>> rfac;
070
071
072 BigInteger ai;
073
074
075 BigInteger bi;
076
077
078 BigInteger ci;
079
080
081 BigInteger di;
082
083
084 BigInteger ei;
085
086
087 GenPolynomial<BigInteger> a;
088
089
090 GenPolynomial<BigInteger> b;
091
092
093 GenPolynomial<BigInteger> c;
094
095
096 GenPolynomial<BigInteger> d;
097
098
099 GenPolynomial<BigInteger> e;
100
101
102 GenPolynomial<GenPolynomial<BigInteger>> ar;
103
104
105 GenPolynomial<GenPolynomial<BigInteger>> br;
106
107
108 GenPolynomial<GenPolynomial<BigInteger>> cr;
109
110
111 GenPolynomial<GenPolynomial<BigInteger>> dr;
112
113
114 GenPolynomial<GenPolynomial<BigInteger>> er;
115
116
117 int rl = 5;
118
119
120 int kl = 4;
121
122
123 int ll = 5;
124
125
126 int el = 3;
127
128
129 float q = 0.3f;
130
131
132 @Override
133 protected void setUp() {
134 a = b = c = d = e = null;
135 ai = bi = ci = di = ei = null;
136 ar = br = cr = dr = er = null;
137 ufd = new GreatestCommonDivisorPrimitive<BigInteger>();
138 String[] vars = ExpVector.STDVARS(rl);
139 String[] cvars = ExpVector.STDVARS(rl - 1);
140 String[] rvars = new String[] { vars[rl - 1] };
141 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl, to, vars);
142 cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl - 1, to, cvars);
143 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to, rvars);
144 }
145
146
147 @Override
148 protected void tearDown() {
149 a = b = c = d = e = null;
150 ai = bi = ci = di = ei = null;
151 ar = br = cr = dr = er = null;
152 ufd = null;
153 dfac = null;
154 cfac = null;
155 rfac = null;
156 }
157
158
159 /**
160 * Test base gcd subresultant.
161 *
162 */
163 public void testBaseGcdSubres() {
164
165 ufd = new GreatestCommonDivisorSubres<BigInteger>();
166
167 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 1, to);
168
169 for (int i = 0; i < 1; i++) {
170 a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q);
171 b = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q);
172 c = dfac.random(kl * (i + 2), ll + 2, el + 2, q);
173 c = c.multiply(dfac.univariate(0));
174 if (c.isZERO()) {
175 // skip for this turn
176 continue;
177 }
178 //a = ufd.basePrimitivePart(a);
179 //b = ufd.basePrimitivePart(b);
180 c = ufd.basePrimitivePart(c).abs();
181
182 //System.out.println("a = " + a);
183 //System.out.println("b = " + b);
184 //System.out.println("c = " + c);
185
186 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
187 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
188 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
189
190 a = a.multiply(c);
191 b = b.multiply(c);
192
193 d = ufd.baseGcd(a, b);
194 e = PolyUtil.<BigInteger> basePseudoRemainder(d, c);
195 //System.out.println("d = " + d);
196 //System.out.println("c = " + c);
197 assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
198
199 e = PolyUtil.<BigInteger> basePseudoRemainder(a, d);
200 //System.out.println("e = " + e);
201 assertTrue("gcd(a,b) | a" + e, e.isZERO());
202
203 e = PolyUtil.<BigInteger> basePseudoRemainder(b, d);
204 //System.out.println("e = " + e);
205 assertTrue("gcd(a,b) | b" + e, e.isZERO());
206 }
207 }
208
209
210 /**
211 * Test recursive gcd subresultant.
212 *
213 */
214 public void testRecursiveGCDsubres() {
215
216 ufd = new GreatestCommonDivisorSubres<BigInteger>();
217
218 di = new BigInteger(1);
219 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2, to);
220 cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2 - 1, to);
221 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to);
222
223 for (int i = 0; i < 5; i++) {
224 ar = rfac.random(kl, ll, el + i, q);
225 br = rfac.random(kl, ll, el, q);
226 cr = rfac.random(kl, ll, el, q);
227 cr = ufd.recursivePrimitivePart(cr).abs();
228 //System.out.println("ar = " + ar);
229 //System.out.println("br = " + br);
230 //System.out.println("cr = " + cr);
231
232 if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
233 // skip for this turn
234 continue;
235 }
236 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
237 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
238 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
239
240 ar = ar.multiply(cr);
241 br = br.multiply(cr);
242 //System.out.println("ar = " + ar);
243 //System.out.println("br = " + br);
244 //System.out.println("cr = " + cr);
245
246 dr = ufd.recursiveUnivariateGcd(ar, br);
247 //System.out.println("dr = " + dr);
248
249 er = PolyUtil.<BigInteger> recursivePseudoRemainder(dr, cr);
250 //System.out.println("er = " + er);
251 assertTrue("c | gcd(ac,bc) " + er, er.isZERO());
252
253 er = PolyUtil.<BigInteger> recursivePseudoRemainder(ar, dr);
254 //System.out.println("er = " + er);
255 assertTrue("gcd(a,b) | a" + er, er.isZERO());
256
257 er = PolyUtil.<BigInteger> recursivePseudoRemainder(br, dr);
258 //System.out.println("er = " + er);
259 assertTrue("gcd(a,b) | b" + er, er.isZERO());
260 }
261 }
262
263
264 /**
265 * Test arbitrary recursive gcd subresultant.
266 *
267 */
268 public void testArbitraryRecursiveGCDsubres() {
269
270 ufd = new GreatestCommonDivisorSubres<BigInteger>();
271
272 di = new BigInteger(1);
273 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2, to);
274 cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2 - 1, to);
275 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to);
276
277 for (int i = 0; i < 5; i++) {
278 ar = rfac.random(kl, ll, el + i, q);
279 br = rfac.random(kl, ll, el, q);
280 cr = rfac.random(kl, ll, el, q);
281 cr = ufd.recursivePrimitivePart(cr).abs();
282 //System.out.println("ar = " + ar);
283 //System.out.println("br = " + br);
284 //System.out.println("cr = " + cr);
285
286 if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
287 // skip for this turn
288 continue;
289 }
290 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
291 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
292 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
293
294 ar = ar.multiply(cr);
295 br = br.multiply(cr);
296 //System.out.println("ar = " + ar);
297 //System.out.println("br = " + br);
298 //System.out.println("cr = " + cr);
299
300 dr = ufd.recursiveGcd(ar, br);
301 //System.out.println("dr = " + dr);
302
303 er = PolyUtil.<BigInteger> recursivePseudoRemainder(dr, cr);
304 //System.out.println("er = " + er);
305 assertTrue("c | gcd(ac,bc) " + er, er.isZERO());
306
307 er = PolyUtil.<BigInteger> recursivePseudoRemainder(ar, dr);
308 //System.out.println("er = " + er);
309 assertTrue("gcd(a,b) | a" + er, er.isZERO());
310
311 er = PolyUtil.<BigInteger> recursivePseudoRemainder(br, dr);
312 //System.out.println("er = " + er);
313 assertTrue("gcd(a,b) | b" + er, er.isZERO());
314 }
315 }
316
317
318 /**
319 * Test gcd subresultant.
320 *
321 */
322 public void testGCDsubres() {
323
324 //GreatestCommonDivisorAbstract<BigInteger> ufd_pp;
325 //ufd_pp = ufd;
326
327 ufd = new GreatestCommonDivisorSubres<BigInteger>();
328
329 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 5, to);
330
331 for (int i = 0; i < 2; i++) {
332 a = dfac.random(kl, ll, el, q);
333 b = dfac.random(kl, ll, el, q);
334 c = dfac.random(kl, ll, el, q);
335 c = c.multiply(dfac.univariate(0));
336 c = ufd.primitivePart(c).abs();
337 //System.out.println("a = " + a);
338 //System.out.println("b = " + b);
339 //System.out.println("c = " + c);
340
341 if (a.isZERO() || b.isZERO() || c.isZERO()) {
342 // skip for this turn
343 continue;
344 }
345 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
346 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
347 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
348
349 a = a.multiply(c);
350 b = b.multiply(c);
351 //System.out.println("a = " + a);
352 //System.out.println("b = " + b);
353 //System.out.println("c = " + c);
354
355 d = ufd.gcd(a, b);
356 //System.out.println("c = " + c);
357 //System.out.println("d = " + d);
358
359 e = PolyUtil.<BigInteger> basePseudoRemainder(d, c);
360 //System.out.println("e = " + e);
361 assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
362
363 e = PolyUtil.<BigInteger> basePseudoRemainder(a, d);
364 //System.out.println("e = " + e);
365 assertTrue("gcd(a,b) | a " + e, e.isZERO());
366
367 e = PolyUtil.<BigInteger> basePseudoRemainder(b, d);
368 //System.out.println("e = " + e);
369 assertTrue("gcd(a,b) | b " + e, e.isZERO());
370 }
371 }
372
373
374 /**
375 * Test base subresultant.
376 *
377 */
378 public void testBaseSubresultant() {
379
380 GreatestCommonDivisorSubres<BigInteger> ufd = new GreatestCommonDivisorSubres<BigInteger>();
381
382 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 1, to);
383
384 for (int i = 0; i < 1; i++) {
385 a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q);
386 b = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q);
387 c = dfac.random(kl, ll, 2, q);
388 //c = c.multiply( cfac.univariate(0) );
389 //c = dfac.getONE();
390 if (c.isZERO()) {
391 // skip for this turn
392 continue;
393 }
394 //System.out.println("a = " + a);
395 //System.out.println("b = " + b);
396 //System.out.println("c = " + c);
397
398 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
399 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
400 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
401
402 a = a.multiply(c);
403 b = b.multiply(c);
404
405 d = ufd.baseResultant(a, b);
406 e = ufd.baseGcd(a, b);
407 //System.out.println("d = " + d);
408 //System.out.println("c = " + c);
409 //System.out.println("e = " + e);
410 if (!e.isConstant()) {
411 assertTrue("res(a,b) == 0 " + d, d.isZERO());
412 } else {
413 assertTrue("res(a,b) != 0 " + d, !d.isZERO());
414 }
415 }
416 }
417
418
419 /**
420 * Test recursive subresultant.
421 *
422 */
423 public void testRecursiveSubresultant() {
424
425 GreatestCommonDivisorSubres<BigInteger> ufd = new GreatestCommonDivisorSubres<BigInteger>();
426
427 di = new BigInteger(1);
428 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2, to);
429 cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2 - 1, to);
430 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to);
431
432 for (int i = 0; i < 5; i++) {
433 ar = rfac.random(kl, ll, el + i, q);
434 br = rfac.random(kl, ll, el, q);
435 cr = rfac.random(kl, ll, 2, q);
436 //cr = rfac.getONE();
437 //cr = ufd.recursivePrimitivePart(cr).abs();
438 //cr = cr.multiply( rfac.univariate(0) );
439 //System.out.println("ar = " + ar);
440 //System.out.println("br = " + br);
441 //System.out.println("cr = " + cr);
442
443 if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
444 // skip for this turn
445 continue;
446 }
447 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
448 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
449 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
450
451 ar = ar.multiply(cr);
452 br = br.multiply(cr);
453 //System.out.println("ar = " + ar);
454 //System.out.println("br = " + br);
455
456 dr = ufd.recursiveResultant(ar, br);
457 //System.out.println("cr = " + cr);
458 //System.out.println("dr = " + dr);
459 er = ufd.recursiveUnivariateGcd(ar, br);
460 //System.out.println("er = " + er);
461
462 if (er.isZERO()) { // cannot happen since a, b, c != 0
463 assertTrue("res(a,b) = 0 " + dr + " e = " + er, dr.isZERO());
464 }
465 if (er.isConstant() && er.leadingBaseCoefficient().isConstant()) {
466 assertTrue("res(a,b) != 0 " + dr + ", e = " + er + ", a = " + ar + ", b = " + br, !dr
467 .isZERO());
468 } else {
469 assertTrue("res(a,b) = 0 or not const " + dr + ", e = " + er + ", a = " + ar + ", b = " + br,
470 dr.isZERO() || !dr.isConstant() || !dr.leadingBaseCoefficient().isConstant());
471 }
472
473 }
474 }
475
476
477 /**
478 * Test subresultant.
479 *
480 */
481 public void testSubres() {
482
483 GreatestCommonDivisorSubres<BigInteger> ufd = new GreatestCommonDivisorSubres<BigInteger>();
484
485 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 3, to);
486
487 for (int i = 0; i < 2; i++) {
488 a = dfac.random(kl, ll, el, q);
489 b = dfac.random(kl, ll, el, q);
490 c = dfac.random(kl, ll, 2, q);
491 //c = dfac.getONE();
492 //c = c.multiply( dfac.univariate(0) );
493 //c = ufd.primitivePart(c).abs();
494 //System.out.println("a = " + a);
495 //System.out.println("b = " + b);
496 //System.out.println("c = " + c);
497
498 if (a.isZERO() || b.isZERO() || c.isZERO()) {
499 // skip for this turn
500 continue;
501 }
502 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
503 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
504 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
505
506 a = a.multiply(c);
507 b = b.multiply(c);
508 //System.out.println("a = " + a);
509 //System.out.println("b = " + b);
510
511 d = ufd.resultant(a, b);
512 e = ufd.gcd(a, b);
513 //System.out.println("c = " + c);
514 //System.out.println("d = " + d);
515 //System.out.println("e = " + e);
516
517 if (e.isZERO()) { // cannot happen since a, b, c != 0
518 assertTrue("res(a,b) = 0 " + d + " e = " + e, d.isZERO());
519 }
520 if (e.isConstant()) {
521 assertTrue("res(a,b) != 0 " + d + ", e = " + e + ", a = " + a + ", b = " + b, !d.isZERO());
522 } else {
523 assertTrue("res(a,b) = 0 or not const " + d + ", e = " + e + ", a = " + a + ", b = " + b, d
524 .isZERO()
525 || !d.isConstant());
526 }
527
528 }
529 }
530
531 }