001 /*
002 * $Id: GCDSubresRatTest.java 3575 2011-03-20 23:11:18Z kredel $
003 */
004
005 package edu.jas.ufd;
006
007
008 import java.util.ArrayList;
009 import java.util.List;
010
011 import junit.framework.Test;
012 import junit.framework.TestCase;
013 import junit.framework.TestSuite;
014
015 import edu.jas.arith.BigRational;
016 import edu.jas.poly.ExpVector;
017 import edu.jas.poly.GenPolynomial;
018 import edu.jas.poly.GenPolynomialRing;
019 import edu.jas.poly.PolyUtil;
020 import edu.jas.poly.TermOrder;
021
022
023 /**
024 * GCD Subres with rational coefficients algorithm tests with JUnit.
025 * @author Heinz Kredel.
026 */
027
028 public class GCDSubresRatTest extends TestCase {
029
030
031 /**
032 * main.
033 */
034 public static void main(String[] args) {
035 junit.textui.TestRunner.run(suite());
036 }
037
038
039 /**
040 * Constructs a <CODE>GCDSubresRatTest</CODE> object.
041 * @param name String.
042 */
043 public GCDSubresRatTest(String name) {
044 super(name);
045 }
046
047
048 /**
049 */
050 public static Test suite() {
051 TestSuite suite = new TestSuite(GCDSubresRatTest.class);
052 return suite;
053 }
054
055
056 //private final static int bitlen = 100;
057
058 GreatestCommonDivisorSubres<BigRational> ufd;
059
060
061 TermOrder to = new TermOrder(TermOrder.INVLEX);
062
063
064 GenPolynomialRing<BigRational> dfac;
065
066
067 GenPolynomialRing<BigRational> cfac;
068
069
070 GenPolynomialRing<GenPolynomial<BigRational>> rfac;
071
072
073 BigRational mi;
074
075
076 BigRational ai;
077
078
079 BigRational bi;
080
081
082 BigRational ci;
083
084
085 BigRational di;
086
087
088 BigRational ei;
089
090
091 GenPolynomial<BigRational> a;
092
093
094 GenPolynomial<BigRational> b;
095
096
097 GenPolynomial<BigRational> c;
098
099
100 GenPolynomial<BigRational> d;
101
102
103 GenPolynomial<BigRational> e;
104
105
106 GenPolynomial<GenPolynomial<BigRational>> ar;
107
108
109 GenPolynomial<GenPolynomial<BigRational>> br;
110
111
112 GenPolynomial<GenPolynomial<BigRational>> cr;
113
114
115 GenPolynomial<GenPolynomial<BigRational>> dr;
116
117
118 GenPolynomial<GenPolynomial<BigRational>> er;
119
120
121 int rl = 3;
122
123
124 int kl = 2;
125
126
127 int ll = 3;
128
129
130 int el = 3;
131
132
133 float q = 0.25f;
134
135
136 @Override
137 protected void setUp() {
138 a = b = c = d = e = null;
139 ai = bi = ci = di = ei = null;
140 ar = br = cr = dr = er = null;
141 mi = new BigRational(1);
142 ufd = new GreatestCommonDivisorSubres<BigRational>();
143 String[] vars = ExpVector.STDVARS(rl);
144 String[] cvars = ExpVector.STDVARS(rl - 1);
145 String[] rvars = new String[] { vars[rl - 1] };
146 dfac = new GenPolynomialRing<BigRational>(mi, rl, to, vars);
147 cfac = new GenPolynomialRing<BigRational>(mi, rl - 1, to, cvars);
148 rfac = new GenPolynomialRing<GenPolynomial<BigRational>>(cfac, 1, to, rvars);
149 //System.out.println("mi = " + mi);
150 }
151
152
153 @Override
154 protected void tearDown() {
155 a = b = c = d = e = null;
156 ai = bi = ci = di = ei = null;
157 ar = br = cr = dr = er = null;
158 mi = null;
159 ufd = null;
160 dfac = null;
161 cfac = null;
162 rfac = null;
163 }
164
165
166 /**
167 * Test gcd.
168 */
169 public void testGcd() {
170 for (int i = 0; i < 1; i++) {
171 a = dfac.random(kl * (i + 2), ll + 2 * i, el + 0 * i, q);
172 b = dfac.random(kl * (i + 2), ll + 2 * i, el + 0 * i, q);
173 c = dfac.random(kl * (i + 2), ll + 2 * i, el + 0 * i, q);
174 c = c.multiply(dfac.univariate(0));
175 //a = ufd.basePrimitivePart(a);
176 //b = ufd.basePrimitivePart(b);
177
178 if (a.isZERO() || b.isZERO() || c.isZERO()) {
179 // skip for this turn
180 continue;
181 }
182 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
183 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
184 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
185
186 a = a.multiply(c);
187 b = b.multiply(c);
188 //System.out.println("a = " + a);
189 //System.out.println("b = " + b);
190
191 d = ufd.gcd(a, b);
192
193 c = ufd.basePrimitivePart(c).abs();
194 e = PolyUtil.<BigRational> basePseudoRemainder(d, c);
195 //System.out.println("c = " + c);
196 //System.out.println("d = " + d);
197 assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
198
199 e = PolyUtil.<BigRational> basePseudoRemainder(a, d);
200 //System.out.println("e = " + e);
201 assertTrue("gcd(a,b) | a" + e, e.isZERO());
202
203 e = PolyUtil.<BigRational> 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 base quotioent and remainder.
212 */
213 public void testBaseQR() {
214 dfac = new GenPolynomialRing<BigRational>(mi, 1, to);
215
216 for (int i = 0; i < 3; i++) {
217 a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q);
218 c = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q);
219 //a = ufd.basePrimitivePart(a).abs();
220 //c = ufd.basePrimitivePart(c);
221 do {
222 ci = mi.random(kl * (i + 2));
223 ci = ci.sum(mi.getONE());
224 } while (ci.isZERO());
225
226 //System.out.println("a = " + a);
227 //System.out.println("c = " + c);
228 //System.out.println("ci = " + ci);
229
230 if (a.isZERO() || c.isZERO()) {
231 // skip for this turn
232 continue;
233 }
234 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
235 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
236 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
237
238 b = a.multiply(c);
239 //System.out.println("b = " + b);
240 d = PolyUtil.<BigRational> basePseudoRemainder(b, c);
241 //System.out.println("d = " + d);
242
243 assertTrue("rem(ac,c) == 0", d.isZERO());
244
245 b = a.multiply(ci);
246 //System.out.println("b = " + b);
247 d = b.divide(ci);
248 //System.out.println("d = " + d);
249
250 assertEquals("a == ac/c", a, d);
251
252 b = a.multiply(c);
253 //System.out.println("b = " + b);
254 d = PolyUtil.<BigRational> basePseudoDivide(b, c);
255 //System.out.println("d = " + d);
256
257 assertEquals("a == ac/c", a, d);
258 }
259 }
260
261
262 /**
263 * Test base content and primitive part.
264 */
265 public void testBaseContentPP() {
266 for (int i = 0; i < 9; i++) {
267 c = dfac.random(kl * (i + 2), ll + 2 * i, el + i, q);
268 c = c.multiply(mi.random(kl * (i + 2)));
269
270 if (c.isZERO()) {
271 // skip for this turn
272 continue;
273 }
274 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
275 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
276 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
277
278 ci = ufd.baseContent(c);
279 d = ufd.basePrimitivePart(c);
280 //System.out.println("c = " + c);
281 //System.out.println("ci = " + ci);
282 //System.out.println("d = " + d);
283
284 a = d.multiply(ci);
285 assertEquals("c == cont(c)pp(c)", c, a);
286 }
287 }
288
289
290 public void testDiscriminant() {
291 dfac = new GenPolynomialRing<BigRational>(mi, 1, to);
292 for (int i = 0; i < 5; i++) {
293 c = dfac.random(kl * (i + 1), ll + 2 * i, el + i, q*2);
294 //System.out.println("c = " + c);
295 if (c.isZERO()) {
296 // skip for this turn
297 continue;
298 }
299 c = c.multiply(c);
300 d = ufd.baseDiscriminant(c);
301 //System.out.println("d = " + d);
302
303 assertTrue("disc(c^2) == 0", d.isZERO());
304 }
305 }
306
307
308 /**
309 * Test base gcd.
310 */
311 public void testBaseGcd() {
312 dfac = new GenPolynomialRing<BigRational>(mi, 1, to);
313
314 for (int i = 0; i < 3; i++) {
315 a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q);
316 b = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q);
317 c = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q);
318 //a = ufd.basePrimitivePart(a);
319 //b = ufd.basePrimitivePart(b);
320 //c = ufd.basePrimitivePart(c).abs();
321
322 //System.out.println("a = " + a);
323 //System.out.println("b = " + b);
324 //System.out.println("c = " + c);
325
326 if (a.isZERO() || b.isZERO() || c.isZERO()) {
327 // skip for this turn
328 continue;
329 }
330 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
331 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
332 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
333
334 a = a.multiply(c);
335 b = b.multiply(c);
336
337 d = ufd.baseGcd(a, b);
338 e = PolyUtil.<BigRational> basePseudoRemainder(d, c);
339 //System.out.println("d = " + d);
340
341 assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
342 }
343 }
344
345
346 /**
347 * Test recursive quotioent and remainder.
348 */
349 public void testRecursiveQR() {
350 dfac = new GenPolynomialRing<BigRational>(mi, 2, to);
351 cfac = new GenPolynomialRing<BigRational>(mi, 2 - 1, to);
352 rfac = new GenPolynomialRing<GenPolynomial<BigRational>>(cfac, 1, to);
353
354 for (int i = 0; i < 3; i++) {
355 a = dfac.random(kl * (i + 1), ll + i, el + i, q);
356 a = ufd.basePrimitivePart(a).abs();
357
358 c = dfac.random(kl * (i + 1), ll + i, el + i, q);
359 c = ufd.basePrimitivePart(a).abs();
360 cr = PolyUtil.<BigRational> recursive(rfac, c);
361
362 c = cfac.random(kl * (i + 1), ll + 2 * i, el + 2 * i, q);
363 c = ufd.basePrimitivePart(c).abs();
364
365 ar = PolyUtil.<BigRational> recursive(rfac, a);
366 //System.out.println("ar = " + ar);
367 //System.out.println("a = " + a);
368 //System.out.println("c = " + c);
369 //System.out.println("cr = " + cr);
370
371 if (cr.isZERO() || c.isZERO()) {
372 // skip for this turn
373 continue;
374 }
375 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
376 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
377 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
378
379
380 br = ar.multiply(cr);
381 //System.out.println("br = " + br);
382 dr = PolyUtil.<BigRational> recursivePseudoRemainder(br, cr);
383 //System.out.println("dr = " + dr);
384 d = PolyUtil.<BigRational> distribute(dfac, dr);
385 //System.out.println("d = " + d);
386
387 assertTrue("rem(ac,c) == 0", d.isZERO());
388
389 br = ar.multiply(c);
390 //System.out.println("br = " + br);
391 dr = PolyUtil.<BigRational> recursiveDivide(br, c);
392 //System.out.println("dr = " + dr);
393 d = PolyUtil.<BigRational> distribute(dfac, dr);
394 //System.out.println("d = " + d);
395
396 assertEquals("a == ac/c", a, d);
397 }
398 }
399
400
401 /**
402 * Test recursive content and primitive part.
403 */
404 public void testRecursiveContentPP() {
405 dfac = new GenPolynomialRing<BigRational>(mi, 2, to);
406 cfac = new GenPolynomialRing<BigRational>(mi, 2 - 1, to);
407 rfac = new GenPolynomialRing<GenPolynomial<BigRational>>(cfac, 1, to);
408
409 for (int i = 0; i < 3; i++) {
410 cr = rfac.random(kl * (i + 2), ll + 2 * i, el + i, q);
411 //System.out.println("cr = " + cr);
412
413 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
414 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
415 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
416
417 c = ufd.recursiveContent(cr);
418 dr = ufd.recursivePrimitivePart(cr);
419 //System.out.println("c = " + c);
420 //System.out.println("dr = " + dr);
421
422 ar = dr.multiply(c);
423 assertEquals("c == cont(c)pp(c)", cr, ar);
424 }
425 }
426
427
428 /**
429 * Test recursive gcd.
430 */
431 public void testRecursiveGCD() {
432 dfac = new GenPolynomialRing<BigRational>(mi, 2, to);
433 cfac = new GenPolynomialRing<BigRational>(mi, 2 - 1, to);
434 rfac = new GenPolynomialRing<GenPolynomial<BigRational>>(cfac, 1, to);
435
436 for (int i = 0; i < 2; i++) {
437 ar = rfac.random(kl, ll, el + i, q);
438 br = rfac.random(kl, ll, el, q);
439 cr = rfac.random(kl, ll, el, q);
440 //System.out.println("ar = " + ar);
441 //System.out.println("br = " + br);
442 //System.out.println("cr = " + cr);
443
444 if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
445 // skip for this turn
446 continue;
447 }
448 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
449 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
450 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
451
452 ar = ar.multiply(cr);
453 br = br.multiply(cr);
454 //System.out.println("ar = " + ar);
455 //System.out.println("br = " + br);
456
457 dr = ufd.recursiveUnivariateGcd(ar, br);
458 //System.out.println("dr = " + dr);
459
460 er = PolyUtil.<BigRational> recursivePseudoRemainder(dr, cr);
461 //System.out.println("er = " + er);
462
463 assertTrue("c | gcd(ac,bc) " + er, er.isZERO());
464 }
465 }
466
467
468 /**
469 * Test arbitrary recursive gcd.
470 */
471 public void testArbitraryRecursiveGCD() {
472 dfac = new GenPolynomialRing<BigRational>(mi, 2, to);
473 cfac = new GenPolynomialRing<BigRational>(mi, 2 - 1, to);
474 rfac = new GenPolynomialRing<GenPolynomial<BigRational>>(cfac, 1, to);
475
476 for (int i = 0; i < 2; i++) {
477 ar = rfac.random(kl, ll, el + i, q);
478 br = rfac.random(kl, ll, el, q);
479 cr = rfac.random(kl, ll, el, q);
480 //System.out.println("ar = " + ar);
481 //System.out.println("br = " + br);
482 //System.out.println("cr = " + cr);
483
484 if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
485 // skip for this turn
486 continue;
487 }
488 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
489 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
490 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
491
492 ar = ar.multiply(cr);
493 br = br.multiply(cr);
494 //System.out.println("ar = " + ar);
495 //System.out.println("br = " + br);
496
497 dr = ufd.recursiveGcd(ar, br);
498 //System.out.println("dr = " + dr);
499
500 er = PolyUtil.<BigRational> recursivePseudoRemainder(dr, cr);
501 //System.out.println("er = " + er);
502
503 assertTrue("c | gcd(ac,bc) " + er, er.isZERO());
504 }
505 }
506
507
508 /**
509 * Test content and primitive part.
510 */
511 public void testContentPP() {
512 dfac = new GenPolynomialRing<BigRational>(mi, 3, to);
513
514 for (int i = 0; i < 3; i++) {
515 c = dfac.random(kl * (i + 2), ll + 2 * i, el + i, q);
516 //System.out.println("cr = " + cr);
517
518 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
519 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
520 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
521
522 a = ufd.content(c);
523 e = a.extend(dfac, 0, 0L);
524 b = ufd.primitivePart(c);
525 //System.out.println("c = " + c);
526 //System.out.println("a = " + a);
527 //System.out.println("e = " + e);
528 //System.out.println("b = " + b);
529
530 d = e.multiply(b);
531 assertEquals("c == cont(c)pp(c)", d, c);
532 }
533 }
534
535
536 /**
537 * Test gcd 3 variables.
538 */
539 public void testGCD3() {
540 dfac = new GenPolynomialRing<BigRational>(mi, 3, to);
541
542 for (int i = 0; i < 3; i++) {
543 a = dfac.random(kl, ll, el + i, q);
544 b = dfac.random(kl, ll, el, q);
545 c = dfac.random(kl, ll, el, q);
546 //System.out.println("a = " + a);
547 //System.out.println("b = " + b);
548 //System.out.println("c = " + c);
549
550 if (a.isZERO() || b.isZERO() || c.isZERO()) {
551 // skip for this turn
552 continue;
553 }
554 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
555 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
556 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
557
558 a = a.multiply(c);
559 b = b.multiply(c);
560 //System.out.println("a = " + a);
561 //System.out.println("b = " + b);
562
563 d = ufd.gcd(a, b);
564 //System.out.println("d = " + d);
565
566 e = PolyUtil.<BigRational> basePseudoRemainder(d, c);
567 //System.out.println("e = " + e);
568
569 assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
570 }
571 }
572
573
574 /**
575 * Test gcd.
576 */
577 public void testGCD() {
578 // dfac = new GenPolynomialRing<BigRational>(mi,3,to);
579
580 for (int i = 0; i < 1; i++) {
581 a = dfac.random(kl, ll, el, q);
582 b = dfac.random(kl, ll, el, q);
583 c = dfac.random(kl, ll, el, q);
584 //System.out.println("a = " + a);
585 //System.out.println("b = " + b);
586 //System.out.println("c = " + c);
587
588 if (a.isZERO() || b.isZERO() || c.isZERO()) {
589 // skip for this turn
590 continue;
591 }
592 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
593 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
594 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
595
596 a = a.multiply(c);
597 b = b.multiply(c);
598 //System.out.println("a = " + a);
599 //System.out.println("b = " + b);
600
601 d = ufd.gcd(a, b);
602 //System.out.println("d = " + d);
603
604 e = PolyUtil.<BigRational> basePseudoRemainder(d, c);
605 //System.out.println("e = " + e);
606 assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
607
608 e = PolyUtil.<BigRational> basePseudoRemainder(a, d);
609 //System.out.println("e = " + e);
610 assertTrue("gcd(a,b) | a " + e, e.isZERO());
611
612 e = PolyUtil.<BigRational> basePseudoRemainder(b, d);
613 //System.out.println("e = " + e);
614 assertTrue("gcd(a,b) | b " + e, e.isZERO());
615 }
616 }
617
618
619 /**
620 * Test lcm.
621 */
622 public void testLCM() {
623 dfac = new GenPolynomialRing<BigRational>(mi, 3, to);
624
625 for (int i = 0; i < 1; i++) {
626 a = dfac.random(kl, ll, el, q);
627 b = dfac.random(kl, ll, el, q);
628 c = dfac.random(kl, 3, 2, q);
629 //System.out.println("a = " + a);
630 //System.out.println("b = " + b);
631 //System.out.println("c = " + c);
632
633 if (a.isZERO() || b.isZERO() || c.isZERO()) {
634 // skip for this turn
635 continue;
636 }
637 assertTrue("length( a" + i + " ) <> 0", a.length() > 0);
638 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
639 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
640
641 a = a.multiply(c);
642 b = b.multiply(c);
643
644 c = ufd.gcd(a, b);
645 //System.out.println("c = " + c);
646
647 d = ufd.lcm(a, b);
648 //System.out.println("d = " + d);
649
650 e = c.multiply(d);
651 //System.out.println("e = " + e);
652 c = a.multiply(b);
653 //System.out.println("c = " + c);
654
655 assertEquals("ab == gcd(a,b)lcm(ab)", c, e);
656 }
657 }
658
659
660 /**
661 * Test co-prime factors.
662 */
663 public void testCoPrime() {
664 dfac = new GenPolynomialRing<BigRational>(mi, 3, to);
665
666 a = dfac.random(kl, 3, 2, q);
667 b = dfac.random(kl, 3, 2, q);
668 c = dfac.random(kl, 3, 2, q);
669 //System.out.println("a = " + a);
670 //System.out.println("b = " + b);
671 //System.out.println("c = " + c);
672
673 if (a.isZERO() || b.isZERO() || c.isZERO()) {
674 // skip for this turn
675 return;
676 }
677 assertTrue("length( a ) <> 0", a.length() > 0);
678
679 d = a.multiply(a).multiply(b).multiply(b).multiply(b).multiply(c);
680 e = a.multiply(b).multiply(c);
681 //System.out.println("d = " + d);
682 //System.out.println("c = " + c);
683
684 List<GenPolynomial<BigRational>> F = new ArrayList<GenPolynomial<BigRational>>(5);
685 F.add(d);
686 F.add(a);
687 F.add(b);
688 F.add(c);
689 F.add(e);
690
691
692 List<GenPolynomial<BigRational>> P = ufd.coPrime(F);
693 //System.out.println("F = " + F);
694 //System.out.println("P = " + P);
695
696 assertTrue("is co-prime ", ufd.isCoPrime(P));
697 assertTrue("is co-prime of ", ufd.isCoPrime(P, F));
698
699
700 //P = ufd.coPrimeSquarefree(F);
701 //System.out.println("F = " + F);
702 //System.out.println("P = " + P);
703 //assertTrue("is co-prime ", ufd.isCoPrime(P) );
704 //assertTrue("is co-prime of ", ufd.isCoPrime(P,F) );
705
706
707 P = ufd.coPrimeRec(F);
708 //System.out.println("F = " + F);
709 //System.out.println("P = " + P);
710
711 assertTrue("is co-prime ", ufd.isCoPrime(P));
712 assertTrue("is co-prime of ", ufd.isCoPrime(P, F));
713 }
714
715 }