Source code

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