Source code

001/*
002 * $Id: GCDPrimitiveTest.java 3789 2011-10-01 18:54:43Z kredel $
003 */
004
005package edu.jas.ufd;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011import org.apache.log4j.BasicConfigurator;
012
013import junit.framework.Test;
014import junit.framework.TestCase;
015import junit.framework.TestSuite;
016
017import edu.jas.arith.BigInteger;
018import edu.jas.arith.BigRational;
019import edu.jas.poly.ExpVector;
020import edu.jas.poly.GenPolynomial;
021import edu.jas.poly.GenPolynomialRing;
022import edu.jas.poly.PolyUtil;
023import edu.jas.poly.TermOrder;
024
025
026/**
027 * GCD Primitive PRS algorithm tests with JUnit.
028 * @author Heinz Kredel.
029 */
030
031public 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}