Source code

001/*
002 * $Id: GCDSubresRatTest.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 junit.framework.Test;
012import junit.framework.TestCase;
013import junit.framework.TestSuite;
014
015import edu.jas.arith.BigRational;
016import edu.jas.poly.ExpVector;
017import edu.jas.poly.GenPolynomial;
018import edu.jas.poly.GenPolynomialRing;
019import edu.jas.poly.PolyUtil;
020import edu.jas.poly.TermOrder;
021
022
023/**
024 * GCD Subres with rational coefficients algorithm tests with JUnit.
025 * @author Heinz Kredel.
026 */
027
028public 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}