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