Source code

001/*
002 * $Id: FDUtilTest.java 5338 2015-12-06 13:06:47Z kredel $
003 */
004
005package edu.jas.fd;
006
007
008import java.util.List;
009
010import junit.framework.Test;
011import junit.framework.TestCase;
012import junit.framework.TestSuite;
013
014import org.apache.log4j.BasicConfigurator;
015
016import edu.jas.arith.BigInteger;
017import edu.jas.arith.BigRational;
018import edu.jas.gbufd.QuotSolvablePolynomialRing;
019import edu.jas.gbufd.SolvableQuotient;
020import edu.jas.gbufd.SolvableQuotientRing;
021import edu.jas.poly.GenPolynomial;
022import edu.jas.poly.GenSolvablePolynomial;
023import edu.jas.poly.GenSolvablePolynomialRing;
024import edu.jas.poly.PolyUtil;
025import edu.jas.poly.PolynomialList;
026import edu.jas.poly.RecSolvablePolynomialRing;
027import edu.jas.poly.RelationGenerator;
028import edu.jas.poly.TermOrder;
029import edu.jas.poly.WeylRelationsIterated;
030
031
032/**
033 * FDUtil tests with JUnit.
034 * @author Heinz Kredel.
035 */
036
037public class FDUtilTest extends TestCase {
038
039
040    /**
041     * main.
042     */
043    public static void main(String[] args) {
044        BasicConfigurator.configure();
045        junit.textui.TestRunner.run(suite());
046    }
047
048
049    /**
050     * Constructs a <CODE>FDUtilTest</CODE> object.
051     * @param name String.
052     */
053    public FDUtilTest(String name) {
054        super(name);
055    }
056
057
058    /**
059     */
060    public static Test suite() {
061        TestSuite suite = new TestSuite(FDUtilTest.class);
062        return suite;
063    }
064
065
066    TermOrder to = new TermOrder(TermOrder.INVLEX);
067
068
069    GenSolvablePolynomialRing<BigInteger> dfac;
070
071
072    GenSolvablePolynomialRing<BigRational> rdfac;
073
074
075    //GenSolvablePolynomialRing<BigRational> cfac;
076
077
078    GenSolvablePolynomialRing<GenPolynomial<BigInteger>> rfac;
079
080
081    GenSolvablePolynomialRing<GenPolynomial<BigRational>> rrfac;
082
083
084    RecSolvablePolynomialRing<BigRational> rrfacTemp;
085
086
087    //BigRational ai, bi, ci, di, ei;
088
089
090    GenSolvablePolynomial<BigInteger> a, b, c, d, e, f;
091
092
093    GenSolvablePolynomial<GenPolynomial<BigInteger>> ar, br, cr, dr, er, fr;
094
095
096    GenSolvablePolynomial<GenPolynomial<BigRational>> arr, brr, crr, drr, err, frr;
097
098
099    int rl = 4;
100
101
102    int kl = 2;
103
104
105    int ll = 3;
106
107
108    int el = 3;
109
110
111    float q = 0.35f;
112
113
114    @Override
115    protected void setUp() {
116        a = b = c = d = e = null;
117        //ai = bi = ci = di = ei = null;
118        ar = br = cr = dr = er = null;
119        String[] vars = new String[] { "a", "b", "c", "d" };
120        dfac = new GenSolvablePolynomialRing<BigInteger>(new BigInteger(1), rl, to, vars);
121        RelationGenerator<BigInteger> wl = new WeylRelationsIterated<BigInteger>();
122        dfac.addRelations(wl);
123        rfac = dfac.recursive(1);
124        //cfac = (GenSolvablePolynomialRing<BigInteger>) rfac.coFac;
125    }
126
127
128    @Override
129    protected void tearDown() {
130        a = b = c = d = e = null;
131        //ai = bi = ci = di = ei = null;
132        ar = br = cr = dr = er = null;
133        dfac = null;
134        //cfac = null;
135        rfac = null;
136    }
137
138
139    /**
140     * Test base pseudo division.
141     */
142    public void testBasePseudoDivision() {
143        String[] names = new String[] { "x" };
144        dfac = new GenSolvablePolynomialRing<BigInteger>(new BigInteger(1), to, names);
145        GenSolvablePolynomialRing<BigRational> rdfac;
146        rdfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), dfac);
147        //System.out.println("\ndfac  = " + dfac);
148
149        a = dfac.random(kl, 2 * ll, el + 15, q);
150        //a = dfac.parse(" 3 x^5 + 44 ");
151        //b = a;
152        b = dfac.random(kl, 2 * ll, el + 2, q);
153        //a = a.multiply(b);
154        //a = a.sum(b);
155        if (b.isZERO()) {
156            b = dfac.parse(" 2 x^2 + 40 ");
157        }
158        //System.out.println("a   = " + a);
159        //System.out.println("b   = " + b);
160
161        GenPolynomial<BigInteger>[] QR = PolyUtil.<BigInteger> basePseudoQuotientRemainder(a, b);
162        c = (GenSolvablePolynomial<BigInteger>) QR[0];
163        d = (GenSolvablePolynomial<BigInteger>) QR[1];
164        //System.out.println("q   = " + c);
165        //System.out.println("r   = " + d);
166
167        GenSolvablePolynomial<BigInteger> n = (GenSolvablePolynomial<BigInteger>) c.multiply(b).sum(d);
168        //System.out.println("n   = " + n); // + ", " + n.monic());
169        //System.out.println("a   = " + a); // + ", " + a.monic());
170        assertTrue("nonsense", !n.isZERO());
171
172        boolean t = PolyUtil.<BigInteger> isBasePseudoQuotientRemainder(a, b, c, d);
173        assertTrue("lc^n a = q b + r: " + d, t);
174
175        GenSolvablePolynomial<BigInteger>[] QRs = FDUtil.<BigInteger> leftBasePseudoQuotientRemainder(a, b);
176        e = QRs[0];
177        f = QRs[1];
178        //System.out.println("");
179        //System.out.println("q   = " + e);
180        //System.out.println("r   = " + f);
181
182        GenSolvablePolynomial<BigInteger> m = (GenSolvablePolynomial<BigInteger>) e.multiply(b).sum(f);
183        //System.out.println("n   = " + n); // + ", " + m.monic());
184        //System.out.println("m   = " + m); // + ", " + m.monic());
185        //System.out.println("a   = " + a); // + ", " + a.monic());
186        assertTrue("nonsense", !m.isZERO());
187
188        t = PolyUtil.<BigInteger> isBasePseudoQuotientRemainder(a, b, e, f);
189        assertTrue("ore(lc^n) a = q b + r: " + f, t);
190
191        // compare with field coefficients:
192        GenSolvablePolynomial<BigRational> ap, bp, cp, dp, ep, fp, qp, rp, rhs;
193        ap = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> fromIntegerCoefficients(rdfac, a);
194        bp = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> fromIntegerCoefficients(rdfac, b);
195        cp = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> fromIntegerCoefficients(rdfac, c);
196        dp = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> fromIntegerCoefficients(rdfac, d);
197        ep = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> fromIntegerCoefficients(rdfac, e);
198        fp = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> fromIntegerCoefficients(rdfac, f);
199        //System.out.println("ap  = " + ap);
200        //System.out.println("bp  = " + bp);
201        //System.out.println("cp  = " + cp);
202        //System.out.println("dp  = " + dp);
203        //System.out.println("ep  = " + ep);
204        //System.out.println("fp  = " + fp);
205
206        qp = (GenSolvablePolynomial<BigRational>) ap.divide(bp);
207        rp = (GenSolvablePolynomial<BigRational>) ap.remainder(bp);
208        //System.out.println("qp  = " + qp);
209        //System.out.println("rp  = " + rp);
210        GenSolvablePolynomial<BigRational>[] QRr = ap.quotientRemainder(bp);
211        assertEquals("qp == QRr[0]: ", qp, QRr[0]);
212        assertEquals("rp == QRr[1]: ", rp, QRr[1]);
213
214        rhs = (GenSolvablePolynomial<BigRational>) qp.multiply(bp).sum(rp);
215        //System.out.println("qp bp + rp  = " + rhs);
216        assertEquals("ap == qp bp + rp: ", ap, rhs);
217
218        assertEquals("cp == qp: ", qp.monic(), cp.monic());
219        assertEquals("dp == rp: ", rp.monic(), dp.monic());
220        // System.out.println("dp = qp: " + qp.monic().equals(dp.monic()) );
221        assertEquals("ep == qp: ", ep.monic(), cp.monic());
222        assertEquals("fp == rp: ", fp.monic(), dp.monic());
223    }
224
225
226    /**
227     * Test recursive pseudo division.
228     * @see edu.jas.ufd.PolyUfdUtilTest#testRecursivePseudoDivisionSparse
229     */
230    public void testRecursivePseudoDivision() {
231        //String[] cnames = new String[] { "x" };
232        //String[] mnames = new String[] { "t" };
233        String[] names = new String[] { "t", "x", "y", "z" };
234        rdfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, names);
235        RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>();
236        rdfac.addRelations(wl);
237        rrfacTemp = (RecSolvablePolynomialRing<BigRational>) rdfac.recursive(1);
238        rrfac = rrfacTemp;
239        GenSolvablePolynomialRing<BigRational> rcfac = (GenSolvablePolynomialRing<BigRational>) rrfac.coFac;
240        SolvableQuotientRing<BigRational> qfac = new SolvableQuotientRing<BigRational>(rcfac);
241        //GenSolvablePolynomialRing<SolvableQuotient<BigRational>> rqfac 
242        //   = new GenSolvablePolynomialRing<SolvableQuotient<BigRational>>(qfac,rrfac);
243        QuotSolvablePolynomialRing<BigRational> rqfac = new QuotSolvablePolynomialRing<BigRational>(qfac,
244                        rrfac);
245        List<GenSolvablePolynomial<GenPolynomial<BigRational>>> rl = rrfacTemp.coeffTable.relationList();
246        List<GenPolynomial<GenPolynomial<BigRational>>> rlc = PolynomialList
247                        .<GenPolynomial<BigRational>> castToList(rl);
248        rqfac.polCoeff.coeffTable.addRelations(rlc);
249        //System.out.println("\nrdfac  = " + rdfac.toScript());
250        //System.out.println("rrfac  = " + rrfac.toScript());
251        //System.out.println("rcfac  = " + rcfac.toScript());
252        //System.out.println("qfac   = " + qfac.toScript());
253        //System.out.println("rqfac  = " + rqfac.toScript());
254
255        // q = q;
256        kl = 1;
257        ll = 3;
258
259        arr = rrfac.random(kl, ll, el, q);
260        //arr = rrfac.parse(" ( t + x + y ) z^2 + ( 2 x - 8 ) y^2 - ( 13 t^4 - 13 t^3 + t^2 + 2 t - 13 ) ");
261        brr = rrfac.random(kl, ll, el, q);
262        if (brr.isZERO()) {
263            brr = rrfac.parse(" ( x - 2 ) z - ( t - y^2 + y ) ");
264        }
265        //System.out.println("FDQR: arr  = " + arr);
266        //System.out.println("FDQR: brr  = " + brr);
267
268        drr = FDUtil.<BigRational> recursivePseudoQuotient(arr, brr);
269        crr = FDUtil.<BigRational> recursiveSparsePseudoRemainder(arr, brr);
270        //System.out.println("FDQR: qr  = " + drr);
271        //System.out.println("FDQR: rr  = " + crr);
272
273        GenSolvablePolynomial<GenPolynomial<BigRational>>[] QR;
274        QR = FDUtil.<BigRational> recursivePseudoQuotientRemainder(arr, brr);
275        assertEquals("drr == QR[0]: ", drr, QR[0]);
276        assertEquals("crr == QR[1]: ", crr, QR[1]);
277
278        //boolean t = PolyUtil.<BigRational> isRecursivePseudoQuotientRemainder(arr, brr, drr, crr);
279        boolean t = FDUtil.<BigRational> isRecursivePseudoQuotientRemainder(arr, brr, drr, crr);
280        //System.out.println("FDQR: ore(lc^n) a == q b + r: " + t);
281        assertTrue("ore(lc^n) a = q b + r: " + crr, t); // ?? 
282
283        GenSolvablePolynomial<SolvableQuotient<BigRational>> ap, bp, cp, dp, qp, rp, rhs, apm, bpm, cpm, dpm, qpm, rpm, rhsm;
284        ap = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, arr);
285        bp = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, brr);
286        cp = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, crr);
287        dp = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, drr);
288        apm = ap.monic();
289        bpm = bp.monic();
290        cpm = cp.monic();
291        dpm = dp.monic();
292        //System.out.println("FDQR: ap  = " + ap);
293        //System.out.println("FDQR: apm = " + apm);
294        //System.out.println("FDQR: bp  = " + bp);
295        //System.out.println("FDQR: bpm = " + bpm);
296        //System.out.println("FDQR: cp  = " + cp);
297        //System.out.println("FDQR: cpm = " + cpm);
298        //System.out.println("FDQR: dp  = " + dp);
299        //System.out.println("FDQR: dpm = " + dpm);
300
301        qp = (GenSolvablePolynomial<SolvableQuotient<BigRational>>) ap.divide(bp);
302        rp = (GenSolvablePolynomial<SolvableQuotient<BigRational>>) ap.remainder(bp);
303        qpm = qp.monic();
304        rpm = rp.monic();
305        //System.out.println("FDQR: qp  = " + qp);
306        //System.out.println("FDQR: qpm = " + qpm);
307        //System.out.println("FDQR: rp  = " + rp);
308        //System.out.println("FDQR: rpm = " + rpm);
309        rhs = (GenSolvablePolynomial<SolvableQuotient<BigRational>>) qp.multiply(bp).sum(rp);
310        //for commutative divide: rhs = (GenSolvablePolynomial<SolvableQuotient<BigRational>>) bp.multiply(qp).sum(rp);
311        rhsm = rhs.monic();
312        //System.out.println("FDQR: qp bp + rp  = " + rhs);
313        //System.out.println("FDQR: qp bp + rp  = " + rhsm);
314        //System.out.println("FDQR: rpm  == cpm: " + rpm.equals(cpm) ); // to weak ??
315        //System.out.println("FDQR: qpm  == dpm: " + qpm.equals(dpm) );
316        //System.out.println("FDQR: rhs  == ap : " + rhs.equals(ap) );
317        //System.out.println("FDQR: rhsm == apm: " + rhsm.equals(apm) );
318
319        assertEquals("ap == qp bp + rp: ", ap, rhs);
320        //assertEquals("apm == qp bp + rp,m: ", apm, rhsm);
321        assertEquals("cpm == rpm: ", rpm, cpm);
322        assertEquals("dpm == qpm: ", qpm, dpm); // ??
323
324        assertEquals("nonsense", apm, ap.monic());
325        assertEquals("nonsense", bpm, bp.monic());
326        assertEquals("nonsense", rhsm, rhsm.monic());
327    }
328
329
330    /**
331     * Test recursive division coefficient polynomial.
332     */
333    public void testLeftAndRightRecursiveDivision() {
334        //String[] names = new String[] { "t", "x", "y", "z" };
335        String[] names = new String[] { "y", "z" };
336        rdfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, names);
337        RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>();
338        rdfac.addRelations(wl);
339        rrfac = rdfac.recursive(1);
340        //System.out.println("\nrdfac  = " + rdfac.toScript());
341        //System.out.println("rrfac  = " + rrfac.toScript());
342        GenSolvablePolynomial<GenPolynomial<BigRational>>[] QR;
343        boolean t;
344
345        // q = q;
346        kl = 2;
347        ll = 4;
348        el = 5;
349
350        arr = rrfac.random(kl, ll, el + 1, q);
351        //arr = rrfac.parse("z^5 - ( 1260/551 y^2 - 143/35 y - 33/100  ) z - ( 1/3 y^2 + 419/299 y - 19/56  )");
352        // b * q + r:
353        //arr = rrfac.parse("z^5 + z^2 - 1");
354        //System.out.println("arr  = " + arr);
355
356        brr = rrfac.random(kl, ll, el, q);
357        //brr = rrfac.parse("z^3 - ( 377/140 y^2 + 211/232 y + 1213967/85560  )");
358        //brr = rrfac.parse("( y ) z^3 - ( 1 ) z + ( 2 )");
359        //System.out.println("brr  = " + brr);
360
361        // left division
362        drr = FDUtil.<BigRational> recursivePseudoQuotient(arr, brr);
363        crr = FDUtil.<BigRational> recursiveSparsePseudoRemainder(arr, brr);
364        //System.out.println("qr  = " + drr);
365        //System.out.println("rr  = " + crr);
366
367        QR = FDUtil.<BigRational> recursivePseudoQuotientRemainder(arr, brr);
368        assertEquals("drr == QR[0]: ", drr, QR[0]);
369        assertEquals("crr == QR[1]: ", crr, QR[1]);
370
371        //t = PolyUtil.<BigRational> isRecursivePseudoQuotientRemainder(arr, brr, drr, crr);
372        t = FDUtil.<BigRational> isRecursivePseudoQuotientRemainder(arr, brr, drr, crr);
373        //System.out.println("FDQR: ore(lc^n) a == q b + r: " + t);
374        assertTrue("ore(lc^n) a = q b + r: " + crr, t); // ?? 
375
376        // right division
377        //drr = FDUtil.<BigRational> recursiveRightPseudoQuotient(arr, brr);
378        //crr = FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(arr, brr);
379        QR = FDUtil.<BigRational> recursiveRightPseudoQuotientRemainder(arr, brr);
380        drr = QR[0];
381        crr = QR[1];
382        //System.out.println("qr  = " + drr);
383        //System.out.println("rr  = " + crr);
384        //assertEquals("drr == QR[0]: ", drr, QR[0]);
385        //assertEquals("crr == QR[1]: ", crr, QR[1]);
386
387        t = FDUtil.<BigRational> isRecursiveRightPseudoQuotientRemainder(arr, brr, drr, crr);
388        //System.out.println("FDQR: a ore(lc^n) == b q + r: " + t);
389        assertTrue("a ore(lc^n) = b q + r: " + crr, t); // ?? 
390    }
391
392
393    /**
394     * Test recursive right coefficient polynomial.
395     */
396    public void testRightRecursivePolynomial() {
397        //String[] names = new String[] { "t", "x", "y", "z" };
398        String[] names = new String[] { "y", "z" };
399        rdfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, names);
400        RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>();
401        rdfac.addRelations(wl);
402        rrfac = rdfac.recursive(1);
403        //System.out.println("\nrdfac  = " + rdfac.toScript());
404        //System.out.println("rrfac  = " + rrfac.toScript());
405
406        // q = q;
407        kl = 3;
408        ll = 4;
409        el = 5;
410
411        arr = rrfac.random(kl, ll, el, q);
412        //System.out.println("FDQR: arr  = " + arr);
413
414        brr = arr.rightRecursivePolynomial();
415        //System.out.println("FDQR: brr  = " + brr);
416
417        //System.out.println("FDQR: arr == brr: " + arr.equals(brr));
418        //assertFalse("arr != brr: ", arr.equals(brr) && false); // mostly unequal
419
420        boolean t = arr.isRightRecursivePolynomial(brr);
421        assertTrue("arr == eval(brr): ", t);
422    }
423
424}