Source code

001/*
002 * $Id: FDUtilTest.java 5863 2018-07-20 11:13:34Z kredel $
003 */
004
005package edu.jas.fd;
006
007
008
009import edu.jas.arith.BigInteger;
010import edu.jas.arith.BigRational;
011import edu.jas.kern.ComputerThreads;
012import edu.jas.poly.GenPolynomial;
013import edu.jas.poly.GenSolvablePolynomial;
014import edu.jas.poly.GenSolvablePolynomialRing;
015import edu.jas.poly.PolyUtil;
016import edu.jas.poly.RecSolvablePolynomial;
017import edu.jas.poly.RecSolvablePolynomialRing;
018import edu.jas.poly.RelationGenerator;
019import edu.jas.poly.TermOrder;
020import edu.jas.poly.WeylRelationsIterated;
021
022import junit.framework.Test;
023import junit.framework.TestCase;
024import junit.framework.TestSuite;
025
026
027/**
028 * FDUtil tests with JUnit.
029 * @author Heinz Kredel
030 */
031
032public class FDUtilTest extends TestCase {
033
034
035    /**
036     * main.
037     */
038    public static void main(String[] args) {
039        junit.textui.TestRunner.run(suite());
040        ComputerThreads.terminate();
041    }
042
043
044    /**
045     * Constructs a <CODE>FDUtilTest</CODE> object.
046     * @param name String.
047     */
048    public FDUtilTest(String name) {
049        super(name);
050    }
051
052
053    /**
054     */
055    public static Test suite() {
056        TestSuite suite = new TestSuite(FDUtilTest.class);
057        return suite;
058    }
059
060
061    TermOrder to = new TermOrder(TermOrder.INVLEX);
062
063
064    GenSolvablePolynomialRing<BigInteger> dfac;
065
066
067    GenSolvablePolynomialRing<BigRational> rdfac;
068
069
070    GenSolvablePolynomialRing<GenPolynomial<BigInteger>> rfac;
071
072
073    GenSolvablePolynomialRing<GenPolynomial<BigRational>> rrfac;
074
075
076    RecSolvablePolynomialRing<BigRational> rsfac;
077
078
079    GenSolvablePolynomial<BigInteger> a, b, c, d, e, f;
080
081
082    GenSolvablePolynomial<GenPolynomial<BigInteger>> ar, br, cr, dr, er, fr;
083
084
085    GenSolvablePolynomial<GenPolynomial<BigRational>> arr, brr, abrr, barr, crr, drr, err, frr, x1;
086
087
088    RecSolvablePolynomial<BigRational> as, bs, cs, ds, es, fs;
089
090
091    int rl = 4;
092
093
094    int kl = 2;
095
096
097    int ll = 4;
098
099
100    int el = 3;
101
102
103    float q = 0.35f;
104
105
106    @Override
107    protected void setUp() {
108        a = b = c = d = e = null;
109        ar = br = cr = dr = er = null;
110        String[] vars = new String[] { "a", "b", "c", "d" };
111        dfac = new GenSolvablePolynomialRing<BigInteger>(new BigInteger(1), rl, to, vars);
112        RelationGenerator<BigInteger> wl = new WeylRelationsIterated<BigInteger>();
113        dfac.addRelations(wl);
114        rfac = dfac.recursive(1);
115        rdfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), rl, to, vars);
116        RelationGenerator<BigRational> wlr = new WeylRelationsIterated<BigRational>();
117        rdfac.addRelations(wlr);
118        rrfac = rdfac.recursive(1);
119    }
120
121
122    @Override
123    protected void tearDown() {
124        a = b = c = d = e = null;
125        ar = br = cr = dr = er = null;
126        dfac = null;
127        rfac = null;
128    }
129
130
131    /**
132     * Test base pseudo division.
133     */
134    public void testBasePseudoDivisionExact() {
135        //System.out.println("dfac  = " + dfac.toScript());
136
137        do {
138            a = dfac.random(kl, ll + 1, el, q);
139        } while (a.isZERO());
140        //a = dfac.parse(" 3 x^5 + 44 ");
141        //System.out.println("a = " + a);
142
143        do {
144            b = dfac.random(kl, ll + 1, el, q);
145        } while (b.isZERO());
146        //a = a.sum(b);
147        //b = dfac.parse(" 2 x^2 + 40 ");
148        //System.out.println("b = " + b);
149
150        // non commutative
151        c = b.multiply(a);
152        d = a.multiply(b);
153        //System.out.println("c = " + c);
154        //System.out.println("d = " + d);
155        assertTrue("c != 0: ", !c.isZERO());
156        assertTrue("d != 0: ", !d.isZERO());
157
158        assertTrue("a*b != b*a", !c.equals(d) || c.leadingExpVector().equals(d.leadingExpVector()));
159
160        // divide 
161        e = FDUtil.<BigInteger> leftBasePseudoQuotient(c, a);
162        //System.out.println("e = " + e);
163        assertEquals("b == b*a/a: ", b, e);
164
165        f = FDUtil.<BigInteger> rightBasePseudoQuotient(c, b);
166        //System.out.println("f = " + f);
167        assertEquals("a == b*a/b: ", a, f);
168
169        e = FDUtil.<BigInteger> rightBasePseudoQuotient(d, a);
170        //System.out.println("e = " + e);
171        assertEquals("b == a*b/a: ", b, e);
172
173        f = FDUtil.<BigInteger> leftBasePseudoQuotient(d, b);
174        //System.out.println("f = " + f);
175        assertEquals("a == a*b/b: ", a, f);
176    }
177
178
179    /**
180     * Test base pseudo division.
181     */
182    @SuppressWarnings({ "cast" })
183    public void testBasePseudoDivision() {
184        String[] names = new String[] { "x" };
185        dfac = new GenSolvablePolynomialRing<BigInteger>(new BigInteger(1), to, names);
186        GenSolvablePolynomialRing<BigRational> rdfac;
187        rdfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), dfac);
188        //System.out.println("dfac  = " + dfac.toScript());
189
190        do {
191            a = dfac.random(kl, ll * 2, el + 1, q);
192        } while (a.isZERO());
193        //a = dfac.parse(" 3 x^5 + 44 ");
194        //System.out.println("a = " + a);
195
196        do {
197            b = dfac.random(kl, ll * 2, el + 1, q);
198        } while (b.isZERO());
199        //a = a.sum(b);
200        //b = dfac.parse(" 2 x^2 + 40 ");
201        //System.out.println("b = " + b);
202
203        GenPolynomial<BigInteger>[] QR = PolyUtil.<BigInteger> basePseudoQuotientRemainder(a, b);
204        c = (GenSolvablePolynomial<BigInteger>) QR[0];
205        d = (GenSolvablePolynomial<BigInteger>) QR[1];
206        //System.out.println("c   = " + c);
207        //System.out.println("d   = " + d);
208
209        boolean t = PolyUtil.<BigInteger> isBasePseudoQuotientRemainder(a, b, c, d);
210        assertTrue("lc^n c = e b + f: " + f, t);
211
212        GenSolvablePolynomial<BigInteger>[] QRs = FDUtil.<BigInteger> leftBasePseudoQuotientRemainder(a, b);
213        e = QRs[0];
214        f = QRs[1];
215        //System.out.println("e   = " + e);
216        //System.out.println("f   = " + f);
217
218        t = PolyUtil.<BigInteger> isBasePseudoQuotientRemainder(a, b, e, f);
219        assertTrue("ore(lc^n) c = e b + f: " + f, t);
220
221        // compare with field coefficients:
222        GenSolvablePolynomial<BigRational> ap, bp, cp, dp, ep, fp, qp, rp, rhs;
223        ap = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> fromIntegerCoefficients(rdfac, a);
224        bp = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> fromIntegerCoefficients(rdfac, b);
225        cp = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> fromIntegerCoefficients(rdfac, c);
226        dp = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> fromIntegerCoefficients(rdfac, d);
227        ep = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> fromIntegerCoefficients(rdfac, e);
228        fp = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> fromIntegerCoefficients(rdfac, f);
229        //System.out.println("ap  = " + ap);
230        //System.out.println("bp  = " + bp);
231        //System.out.println("cp  = " + cp);
232        //System.out.println("dp  = " + dp);
233        //System.out.println("ep  = " + ep);
234        //System.out.println("fp  = " + fp);
235
236        qp = (GenSolvablePolynomial<BigRational>) ap.divide(bp);
237        rp = (GenSolvablePolynomial<BigRational>) ap.remainder(bp);
238        //System.out.println("qp  = " + qp);
239        //System.out.println("rp  = " + rp);
240        GenSolvablePolynomial<BigRational>[] QRr = ap.quotientRemainder(bp);
241        assertEquals("qp == QRr[0]: ", qp, QRr[0]);
242        assertEquals("rp == QRr[1]: ", rp, QRr[1]);
243
244        rhs = (GenSolvablePolynomial<BigRational>) qp.multiply(bp).sum(rp);
245        //System.out.println("qp bp + rp  = " + rhs);
246        assertEquals("ap == qp bp + rp: ", ap, rhs);
247
248        assertEquals("cp == qp: ", qp.monic(), cp.monic());
249        assertEquals("dp == rp: ", rp.monic(), dp.monic());
250        //System.out.println("dp = qp: " + qp.monic().equals(dp.monic()) );
251        assertEquals("ep == qp: ", ep.monic(), cp.monic());
252        assertEquals("fp == rp: ", fp.monic(), dp.monic());
253    }
254
255
256    /**
257     * Test recursive pseudo division.
258     * @see edu.jas.ufd.PolyUfdUtilTest#testRecursivePseudoDivisionSparse
259     */
260    public void testRecursivePseudoDivision() {
261        //String[] cnames = new String[] { "x" };
262        //String[] mnames = new String[] { "t" };
263        String[] names = new String[] { "t", "x", "y", "z" };
264        rdfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, names);
265        RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>();
266        rdfac.addRelations(wl);
267        rsfac = (RecSolvablePolynomialRing<BigRational>) rdfac.recursive(1);
268
269        // q = q;
270        kl = 1;
271        ll = 3;
272
273        arr = rrfac.random(kl, ll, el, q);
274        //arr = rrfac.parse(" ( t + x + y ) z^2 + ( 2 x - 8 ) y^2 - ( 13 t^4 - 13 t^3 + t^2 + 2 t - 13 ) ");
275        brr = rrfac.random(kl, ll, el, q);
276        if (brr.isZERO()) {
277            brr = rrfac.parse(" ( x - 2 ) z - ( t - y^2 + y ) ");
278        }
279        //System.out.println("FDQR: arr  = " + arr);
280        //System.out.println("FDQR: brr  = " + brr);
281
282        drr = FDUtil.<BigRational> recursivePseudoQuotient(arr, brr);
283        crr = FDUtil.<BigRational> recursiveSparsePseudoRemainder(arr, brr);
284        //System.out.println("FDQR: qr  = " + drr);
285        //System.out.println("FDQR: rr  = " + crr);
286
287        GenSolvablePolynomial<GenPolynomial<BigRational>>[] QR;
288        QR = FDUtil.<BigRational> recursivePseudoQuotientRemainder(arr, brr);
289        assertEquals("drr == QR[0]: ", drr, QR[0]);
290        assertEquals("crr == QR[1]: ", crr, QR[1]);
291
292        boolean t = FDUtil.<BigRational> isRecursivePseudoQuotientRemainder(arr, brr, drr, crr);
293        //System.out.println("FDQR: ore(lc^n) a == q b + r: " + t);
294        assertTrue("ore(lc^n) a = q b + r: " + crr, t); // ?? 
295    }
296
297
298    /**
299     * Test recursive division coefficient polynomial.
300     */
301    public void testLeftAndRightRecursiveDivision() {
302        //String[] names = new String[] { "t", "x", "y", "z" };
303        String[] names = new String[] { "y", "z" };
304        rdfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, names);
305        RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>();
306        rdfac.addRelations(wl);
307        rrfac = rdfac.recursive(1);
308        //System.out.println("\nrdfac  = " + rdfac.toScript());
309        //System.out.println("rrfac  = " + rrfac.toScript());
310        GenSolvablePolynomial<GenPolynomial<BigRational>>[] QR;
311        boolean t;
312
313        // q = q;
314        kl = 2;
315        ll = 4;
316        el = 5;
317
318        arr = rrfac.random(kl, ll, el + 1, q);
319        //arr = rrfac.parse("z^5 - ( 1260/551 y^2 - 143/35 y - 33/100  ) z - ( 1/3 y^2 + 419/299 y - 19/56  )");
320        // b * q + r:
321        //arr = rrfac.parse("z^5 + z^2 - 1");
322        //System.out.println("arr  = " + arr);
323
324        brr = rrfac.random(kl, ll, el, q);
325        //brr = rrfac.parse("z^3 - ( 377/140 y^2 + 211/232 y + 1213967/85560  )");
326        //brr = rrfac.parse("( y ) z^3 - ( 1 ) z + ( 2 )");
327        //System.out.println("brr  = " + brr);
328
329        abrr = arr.multiply(brr);
330        //System.out.println("abrr  = " + abrr);
331
332        // exact left division
333        drr = FDUtil.<BigRational> recursivePseudoQuotient(abrr, brr);
334        crr = FDUtil.<BigRational> recursiveSparsePseudoRemainder(abrr, brr);
335        //System.out.println("drr  = " + drr);
336        //System.out.println("crr  = " + crr);
337
338        QR = FDUtil.<BigRational> recursivePseudoQuotientRemainder(abrr, brr);
339        assertEquals("drr == QR[0]: ", drr, QR[0]);
340        assertEquals("crr == QR[1]: ", crr, QR[1]);
341
342        //t = PolyUtil.<BigRational> isRecursivePseudoQuotientRemainder(arr, brr, drr, crr);
343        t = FDUtil.<BigRational> isRecursivePseudoQuotientRemainder(abrr, brr, drr, crr);
344        //System.out.println("FDQR: ore(lc^n) a == q b + r: " + t);
345        assertTrue("ore(lc^n) a = q b + r: " + crr, t); // ?? 
346
347        barr = brr.multiply(arr);
348        //System.out.println("barr  = " + barr);
349
350        // exact right division
351        QR = FDUtil.<BigRational> recursiveRightPseudoQuotientRemainder(barr, brr);
352        drr = QR[0];
353        crr = QR[1];
354        //System.out.println("drr  = " + drr);
355        //System.out.println("crr  = " + crr);
356        //assertEquals("drr == QR[0]: ", drr, QR[0]);
357        //assertEquals("crr == QR[1]: ", crr, QR[1]);
358
359        t = FDUtil.<BigRational> isRecursiveRightPseudoQuotientRemainder(barr, brr, drr, crr);
360        //System.out.println("FDQR: a ore(lc^n) == q b + r: " + t);
361        assertTrue("a ore(lc^n) = q b + r: " + crr, t); // ?? 
362
363        // left division
364        QR = FDUtil.<BigRational> recursivePseudoQuotientRemainder(arr, brr);
365        drr = QR[0];
366        crr = QR[1];
367        t = FDUtil.<BigRational> isRecursivePseudoQuotientRemainder(arr, brr, drr, crr);
368        //System.out.println("drr  = " + drr);
369        //System.out.println("crr  = " + crr);
370        assertTrue("ore(lc^n) a = b q + r: " + crr, t); // ?? 
371
372        // right division
373        QR = FDUtil.<BigRational> recursiveRightPseudoQuotientRemainder(arr, brr);
374        drr = QR[0];
375        crr = QR[1];
376        t = FDUtil.<BigRational> isRecursiveRightPseudoQuotientRemainder(arr, brr, drr, crr);
377        //System.out.println("drr  = " + drr);
378        //System.out.println("crr  = " + crr);
379        assertTrue("ore(lc^n) a = q p + r: " + crr, t); // ?? 
380    }
381
382
383    /**
384     * Test recursive right coefficient polynomial.
385     */
386    public void testRightRecursivePolynomial() {
387        //String[] names = new String[] { "t", "x", "y", "z" };
388        String[] names = new String[] { "y", "z" };
389        rdfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, names);
390        RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>();
391        rdfac.addRelations(wl);
392        rrfac = rdfac.recursive(1);
393        //System.out.println("\nrdfac  = " + rdfac.toScript());
394        //System.out.println("rrfac  = " + rrfac.toScript());
395
396        // q = q;
397        kl = 3;
398        ll = 4;
399        el = 5;
400
401        arr = rrfac.random(kl, ll, el, q);
402        //System.out.println("FDQR: arr  = " + arr);
403
404        brr = arr.rightRecursivePolynomial();
405        //System.out.println("FDQR: brr  = " + brr);
406
407        //System.out.println("FDQR: arr == brr: " + arr.equals(brr));
408        //assertFalse("arr != brr: ", arr.equals(brr) && false); // mostly unequal
409
410        boolean t = arr.isRightRecursivePolynomial(brr);
411        assertTrue("arr == eval(brr): ", t);
412
413        GenSolvablePolynomial<BigRational> c = (GenSolvablePolynomial<BigRational>) rrfac
414                        .random(kl, ll, el, q).leadingBaseCoefficient();
415        //System.out.println("FDQR: c  = " + c);
416
417        //drr = FDUtil.<BigRational> multiplyRightRecursivePolynomial(brr,c);
418        drr = brr.multiply(c);
419        //System.out.println("FDQR: drr  = " + drr);
420
421        //no: err = FDUtil.<BigRational> recursiveRightPseudoQuotientRemainder(drr,c)[0];
422        err = FDUtil.<BigRational> recursiveDivideRightEval(drr, c); // this is correct
423        assertEquals("arr == err: " + err, brr, err);
424
425        //no: err = FDUtil.<BigRational> recursiveRightDivide(drr,c);
426        //System.out.println("FDQR: err  = " + err);
427        //assertEquals("brr == err: " + err, brr, err);
428
429
430        drr = brr.multiplyLeft(c);
431        //System.out.println("FDQR: drr  = " + drr);
432
433        err = FDUtil.<BigRational> recursiveLeftDivide(drr, c);
434        //System.out.println("FDQR: err  = " + err);
435        assertEquals("brr == err: " + err, brr, err);
436    }
437
438
439    /*
440     * Test exact division of recursive polynomials.
441     */
442    @SuppressWarnings({ "cast" })
443    public void testRecursiveDivide() {
444        rdfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), dfac);
445        RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>();
446        rdfac.addRelations(wl);
447        //System.out.println("rdfac  = " + rdfac.toScript());
448        rsfac = (RecSolvablePolynomialRing<BigRational>) rdfac.recursive(1);
449        //System.out.println("rsfac  = " + rsfac.toScript());
450
451        assertFalse("isCommutative()", rsfac.isCommutative());
452        assertTrue("isAssociative()", rsfac.isAssociative());
453
454        do {
455            as = rsfac.random(kl, ll, el, q);
456        } while (as.isZERO());
457        //System.out.println("as = " + as);
458
459        do {
460            bs = rsfac.random(kl, ll, el, q);
461        } while (bs.isZERO());
462        //System.out.println("bs = " + bs);
463
464        // non commutative
465        cs = bs.multiply(as);
466        ds = as.multiply(bs);
467        //System.out.println("cs = " + cs);
468        //System.out.println("ds = " + ds);
469        assertTrue("cs != 0: ", !cs.isZERO());
470        assertTrue("ds != 0: ", !ds.isZERO());
471
472        //es = (RecSolvablePolynomial<BigRational>) ds.subtract(cs);
473        assertTrue("as*bs != bs*as", !cs.equals(ds) || cs.leadingExpVector().equals(ds.leadingExpVector()));
474
475        // divide 
476        es = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursivePseudoQuotient(cs, as);
477        //System.out.println("es = " + es);
478        final int max = 4;
479        int i = 0;
480        do {
481            x1 = (RecSolvablePolynomial<BigRational>) bs.multiplyLeft(as.leadingBaseCoefficient().power(i));
482            //System.out.println("lc(a)^"+i+"*b = " + x1);
483            if (es.equals(x1)) {
484                assertEquals("b == b*a/a: ", es, x1);
485                break;
486            }
487            if (es.leadingBaseCoefficient().equals(x1.leadingBaseCoefficient())) {
488                // assertEquals("b == b*a/a: ", e, x1);
489                System.out.println("fail: b == b*a/a: lc(e)==lc(x1)");
490                if (es.abs().equals(bs.abs())) {
491                    System.out.println("success via pseudo: b == b*a/a: ");
492                }
493                break;
494            }
495        } while (i++ < max);
496
497        fs = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightPseudoQuotient(cs, bs);
498        //System.out.println("fs = " + fs);
499        i = 0;
500        do {
501            x1 = (RecSolvablePolynomial<BigRational>) as.multiply(bs.leadingBaseCoefficient().power(i));
502            //System.out.println("a*lc(b)^"+i+" = " + x1);
503            if (fs.equals(x1)) {
504                assertEquals("a == b*a/b: ", fs, x1);
505                break;
506            }
507            if (fs.leadingBaseCoefficient().equals(x1.leadingBaseCoefficient())) {
508                System.out.println("fail: a == b*a/b: lc(f)==lc(x1)");
509                if (fs.abs().equals(as.abs())) {
510                    System.out.println("success via pseudo: a == b*a/b: ");
511                }
512                break;
513            }
514        } while (i++ < max);
515
516        es = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightPseudoQuotient(ds, as);
517        //System.out.println("es = " + es);
518        i = 0;
519        do {
520            x1 = (RecSolvablePolynomial<BigRational>) bs.multiply(as.leadingBaseCoefficient().power(i));
521            //System.out.println("b*lc(a)^"+i+" = " + x1);
522            if (es.equals(x1)) {
523                assertEquals("b == a*b/a: ", es, x1);
524                break;
525            }
526            if (es.leadingBaseCoefficient().equals(x1.leadingBaseCoefficient())) {
527                System.out.println("fail: b == a*b/a: lc(e) == lc(x1)");
528                if (es.abs().equals(bs.abs())) {
529                    //System.out.println("success via pseudo: b == a*b/a: ");
530                }
531                break;
532            }
533        } while (i++ < max);
534
535        fs = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursivePseudoQuotient(ds, bs);
536        //System.out.println("fs = " + fs);
537        i = 0;
538        do {
539            x1 = (RecSolvablePolynomial<BigRational>) as.multiplyLeft(bs.leadingBaseCoefficient().power(i));
540            //System.out.println("lc(b)^"+i+"*a = " + x1);
541            if (fs.equals(x1)) {
542                assertEquals("a == a*b/b: ", fs, x1);
543                break;
544            }
545            if (fs.leadingBaseCoefficient().equals(x1.leadingBaseCoefficient())) {
546                System.out.println("fail: a == a*b/b: lc(f)==lc(x1)");
547                if (fs.abs().equals(as.abs())) {
548                    System.out.println("success via pseudo: a == a*b/b: ");
549                }
550                break;
551            }
552        } while (i++ < max);
553    }
554
555}