Source code

001/*
002 * $Id: PolyUtilTest.java 4015 2012-07-22 12:05:38Z kredel $
003 */
004
005package edu.jas.poly;
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.BigComplex;
016import edu.jas.arith.BigInteger;
017import edu.jas.arith.BigRational;
018import edu.jas.arith.ModInteger;
019import edu.jas.arith.ModIntegerRing;
020import edu.jas.arith.Product;
021import edu.jas.arith.ProductRing;
022
023import edu.jas.kern.ComputerThreads;
024import edu.jas.ufd.PolyUfdUtil;
025import edu.jas.ufd.Quotient;
026import edu.jas.ufd.QuotientRing;
027
028
029/**
030 * PolyUtil tests with JUnit.
031 * @author Heinz Kredel.
032 */
033
034public class PolyUtilTest extends TestCase {
035
036
037    /**
038     * main.
039     */
040    public static void main(String[] args) {
041        junit.textui.TestRunner.run(suite());
042    }
043
044
045    /**
046     * Constructs a <CODE>PolyUtilTest</CODE> object.
047     * @param name String.
048     */
049    public PolyUtilTest(String name) {
050        super(name);
051    }
052
053
054    /**
055     */
056    public static Test suite() {
057        TestSuite suite = new TestSuite(PolyUtilTest.class);
058        return suite;
059    }
060
061
062    //private final static int bitlen = 100;
063
064    TermOrder to = new TermOrder(TermOrder.INVLEX);
065
066
067    GenPolynomialRing<BigInteger> dfac;
068
069
070    GenPolynomialRing<BigInteger> cfac;
071
072
073    GenPolynomialRing<GenPolynomial<BigInteger>> rfac;
074
075
076    BigInteger ai;
077
078
079    BigInteger bi;
080
081
082    BigInteger ci;
083
084
085    BigInteger di;
086
087
088    BigInteger ei;
089
090
091    GenPolynomial<BigInteger> a;
092
093
094    GenPolynomial<BigInteger> b;
095
096
097    GenPolynomial<BigInteger> c;
098
099
100    GenPolynomial<BigInteger> d;
101
102
103    GenPolynomial<BigInteger> e;
104
105
106    GenPolynomial<GenPolynomial<BigInteger>> ar;
107
108
109    GenPolynomial<GenPolynomial<BigInteger>> br;
110
111
112    GenPolynomial<GenPolynomial<BigInteger>> cr;
113
114
115    GenPolynomial<GenPolynomial<BigInteger>> dr;
116
117
118    GenPolynomial<GenPolynomial<BigInteger>> er;
119
120
121    int rl = 5;
122
123
124    int kl = 5;
125
126
127    int ll = 5;
128
129
130    int el = 3;
131
132
133    float q = 0.3f;
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        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl, to);
142        cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl - 1, to);
143        rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to);
144    }
145
146
147    @Override
148    protected void tearDown() {
149        a = b = c = d = e = null;
150        ai = bi = ci = di = ei = null;
151        ar = br = cr = dr = er = null;
152        dfac = null;
153        cfac = null;
154        rfac = null;
155    }
156
157
158    protected static java.math.BigInteger getPrime1() {
159        long prime = 2; //2^60-93; // 2^30-35; //19; knuth (2,390)
160        for (int i = 1; i < 60; i++) {
161            prime *= 2;
162        }
163        prime -= 93;
164        //prime = 37;
165        //System.out.println("p1 = " + prime);
166        return new java.math.BigInteger("" + prime);
167    }
168
169
170    protected static java.math.BigInteger getPrime2() {
171        long prime = 2; //2^60-93; // 2^30-35; //19; knuth (2,390)
172        for (int i = 1; i < 30; i++) {
173            prime *= 2;
174        }
175        prime -= 35;
176        //prime = 19;
177        //System.out.println("p1 = " + prime);
178        return new java.math.BigInteger("" + prime);
179    }
180
181
182    /**
183     * Test recursive <--> distributive conversion.
184     */
185    public void testConversion() {
186        c = dfac.getONE();
187        assertTrue("length( c ) = 1", c.length() == 1);
188        assertTrue("isZERO( c )", !c.isZERO());
189        assertTrue("isONE( c )", c.isONE());
190
191        cr = PolyUtil.recursive(rfac, c);
192        a = PolyUtil.distribute(dfac, cr);
193        assertEquals("c == dist(rec(c))", c, a);
194
195        d = dfac.getZERO();
196        assertTrue("length( d ) = 0", d.length() == 0);
197        assertTrue("isZERO( d )", d.isZERO());
198        assertTrue("isONE( d )", !d.isONE());
199
200        dr = PolyUtil.recursive(rfac, d);
201        b = PolyUtil.distribute(dfac, dr);
202        assertEquals("d == dist(rec(d))", d, b);
203    }
204
205
206    /**
207     * Test recursive <--> distributive ring conversion.
208     */
209    public void testConversionRing() {
210        GenPolynomialRing<GenPolynomial<BigInteger>> rf = dfac.recursive(1);
211        GenPolynomialRing<BigInteger> cf = (GenPolynomialRing<BigInteger>)rf.coFac;
212        assertEquals("rfac#var == rf#var ", rfac.nvar, rf.nvar);
213        assertEquals("rfac.coFac#var == rf.coFac#var ", cfac.nvar, cf.nvar);
214        assertEquals("rfac.coFac.coFac == rf.coFac.coFac ", cfac.coFac, cf.coFac);
215        // variable names not same in this test
216    }
217
218
219    /**
220     * Test random recursive <--> distributive conversion.
221     */
222    public void testRandomConversion() {
223        for (int i = 0; i < 7; i++) {
224            c = dfac.random(kl * (i + 2), ll + 2 * i, el + i, q);
225
226            assertTrue("length( c" + i + " ) <> 0", c.length() >= 0);
227            assertTrue(" not isZERO( c" + i + " )", !c.isZERO());
228            assertTrue(" not isONE( c" + i + " )", !c.isONE());
229
230            cr = PolyUtil.recursive(rfac, c);
231            a = PolyUtil.distribute(dfac, cr);
232            //System.out.println("c   = " + c);
233            //System.out.println("cr  = " + cr);
234            //System.out.println("crd = " + a);
235
236            assertEquals("c == dist(rec(c))", c, a);
237        }
238    }
239
240
241    /**
242     * Test random rational <--> integer conversion.
243     */
244    public void testRationalConversion() {
245        GenPolynomialRing<BigRational> rfac = new GenPolynomialRing<BigRational>(new BigRational(1), rl, to);
246
247        GenPolynomial<BigRational> ar;
248        GenPolynomial<BigRational> br;
249
250        for (int i = 0; i < 3; i++) {
251            c = dfac.random(kl * (i + 9), ll * (i + 3), el + i, q).abs();
252            //c = c.multiply( new BigInteger(99) ); // fails, since not primitive
253            //c = GreatestCommonDivisor.primitivePart(c);
254
255            assertTrue("length( c" + i + " ) <> 0", c.length() >= 0);
256            assertTrue(" not isZERO( c" + i + " )", !c.isZERO());
257            assertTrue(" not isONE( c" + i + " )", !c.isONE());
258
259            ar = PolyUtil.<BigRational> fromIntegerCoefficients(rfac, c);
260            br = ar.monic();
261            a = PolyUtil.integerFromRationalCoefficients(dfac, br);
262            //System.out.println("c   = " + c);
263            //System.out.println("ar  = " + ar);
264            //System.out.println("br  = " + br);
265            //System.out.println("crd = " + a);
266
267            assertEquals("c == integer(rational(c))", c, a);
268        }
269    }
270
271
272    /**
273     * Test random modular <--> integer conversion.
274     */
275    public void testModularConversion() {
276        ModIntegerRing pm = new ModIntegerRing(getPrime1());
277        GenPolynomialRing<ModInteger> mfac = new GenPolynomialRing<ModInteger>(pm, rl, to);
278
279        GenPolynomial<ModInteger> ar;
280
281        for (int i = 0; i < 3; i++) {
282            c = dfac.random(kl * (i + 2), ll * (i + 1), el + i, q).abs();
283            //c = c.multiply( new BigInteger(99) ); // fails, since not primitive
284            //c = GreatestCommonDivisor.primitivePart(c);
285
286            assertTrue("length( c" + i + " ) <> 0", c.length() >= 0);
287            assertTrue(" not isZERO( c" + i + " )", !c.isZERO());
288            assertTrue(" not isONE( c" + i + " )", !c.isONE());
289
290            ar = PolyUtil.<ModInteger> fromIntegerCoefficients(mfac, c);
291            a = PolyUtil.integerFromModularCoefficients(dfac, ar);
292            //System.out.println("c   = " + c);
293            //System.out.println("ar  = " + ar);
294            //System.out.println("crd = " + a);
295
296            assertEquals("c == integer(modular(c))", c, a);
297        }
298    }
299
300
301    /**
302     * Test chinese remainder.
303     */
304    public void testChineseRemainder() {
305        java.math.BigInteger p1 = getPrime1();
306        java.math.BigInteger p2 = getPrime2();
307        java.math.BigInteger p12 = p1.multiply(p2);
308
309        ModIntegerRing pm1 = new ModIntegerRing(p1);
310        GenPolynomialRing<ModInteger> mfac1 = new GenPolynomialRing<ModInteger>(pm1, rl, to);
311
312        ModIntegerRing pm2 = new ModIntegerRing(p2);
313        GenPolynomialRing<ModInteger> mfac2 = new GenPolynomialRing<ModInteger>(pm2, rl, to);
314
315        ModIntegerRing pm12 = new ModIntegerRing(p12);
316        GenPolynomialRing<ModInteger> mfac = new GenPolynomialRing<ModInteger>(pm12, rl, to);
317
318        ModInteger di = pm2.create(p1);
319        di = di.inverse();
320        //System.out.println("di = " + di);
321
322        GenPolynomial<ModInteger> am;
323        GenPolynomial<ModInteger> bm;
324        GenPolynomial<ModInteger> cm;
325
326        ExpVector degv, qdegv;
327
328        for (int i = 0; i < 3; i++) {
329            c = dfac.random((59 + 29) / 2, ll * (i + 1), el + i, q);
330            //c = c.multiply( new BigInteger(99) ); // fails, since not primitive
331            //c = GreatestCommonDivisor.primitivePart(c);
332            degv = c.degreeVector();
333            //System.out.println("degv  = " + degv);
334
335            assertTrue("length( c" + i + " ) <> 0", c.length() >= 0);
336            assertTrue(" not isZERO( c" + i + " )", !c.isZERO());
337            assertTrue(" not isONE( c" + i + " )", !c.isONE());
338
339            am = PolyUtil.<ModInteger> fromIntegerCoefficients(mfac1, c);
340            qdegv = am.degreeVector();
341            //System.out.println("qdegv  = " + qdegv);
342            if (!degv.equals(qdegv)) {
343                continue;
344            }
345            bm = PolyUtil.<ModInteger> fromIntegerCoefficients(mfac2, c);
346            qdegv = bm.degreeVector();
347            //System.out.println("qdegv  = " + qdegv);
348            if (!degv.equals(qdegv)) {
349                continue;
350            }
351
352            cm = PolyUtil.chineseRemainder(mfac, am, di, bm);
353            a = PolyUtil.integerFromModularCoefficients(dfac, cm);
354
355            //System.out.println("c  = " + c);
356            //System.out.println("am = " + am);
357            //System.out.println("bm = " + bm);
358            //System.out.println("cm = " + cm);
359            //System.out.println("a  = " + a);
360
361            assertEquals("cra(c mod p1,c mod p2) = c", c, a);
362        }
363    }
364
365
366    /**
367     * Test complex conversion.
368     */
369    public void testComplexConversion() {
370        BigRational rf = new BigRational(1);
371        GenPolynomialRing<BigRational> rfac = new GenPolynomialRing<BigRational>(rf, rl, to);
372
373        BigComplex cf = new BigComplex(1);
374        GenPolynomialRing<BigComplex> cfac = new GenPolynomialRing<BigComplex>(cf, rl, to);
375
376        BigComplex imag = BigComplex.I;
377
378        GenPolynomial<BigRational> rp;
379        GenPolynomial<BigRational> ip;
380        GenPolynomial<BigComplex> crp;
381        GenPolynomial<BigComplex> cip;
382        GenPolynomial<BigComplex> cp;
383        GenPolynomial<BigComplex> ap;
384
385        for (int i = 0; i < 3; i++) {
386            cp = cfac.random(kl + 2 * i, ll * (i + 1), el + i, q);
387
388            assertTrue("length( c" + i + " ) <> 0", cp.length() >= 0);
389            assertTrue(" not isZERO( c" + i + " )", !cp.isZERO());
390            assertTrue(" not isONE( c" + i + " )", !cp.isONE());
391
392            rp = PolyUtil.realPart(rfac, cp);
393            ip = PolyUtil.imaginaryPart(rfac, cp);
394
395            crp = PolyUtil.complexFromRational(cfac, rp);
396            cip = PolyUtil.complexFromRational(cfac, ip);
397
398            ap = crp.sum(cip.multiply(imag));
399
400            //System.out.println("cp = " + cp);
401            //System.out.println("rp = " + rp);
402            //System.out.println("ip = " + ip);
403            //System.out.println("crp = " + crp);
404            //System.out.println("cip = " + cip);
405            //System.out.println("ap  = " + ap);
406
407            assertEquals("re(c)+i*im(c) = c", cp, ap);
408        }
409    }
410
411
412    /**
413     * Test base pseudo division.
414     */
415    public void testBasePseudoDivision() {
416        String[] names = new String[] { "x" };
417        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1),to,names);
418        GenPolynomialRing<BigRational> rdfac = new GenPolynomialRing<BigRational>(new BigRational(1),dfac);
419        //System.out.println("\ndfac  = " + dfac);
420        //System.out.println("rdfac = " + rdfac);
421
422        a = dfac.random(kl, 2*ll, el+17, q);
423        //a = dfac.parse(" 3 x^5 + 44 ");
424        //b = a;
425        b = dfac.random(kl, 2*ll, el+3, q);
426        //a = a.multiply(b);
427        //a = a.sum(b);
428        //b = dfac.parse(" 2 x^2 + 40 ");
429        //System.out.println("a   = " + a);
430        //System.out.println("b   = " + b);
431
432        GenPolynomial<BigInteger>[] QR = PolyUtil.<BigInteger> basePseudoQuotientRemainder(a, b);
433        c = QR[1];
434        d = QR[0];
435        //System.out.println("q   = " + d);
436        //System.out.println("r   = " + c);
437
438        boolean t = PolyUtil.<BigInteger> isBasePseudoQuotientRemainder(a, b, d, c);
439        assertTrue("lc^n a = q b + r: " + c, t);
440
441        GenPolynomial<BigRational> ap = PolyUtil.<BigRational> fromIntegerCoefficients(rdfac,a);
442        GenPolynomial<BigRational> bp = PolyUtil.<BigRational> fromIntegerCoefficients(rdfac,b);
443        GenPolynomial<BigRational> cp = PolyUtil.<BigRational> fromIntegerCoefficients(rdfac,c);
444        GenPolynomial<BigRational> dp = PolyUtil.<BigRational> fromIntegerCoefficients(rdfac,d);
445        //System.out.println("ap  = " + ap);
446        //System.out.println("bp  = " + bp);
447        //System.out.println("cp  = " + cp);
448        ////System.out.println("dp  = " + dp);
449        //System.out.println("dp  = " + dp.monic());
450
451        GenPolynomial<BigRational> qp = ap.divide(bp);
452        GenPolynomial<BigRational> rp = ap.remainder(bp);
453        //System.out.println("qp  = " + qp);
454        //System.out.println("qp  = " + qp.monic());
455        //System.out.println("rp  = " + rp);
456        GenPolynomial<BigRational> rhs = qp.multiply(bp).sum(rp);
457        //System.out.println("qp bp + rp  = " + rhs);
458
459        assertEquals("ap = qp bp + rp: ", ap, rhs);
460
461        assertEquals("cp = rp: ", rp.monic(), cp.monic() );
462        assertEquals("dp = qp: ", qp.monic(), dp.monic() ); // ??
463        //System.out.println("dp = qp: " + qp.monic().equals(dp.monic()) );
464    }
465
466
467    /**
468     * Test base sparse pseudo division.
469     */
470    public void testBasePseudoDivisionSparse() {
471        String[] names = new String[] { "x" };
472        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1),to,names);
473        GenPolynomialRing<BigRational> rdfac = new GenPolynomialRing<BigRational>(new BigRational(1),dfac);
474        //System.out.println("\ndfac  = " + dfac);
475        //System.out.println("rdfac = " + rdfac);
476
477        a = dfac.random(kl, 2*ll, el+17, q);
478        //a = dfac.parse(" 3 x^5 + 44 ");
479        //b = a;
480        b = dfac.random(kl, 2*ll, el+3, q);
481        //a = a.multiply(b);
482        //a = a.sum(b);
483        //b = dfac.parse(" 2 x^2 + 40 ");
484        //System.out.println("a   = " + a);
485        //System.out.println("b   = " + b);
486
487        d = PolyUtil.<BigInteger> basePseudoDivide(a, b);
488        //System.out.println("q   = " + d);
489        c = PolyUtil.<BigInteger> baseSparsePseudoRemainder(a, b);
490        //System.out.println("r   = " + c);
491
492        boolean t = PolyUtil.<BigInteger> isBasePseudoQuotientRemainder(a, b, d, c);
493        assertTrue("lc^n a = q b + r: " + c, t);
494
495        GenPolynomial<BigRational> ap = PolyUtil.<BigRational> fromIntegerCoefficients(rdfac,a);
496        GenPolynomial<BigRational> bp = PolyUtil.<BigRational> fromIntegerCoefficients(rdfac,b);
497        GenPolynomial<BigRational> cp = PolyUtil.<BigRational> fromIntegerCoefficients(rdfac,c);
498        GenPolynomial<BigRational> dp = PolyUtil.<BigRational> fromIntegerCoefficients(rdfac,d);
499        //System.out.println("ap  = " + ap);
500        //System.out.println("bp  = " + bp);
501        //System.out.println("cp  = " + cp);
502        ////System.out.println("dp  = " + dp);
503        //System.out.println("dp  = " + dp.monic());
504
505        GenPolynomial<BigRational> qp = ap.divide(bp);
506        GenPolynomial<BigRational> rp = ap.remainder(bp);
507        //System.out.println("qp  = " + qp);
508        //System.out.println("qp  = " + qp.monic());
509        //System.out.println("rp  = " + rp);
510        GenPolynomial<BigRational> rhs = qp.multiply(bp).sum(rp);
511        //System.out.println("qp bp + rp  = " + rhs);
512
513        assertEquals("ap = qp bp + rp: ", ap, rhs);
514
515        assertEquals("cp = rp: ", rp.monic(), cp.monic() );
516        assertEquals("dp = qp: ", qp.monic(), dp.monic() ); // ??
517        //System.out.println("dp = qp: " + qp.monic().equals(dp.monic()) );
518    }
519
520
521    /**
522     * Test base dense pseudo division.
523     */
524    public void testBasePseudoDivisionDense() {
525        String[] names = new String[] { "x" };
526        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1),to,names);
527        GenPolynomialRing<BigRational> rdfac = new GenPolynomialRing<BigRational>(new BigRational(1),dfac);
528        //System.out.println("\ndfac  = " + dfac);
529        //System.out.println("rdfac = " + rdfac);
530
531        a = dfac.random(kl, 2*ll, el+17, q);
532        //a = dfac.parse(" 3 x^5 + 44 ");
533        //b = a;
534        b = dfac.random(kl, 2*ll, el+3, q);
535        //a = a.multiply(b);
536        //a = a.sum(b);
537        //b = dfac.parse(" 2 x^2 + 40 ");
538        //System.out.println("a   = " + a);
539        //System.out.println("b   = " + b);
540
541        d = PolyUtil.<BigInteger> baseDensePseudoQuotient(a, b);
542        //System.out.println("q   = " + d);
543        c = PolyUtil.<BigInteger> baseDensePseudoRemainder(a, b);
544        //System.out.println("r   = " + c);
545
546        boolean t = PolyUtil.<BigInteger> isBasePseudoQuotientRemainder(a, b, d, c);
547        assertTrue("lc^n a = q b + r: " + c, t);
548
549        GenPolynomial<BigRational> ap = PolyUtil.<BigRational> fromIntegerCoefficients(rdfac,a);
550        GenPolynomial<BigRational> bp = PolyUtil.<BigRational> fromIntegerCoefficients(rdfac,b);
551        GenPolynomial<BigRational> cp = PolyUtil.<BigRational> fromIntegerCoefficients(rdfac,c);
552        GenPolynomial<BigRational> dp = PolyUtil.<BigRational> fromIntegerCoefficients(rdfac,d);
553        //System.out.println("ap  = " + ap);
554        //System.out.println("bp  = " + bp);
555        //System.out.println("cp  = " + cp);
556        ////System.out.println("dp  = " + dp);
557        //System.out.println("dp  = " + dp.monic());
558
559        GenPolynomial<BigRational> qp = ap.divide(bp);
560        GenPolynomial<BigRational> rp = ap.remainder(bp);
561        //System.out.println("qp  = " + qp);
562        //System.out.println("qp  = " + qp.monic());
563        //System.out.println("rp  = " + rp);
564        GenPolynomial<BigRational> rhs = qp.multiply(bp).sum(rp);
565        //System.out.println("qp bp + rp  = " + rhs);
566
567        assertEquals("ap = qp bp + rp: ", ap, rhs);
568
569        assertEquals("cp = rp: ", rp.monic(), cp.monic() );
570        assertEquals("dp = qp: ", qp.monic(), dp.monic() ); // ??
571        //System.out.println("dp = qp: " + qp.monic().equals(dp.monic()) );
572    }
573
574
575    /**
576     * Test recursive pseudo division.
577     * @see edu.jas.ufd.PolyUfdUtilTest#testRecursivePseudoDivisionSparse
578     */
579    public void testRecursivePseudoDivision() {
580    }
581
582
583    /**
584     * Test evaluate main recursive.
585     */
586    public void testEvalMainRecursive() {
587        ai = (new BigInteger()).random(kl);
588        //System.out.println("ai  = " + ai);
589
590        ar = rfac.getZERO();
591        //System.out.println("ar  = " + ar);
592
593        a = PolyUtil.<BigInteger> evaluateMainRecursive(cfac, ar, ai);
594        //System.out.println("a   = " + a);
595
596        assertTrue("isZERO( a )", a.isZERO());
597
598        ar = rfac.getONE();
599        //System.out.println("ar  = " + ar);
600
601        a = PolyUtil.<BigInteger> evaluateMainRecursive(cfac, ar, ai);
602        //System.out.println("a   = " + a);
603
604        assertTrue("isONE( a )", a.isONE());
605
606
607        //ar = rfac.getONE();
608        ar = rfac.random(kl, ll, el, q);
609        //System.out.println("ar  = " + ar);
610        //br = rfac.getONE();
611        br = rfac.random(kl, ll, el, q);
612        //System.out.println("br  = " + br);
613
614        cr = br.sum(ar);
615        //System.out.println("cr  = " + cr);
616
617        a = PolyUtil.<BigInteger> evaluateMainRecursive(cfac, ar, ai);
618        b = PolyUtil.<BigInteger> evaluateMainRecursive(cfac, br, ai);
619        c = PolyUtil.<BigInteger> evaluateMainRecursive(cfac, cr, ai);
620        //System.out.println("a   = " + a);
621        //System.out.println("b   = " + b);
622        //System.out.println("c   = " + c);
623
624        d = a.sum(b);
625        //System.out.println("d   = " + d);
626
627        assertEquals("eval(a+b) == eval(a) + eval(b)", c, d);
628
629
630        cr = br.multiply(ar);
631        //System.out.println("cr  = " + cr);
632
633        a = PolyUtil.<BigInteger> evaluateMainRecursive(cfac, ar, ai);
634        b = PolyUtil.<BigInteger> evaluateMainRecursive(cfac, br, ai);
635        c = PolyUtil.<BigInteger> evaluateMainRecursive(cfac, cr, ai);
636        //System.out.println("a   = " + a);
637        //System.out.println("b   = " + b);
638        //System.out.println("c   = " + c);
639
640        d = a.multiply(b);
641        //System.out.println("d   = " + d);
642
643        assertEquals("eval(a*b) == eval(a) * eval(b)", c, d);
644    }
645
646
647    /**
648     * Test evaluate main.
649     */
650    public void testEvalMain() {
651        ei = (new BigInteger()).random(kl);
652        //System.out.println("ei  = " + ei);
653
654        cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 1, to);
655        //System.out.println("cfac  = " + cfac);
656
657        a = cfac.getZERO();
658        //System.out.println("a  = " + a);
659
660        ai = PolyUtil.<BigInteger> evaluateMain(ei, a, ei);
661        //System.out.println("ai   = " + ai);
662
663        assertTrue("isZERO( ai )", ai.isZERO());
664
665        a = cfac.getONE();
666        //System.out.println("a  = " + a);
667
668        ai = PolyUtil.<BigInteger> evaluateMain(ei, a, ei);
669        //System.out.println("ai   = " + ai);
670
671        assertTrue("isONE( ai )", ai.isONE());
672
673        //a = cfac.getONE();
674        a = cfac.random(kl, ll, el, q);
675        //System.out.println("a  = " + a);
676        //b = cfac.getONE();
677        b = cfac.random(kl, ll, el, q);
678        //System.out.println("b  = " + b);
679
680        c = b.sum(a);
681        //System.out.println("c  = " + c);
682
683        ai = PolyUtil.<BigInteger> evaluateMain(ei, a, ei);
684        bi = PolyUtil.<BigInteger> evaluateMain(ei, b, ei);
685        ci = PolyUtil.<BigInteger> evaluateMain(ei, c, ei);
686        //System.out.println("ai   = " + ai);
687        //System.out.println("bi   = " + bi);
688        //System.out.println("ci   = " + ci);
689
690        di = bi.sum(ai);
691        //System.out.println("di   = " + di);
692
693        assertEquals("eval(a+b) == eval(a) + eval(b)", ci, di);
694
695        c = b.multiply(a);
696        //System.out.println("c  = " + c);
697
698        ai = PolyUtil.<BigInteger> evaluateMain(ei, a, ei);
699        bi = PolyUtil.<BigInteger> evaluateMain(ei, b, ei);
700        ci = PolyUtil.<BigInteger> evaluateMain(ei, c, ei);
701        //System.out.println("ai   = " + ai);
702        //System.out.println("bi   = " + bi);
703        //System.out.println("ci   = " + ci);
704
705        di = bi.multiply(ai);
706        //System.out.println("di   = " + di);
707
708        assertEquals("eval(a*b) == eval(a) * eval(b)", ci, di);
709    }
710
711
712    /**
713     * Test evaluate first.
714     */
715    public void testEvalFirst() {
716        ei = (new BigInteger()).random(kl);
717        //System.out.println("ei  = " + ei);
718
719        GenPolynomial<BigInteger> ae, be, ce, de;
720
721        GenPolynomialRing<BigInteger> fac;
722        fac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl, to);
723        //System.out.println("fac  = " + fac);
724
725        cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 1, to);
726        //System.out.println("cfac  = " + cfac);
727
728        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl - 1, to);
729        //System.out.println("dfac  = " + dfac);
730
731        a = fac.getZERO();
732        //System.out.println("a  = " + a);
733
734        ae = PolyUtil.<BigInteger> evaluateFirst(cfac, dfac, a, ei);
735        //System.out.println("ae   = " + ae);
736
737        assertTrue("isZERO( ae )", ae.isZERO());
738
739        a = fac.getONE();
740        //System.out.println("a  = " + a);
741
742        ae = PolyUtil.<BigInteger> evaluateFirst(cfac, dfac, a, ei);
743        //System.out.println("ae   = " + ae);
744
745        assertTrue("isONE( ae )", ae.isONE());
746
747        //a = fac.getONE();
748        a = fac.random(kl, ll, el, q);
749        //System.out.println("a  = " + a);
750        //b = fac.getONE();
751        b = fac.random(kl, ll, el, q);
752        //System.out.println("b  = " + b);
753
754        c = b.sum(a);
755        //System.out.println("c  = " + c);
756
757        ae = PolyUtil.<BigInteger> evaluateFirst(cfac, dfac, a, ei);
758        be = PolyUtil.<BigInteger> evaluateFirst(cfac, dfac, b, ei);
759        ce = PolyUtil.<BigInteger> evaluateFirst(cfac, dfac, c, ei);
760        //System.out.println("ae   = " + ae);
761        //System.out.println("be   = " + be);
762        //System.out.println("ce   = " + ce);
763
764        de = be.sum(ae);
765        //System.out.println("de   = " + de);
766
767        assertEquals("eval(a+b) == eval(a) + eval(b)", ce, de);
768
769        c = b.multiply(a);
770        //System.out.println("c  = " + c);
771
772        ae = PolyUtil.<BigInteger> evaluateFirst(cfac, dfac, a, ei);
773        be = PolyUtil.<BigInteger> evaluateFirst(cfac, dfac, b, ei);
774        ce = PolyUtil.<BigInteger> evaluateFirst(cfac, dfac, c, ei);
775        //System.out.println("ae   = " + ae);
776        //System.out.println("be   = " + be);
777        //System.out.println("ce   = " + ce);
778
779        de = be.multiply(ae);
780        //System.out.println("de   = " + de);
781
782        assertEquals("eval(a*b) == eval(a) * eval(b)", ce, de);
783    }
784
785
786    /**
787     * Test evaluate all.
788     */
789    public void testEvalAll() {
790        BigInteger cfac = new BigInteger();
791
792        List<BigInteger> Ev = new ArrayList<BigInteger>();
793        for (int i = 0; i < rl; i++) {
794            ei = cfac.random(kl);
795            Ev.add(ei);
796        }
797        //System.out.println("Ev  = " + Ev);
798
799        BigInteger ae, be, ce, de;
800
801        GenPolynomialRing<BigInteger> fac;
802        fac = new GenPolynomialRing<BigInteger>(cfac, rl, to);
803        //System.out.println("fac  = " + fac);
804
805        a = fac.getZERO();
806        //System.out.println("a  = " + a);
807
808        ae = PolyUtil.<BigInteger> evaluateAll(cfac, dfac, a, Ev);
809        //System.out.println("ae   = " + ae);
810
811        assertTrue("isZERO( ae )", ae.isZERO());
812
813        a = fac.getONE();
814        //System.out.println("a  = " + a);
815
816        ae = PolyUtil.<BigInteger> evaluateAll(cfac, dfac, a, Ev);
817        //System.out.println("ae   = " + ae);
818
819        assertTrue("isONE( ae )", ae.isONE());
820
821        //a = fac.getONE();
822        a = fac.random(kl, ll, el, q);
823        //System.out.println("a  = " + a);
824        //b = fac.getONE();
825        b = fac.random(kl, ll, el, q);
826        //System.out.println("b  = " + b);
827
828        c = b.sum(a);
829        //System.out.println("c  = " + c);
830
831        ae = PolyUtil.<BigInteger> evaluateAll(cfac, dfac, a, Ev);
832        be = PolyUtil.<BigInteger> evaluateAll(cfac, dfac, b, Ev);
833        ce = PolyUtil.<BigInteger> evaluateAll(cfac, dfac, c, Ev);
834        //System.out.println("ae   = " + ae);
835        //System.out.println("be   = " + be);
836        //System.out.println("ce   = " + ce);
837
838        de = be.sum(ae);
839        //System.out.println("de   = " + de);
840
841        assertEquals("eval(a+b) == eval(a) + eval(b)", ce, de);
842
843        c = b.multiply(a);
844        //System.out.println("c  = " + c);
845
846        ce = PolyUtil.<BigInteger> evaluateAll(cfac, dfac, c, Ev);
847        //System.out.println("ae   = " + ae);
848        //System.out.println("be   = " + be);
849        //System.out.println("ce   = " + ce);
850
851        de = be.multiply(ae);
852        //System.out.println("de   = " + de);
853
854        assertEquals("eval(a*b) == eval(a) * eval(b)", ce, de);
855    }
856
857
858    /**
859     * Test interpolate univariate 1 polynomial.
860     */
861    public void testInterpolateUnivariateOne() {
862        ModInteger ai, bi, ci, di, ei, fi, gi, hi;
863        GenPolynomial<ModInteger> a;
864        GenPolynomialRing<ModInteger> cfac;
865        ModIntegerRing fac;
866        GenPolynomial<ModInteger> r;
867        GenPolynomial<ModInteger> Q;
868        GenPolynomial<ModInteger> Qp;
869
870        fac = new ModIntegerRing(19);
871        //System.out.println("fac.modul  = " + fac.getModul());
872        cfac = new GenPolynomialRing<ModInteger>(fac, 1, to);
873        //System.out.println("cfac  = " + cfac);
874
875        a = cfac.getONE();
876        //System.out.println("a  = " + a);
877
878        ei = fac.fromInteger(11);
879        //System.out.println("ei  = " + ei);
880        // a(ei)
881        ai = PolyUtil.<ModInteger> evaluateMain(fac, a, ei);
882        //System.out.println("ai   = " + ai);
883        assertTrue("isONE( ai )", ai.isONE());
884
885        di = fac.fromInteger(13);
886        //System.out.println("di  = " + di);
887        // a(di)
888        bi = PolyUtil.<ModInteger> evaluateMain(fac, a, di);
889        //System.out.println("bi   = " + bi);
890        assertTrue("isONE( bi )", bi.isONE());
891
892        // interpolation result
893        r = cfac.getZERO();
894        //System.out.println("r   = " + r);
895
896        // interpolation polynomials product
897        Q = cfac.getONE();
898        //System.out.println("Q   = " + Q);
899
900        ci = PolyUtil.<ModInteger> evaluateMain(fac, Q, ei);
901        //System.out.println("ci   = " + ci);
902        // Q(ei)^-1
903        fi = ci.inverse();
904        //System.out.println("fi   = " + fi);
905        r = PolyUtil.<ModInteger> interpolate(cfac, r, Q, fi, ai, ei);
906        //System.out.println("r   = " + r);
907
908        // next evaluation polynomial
909        Qp = cfac.univariate(0);
910        Qp = Qp.subtract(cfac.getONE().multiply(ei));
911        //System.out.println("Qp   = " + Qp);
912        Q = Q.multiply(Qp);
913        //System.out.println("Q   = " + Q);
914
915        ci = PolyUtil.<ModInteger> evaluateMain(fac, Q, di);
916        //System.out.println("ci   = " + ci);
917        // Q(di)^-1
918        fi = ci.inverse();
919        //System.out.println("fi   = " + fi);
920        r = PolyUtil.<ModInteger> interpolate(cfac, r, Q, fi, bi, di);
921        //System.out.println("r   = " + r);
922
923        // check evaluation
924        gi = PolyUtil.<ModInteger> evaluateMain(fac, r, ei);
925        //System.out.println("gi   = " + gi);
926        hi = PolyUtil.<ModInteger> evaluateMain(fac, r, di);
927        //System.out.println("hi   = " + hi);
928        assertTrue("gi == 1 ", gi.isONE());
929        assertTrue("hi == 1 ", hi.isONE());
930
931        //            interpolate( a(ei), a(di) )            = a (mod 19)
932        assertEquals("interpolate(a mod (x-ei),a mod (x-di)) = a (mod 19)", a, r);
933    }
934
935
936    /**
937     * Test interpolate univariate deg > 0 polynomial.
938     */
939    public void testInterpolateUnivariate() {
940        ModInteger ai, ci, ei, fi;
941        GenPolynomial<ModInteger> a;
942        GenPolynomialRing<ModInteger> cfac;
943        ModIntegerRing fac;
944        GenPolynomial<ModInteger> r;
945        GenPolynomial<ModInteger> Q;
946        GenPolynomial<ModInteger> Qp;
947
948        //long prime = 19;
949        long prime = getPrime1().longValue();
950        fac = new ModIntegerRing(prime);
951        //System.out.println("fac.modul  = " + fac.getModul());
952        cfac = new GenPolynomialRing<ModInteger>(fac, 1, to);
953        //System.out.println("cfac  = " + cfac);
954        int maxdeg = 19;
955
956        // polynomial to interpolate
957        long deg = 0;
958        do {
959            a = cfac.random(kl, ll, maxdeg, q);
960            if (!a.isZERO()) {
961                deg = a.degree(0);
962            }
963        } while (deg <= 0);
964        //System.out.println("a  = " + a);
965        //System.out.println("deg  = " + deg);
966
967        // interpolation result
968        r = cfac.getZERO();
969        //System.out.println("r   = " + r);
970
971        // interpolation polynomials product
972        Q = cfac.getONE();
973        //System.out.println("Q   = " + Q);
974
975        long i = -1;
976        long qdeg;
977        do {
978            i++;
979            if (i >= prime) {
980                assertTrue("elements of Z_prime exhausted", i < prime);
981            }
982            qdeg = Q.degree(0);
983            ei = fac.fromInteger(i);
984            //System.out.println("ei  = " + ei);
985            // a(ei)
986            ai = PolyUtil.<ModInteger> evaluateMain(fac, a, ei);
987            //System.out.println("ai   = " + ai);
988
989            ci = PolyUtil.<ModInteger> evaluateMain(fac, Q, ei);
990            //System.out.println("ci   = " + ci);
991            // Q(ei)^-1
992            fi = ci.inverse();
993            //System.out.println("fi   = " + fi);
994            r = PolyUtil.<ModInteger> interpolate(cfac, r, Q, fi, ai, ei);
995            //System.out.println("r   = " + r);
996
997            // next evaluation polynomial
998            Qp = cfac.univariate(0);
999            Qp = Qp.subtract(cfac.getONE().multiply(ei));
1000            //System.out.println("Qp   = " + Qp);
1001            Q = Q.multiply(Qp);
1002            //System.out.println("Q   = " + Q);
1003        } while (qdeg < deg);
1004
1005        //System.out.println("a   = " + a);
1006        //System.out.println("r   = " + r);
1007
1008        //            interpolate( a(e1), ..., a(ei) )           = a (mod 19)
1009        assertEquals("interpolate(a mod (x-e1),...,a mod (x-ei)) = a (mod 19)", a, r);
1010    }
1011
1012
1013    /**
1014     * Test interpolate multivariate deg > 0 polynomial.
1015     */
1016    public void testInterpolateMultivariate() {
1017        ModInteger ci, ei, fi;
1018        GenPolynomial<ModInteger> ap, bp;
1019        GenPolynomial<GenPolynomial<ModInteger>> a;
1020        GenPolynomialRing<GenPolynomial<ModInteger>> cfac;
1021        GenPolynomialRing<ModInteger> ufac;
1022        GenPolynomialRing<ModInteger> dfac;
1023        ModIntegerRing fac;
1024        GenPolynomial<GenPolynomial<ModInteger>> r;
1025        GenPolynomial<ModInteger> Q;
1026        GenPolynomial<ModInteger> Qp;
1027
1028        //long prime = 19;
1029        long prime = getPrime1().longValue();
1030        fac = new ModIntegerRing(prime);
1031        //System.out.println("fac.modul  = " + fac.getModul());
1032        ufac = new GenPolynomialRing<ModInteger>(fac, 1, to);
1033        //System.out.println("ufac  = " + ufac);
1034        cfac = new GenPolynomialRing<GenPolynomial<ModInteger>>(ufac, rl, to);
1035        //System.out.println("cfac  = " + cfac);
1036        dfac = new GenPolynomialRing<ModInteger>(fac, rl, to);
1037        //System.out.println("dfac  = " + dfac);
1038        int maxdeg = 19;
1039
1040        // polynomial to interpolate
1041        long deg = 0;
1042        do {
1043            a = cfac.random(kl, ll + 9, maxdeg, q);
1044            if (!a.isZERO()) {
1045                deg = PolyUtil.<ModInteger> coeffMaxDegree(a);
1046            }
1047        } while (deg <= 0);
1048        //System.out.println("a  = " + a);
1049        //System.out.println("deg  = " + deg);
1050        ExpVector degv = a.degreeVector();
1051        //System.out.println("degv  = " + degv);
1052
1053        // interpolation result
1054        r = cfac.getZERO();
1055        //System.out.println("r   = " + r);
1056
1057        // interpolation polynomials product
1058        Q = ufac.getONE();
1059        //System.out.println("Q   = " + Q);
1060
1061        long i = -1;
1062        long qdeg;
1063        ExpVector qdegv;
1064        do {
1065            i++;
1066            if (i >= prime) {
1067                assertTrue("elements of Z_prime exhausted", i < prime);
1068            }
1069            qdeg = Q.degree(0);
1070            ei = fac.fromInteger(i);
1071            //System.out.println("ei  = " + ei);
1072            // a(ei)
1073            ap = PolyUtil.<ModInteger> evaluateFirstRec(ufac, dfac, a, ei);
1074            //System.out.println("ap   = " + ap);
1075            qdegv = ap.degreeVector();
1076            //System.out.println("qdegv = " + qdegv);
1077            if (!degv.equals(qdegv)) {
1078                continue;
1079            }
1080            ci = PolyUtil.<ModInteger> evaluateMain(fac, Q, ei);
1081            //System.out.println("ci   = " + ci);
1082            // Q(ei)^-1
1083            fi = ci.inverse();
1084            //System.out.println("fi   = " + fi);
1085            r = PolyUtil.<ModInteger> interpolate(cfac, r, Q, fi, ap, ei);
1086            //System.out.println("r   = " + r);
1087
1088            // check
1089            bp = PolyUtil.<ModInteger> evaluateFirstRec(ufac, dfac, r, ei);
1090            //System.out.println("bp   = " + bp);
1091            assertEquals("interpolate(a)(ei) == a ", bp, ap);
1092
1093
1094            // next evaluation polynomial
1095            Qp = ufac.univariate(0);
1096            Qp = Qp.subtract(ufac.getONE().multiply(ei));
1097            //System.out.println("Qp   = " + Qp);
1098            Q = Q.multiply(Qp);
1099            //System.out.println("Q   = " + Q);
1100        } while (qdeg <= deg);
1101
1102        //System.out.println("a   = " + a);
1103        //System.out.println("r   = " + r);
1104
1105        //            interpolate( a(e1), ..., a(ei) )           = a (mod 19)
1106        assertEquals("interpolate(a mod (x-e1),...,a mod (x-ei)) = a (mod 19)", a, r);
1107    }
1108
1109
1110    /**
1111     * Test interpolate rational multivariate deg > 0 polynomial.
1112     */
1113    public void testInterpolateRationalMultivariate() {
1114        BigRational ci, ei, fi;
1115        GenPolynomial<BigRational> ap, bp;
1116        GenPolynomial<GenPolynomial<BigRational>> a;
1117        GenPolynomialRing<GenPolynomial<BigRational>> cfac;
1118        GenPolynomialRing<BigRational> ufac;
1119        GenPolynomialRing<BigRational> dfac;
1120        BigRational fac;
1121        GenPolynomial<GenPolynomial<BigRational>> r;
1122        GenPolynomial<BigRational> Q;
1123        GenPolynomial<BigRational> Qp;
1124
1125        fac = new BigRational();
1126        //System.out.println("fac.modul  = " + fac.getModul());
1127        ufac = new GenPolynomialRing<BigRational>(fac, 1, to);
1128        //System.out.println("ufac  = " + ufac);
1129        cfac = new GenPolynomialRing<GenPolynomial<BigRational>>(ufac, rl, to);
1130        //System.out.println("cfac  = " + cfac);
1131        dfac = new GenPolynomialRing<BigRational>(fac, rl, to);
1132        //System.out.println("dfac  = " + dfac);
1133        int maxdeg = 19;
1134
1135        // polynomial to interpolate
1136        long deg = 0;
1137        do {
1138            a = cfac.random(kl, ll + 9, maxdeg, q);
1139            if (!a.isZERO()) {
1140                deg = PolyUtil.<BigRational> coeffMaxDegree(a);
1141            }
1142        } while (deg <= 0);
1143        //System.out.println("a  = " + a);
1144        //System.out.println("deg  = " + deg);
1145        ExpVector degv = a.degreeVector();
1146        //System.out.println("degv  = " + degv);
1147
1148        // interpolation result
1149        r = cfac.getZERO();
1150        //System.out.println("r   = " + r);
1151
1152        // interpolation polynomials product
1153        Q = ufac.getONE();
1154        //System.out.println("Q   = " + Q);
1155
1156        long i = -1;
1157        long qdeg;
1158        ExpVector qdegv;
1159        do {
1160            i++;
1161            qdeg = Q.degree(0);
1162            ei = fac.fromInteger(i);
1163            //System.out.println("ei  = " + ei);
1164            // a(ei)
1165            ap = PolyUtil.<BigRational> evaluateFirstRec(ufac, dfac, a, ei);
1166            //System.out.println("ap   = " + ap);
1167            qdegv = ap.degreeVector();
1168            //System.out.println("qdegv = " + qdegv);
1169            if (!degv.equals(qdegv)) {
1170                continue;
1171            }
1172            ci = PolyUtil.<BigRational> evaluateMain(fac, Q, ei);
1173            //System.out.println("ci   = " + ci);
1174            // Q(ei)^-1
1175            fi = ci.inverse();
1176            //System.out.println("fi   = " + fi);
1177            r = PolyUtil.<BigRational> interpolate(cfac, r, Q, fi, ap, ei);
1178            //System.out.println("r   = " + r);
1179
1180            // check
1181            bp = PolyUtil.<BigRational> evaluateFirstRec(ufac, dfac, r, ei);
1182            //System.out.println("bp   = " + bp);
1183            assertEquals("interpolate(a)(ei) == a ", bp, ap);
1184
1185
1186            // next evaluation polynomial
1187            Qp = ufac.univariate(0);
1188            Qp = Qp.subtract(ufac.getONE().multiply(ei));
1189            //System.out.println("Qp   = " + Qp);
1190            Q = Q.multiply(Qp);
1191            //System.out.println("Q   = " + Q);
1192        } while (qdeg <= deg);
1193
1194        //System.out.println("a   = " + a);
1195        //System.out.println("r   = " + r);
1196
1197        //            interpolate( a(e1), ..., a(ei) )           = a (mod 19)
1198        assertEquals("interpolate(a mod (x-e1),...,a mod (x-ei)) = a (mod 19)", a, r);
1199    }
1200
1201
1202    /**
1203     * Test coefficient map function.
1204     */
1205    public void testMap() {
1206        // integers
1207        BigInteger fi = new BigInteger();
1208        //System.out.println("fi = " + fi);
1209
1210        // rational numbers
1211        BigRational fr = new BigRational();
1212        //System.out.println("fr = " + fr);
1213
1214        // modular integers
1215        ModIntegerRing fm = new ModIntegerRing(17);
1216        //System.out.println("fm = " + fm);
1217
1218        // polynomials over integral numbers
1219        GenPolynomialRing<BigInteger> pfi = new GenPolynomialRing<BigInteger>(fi, rl);
1220        //System.out.println("pfi = " + pfi);
1221
1222        // polynomials over rational numbers
1223        GenPolynomialRing<BigRational> pfr = new GenPolynomialRing<BigRational>(fr, rl);
1224        //System.out.println("pfr = " + pfr);
1225
1226        // polynomials over modular integers
1227        GenPolynomialRing<ModInteger> pfm = new GenPolynomialRing<ModInteger>(fm, rl);
1228        //System.out.println("pfm = " + pfm);
1229
1230
1231        // random polynomial
1232        GenPolynomial<BigInteger> pi = pfi.random(kl, 2 * ll, el, q);
1233        //System.out.println("pi = " + pi);
1234
1235        // random polynomial
1236        GenPolynomial<BigRational> pr = pfr.random(kl, 2 * ll, el, q).monic();
1237        //System.out.println("pr = " + pr);
1238
1239        // random polynomial
1240        GenPolynomial<ModInteger> pm = pfm.random(kl, 2 * ll, el, q);
1241        //System.out.println("pm = " + pm);
1242
1243        // test integer to rational and back
1244        GenPolynomial<BigRational> qr;
1245        GenPolynomial<BigInteger> qi;
1246        qr = PolyUtil.<BigInteger, BigRational> map(pfr, pi, new FromInteger<BigRational>(fr));
1247        qi = PolyUtil.<BigRational, BigInteger> map(pfi, qr, new RatNumer());
1248        //System.out.println("qr = " + qr);
1249        //System.out.println("qi = " + qi);
1250        assertEquals("pi == qi ", pi, qi);
1251
1252        // test rational to integer and back
1253        qi = PolyUtil.integerFromRationalCoefficients(pfi, pr);
1254        qr = PolyUtil.<BigInteger, BigRational> map(pfr, qi, new FromInteger<BigRational>(fr));
1255        qr = qr.monic();
1256        //System.out.println("pr = " + pr);
1257        //System.out.println("qr = " + qr);
1258        //System.out.println("qi = " + qi);
1259        assertEquals("pr == qr ", pr, qr);
1260
1261        // test symmetric modular integer to integer and back
1262        GenPolynomial<ModInteger> qm;
1263        qi = PolyUtil.<ModInteger, BigInteger> map(pfi, pm, new ModSymToInt<ModInteger>());
1264        qm = PolyUtil.<BigInteger, ModInteger> map(pfm, qi, new FromInteger<ModInteger>(fm));
1265        //System.out.println("qi = " + qi);
1266        //System.out.println("qm = " + qm);
1267        assertEquals("pm == qm ", pm, qm);
1268
1269        // test modular integer to integer and back
1270        qi = PolyUtil.<ModInteger, BigInteger> map(pfi, pm, new ModToInt<ModInteger>());
1271        qm = PolyUtil.<BigInteger, ModInteger> map(pfm, qi, new FromInteger<ModInteger>(fm));
1272        //System.out.println("qi = " + qi);
1273        //System.out.println("qm = " + qm);
1274        assertEquals("pm == qm ", pm, qm);
1275
1276        // test symmetric modular integer to integer to rational and back
1277        qi = PolyUtil.<ModInteger, BigInteger> map(pfi, pm, new ModSymToInt<ModInteger>());
1278        qr = PolyUtil.<BigInteger, BigRational> map(pfr, qi, new FromInteger<BigRational>(fr));
1279        qi = PolyUtil.<BigRational, BigInteger> map(pfi, qr, new RatNumer());
1280        qm = PolyUtil.<BigInteger, ModInteger> map(pfm, qi, new FromInteger<ModInteger>(fm));
1281        //System.out.println("qi = " + qi);
1282        //System.out.println("qm = " + qm);
1283        assertEquals("pm == qm ", pm, qm);
1284    }
1285
1286
1287    /**
1288     * Test substitution.
1289     */
1290    public void testSubstitution() {
1291        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 1, to);
1292
1293        // subs = x - 7
1294        GenPolynomial<BigInteger> s = dfac.univariate(0).subtract(dfac.fromInteger(7));
1295        GenPolynomial<BigInteger> s1 = dfac.univariate(0).sum(dfac.fromInteger(7));
1296        //System.out.println("s = " + s);
1297        //System.out.println("s1 = " + s1);
1298
1299        for (int i = 0; i < 5; i++) {
1300            a = dfac.random(kl, ll, el, q);
1301            //System.out.println("a = " + a);
1302            b = PolyUtil.<BigInteger> substituteMain(a, s);
1303            c = PolyUtil.<BigInteger> substituteMain(b, s1);
1304            //System.out.println("b = " + b);
1305            //System.out.println("c = " + c);
1306            //System.out.println("a == c " + a.equals(c));
1307            assertEquals("a == c ", a, c);
1308        }
1309    }
1310
1311
1312    /**
1313     * Test algebraic substitution.
1314     */
1315    public void testAlgebraicSubstitution() {
1316
1317        BigRational cfac = new BigRational(1);
1318        String[] alpha = new String[] { "alpha" };
1319        String[] vars = new String[] { "z" };
1320        GenPolynomialRing<BigRational> pfac = new GenPolynomialRing<BigRational>(cfac, 1, to, alpha);
1321        GenPolynomial<BigRational> agen = pfac.univariate(0, 2);
1322        agen = agen.sum(pfac.getONE()); // x^2 + 1
1323        AlgebraicNumberRing<BigRational> afac = new AlgebraicNumberRing<BigRational>(agen, true);
1324        GenPolynomialRing<AlgebraicNumber<BigRational>> apfac 
1325           = new GenPolynomialRing<AlgebraicNumber<BigRational>>(afac, 1, to, vars); // univariate
1326
1327        //System.out.println("agen  = " + agen);
1328        //System.out.println("afac  = " + afac);
1329        //System.out.println("apfac = " + apfac);
1330
1331        // subs = x - 7
1332        GenPolynomial<AlgebraicNumber<BigRational>> s 
1333           = apfac.univariate(0).subtract(apfac.fromInteger(7).multiply(afac.getGenerator()));
1334        GenPolynomial<AlgebraicNumber<BigRational>> s1 
1335           = apfac.univariate(0).sum(apfac.fromInteger(7).multiply(afac.getGenerator()));
1336        //System.out.println("s = " + s);
1337        //System.out.println("s1 = " + s1);
1338
1339        GenPolynomial<AlgebraicNumber<BigRational>> a, b, c;
1340        for (int i = 0; i < 5; i++) {
1341            a = apfac.random(kl, ll, el, q);
1342            //System.out.println("a = " + a);
1343            b = PolyUtil.<AlgebraicNumber<BigRational>> substituteMain(a, s);
1344            c = PolyUtil.<AlgebraicNumber<BigRational>> substituteMain(b, s1);
1345            //System.out.println("b = " + b);
1346            //System.out.println("c = " + c);
1347            //System.out.println("a == c " + a.equals(c));
1348            assertEquals("a == c ", a, c);
1349        }
1350    }
1351
1352
1353    /**
1354     * Test switch variables.
1355     */
1356    public void testSwitchVariables() {
1357
1358        BigRational cfac = new BigRational(1);
1359        GenPolynomialRing<BigRational> pfac = new GenPolynomialRing<BigRational>(cfac, rl, to);
1360        GenPolynomialRing<GenPolynomial<BigRational>> rfac 
1361           = new GenPolynomialRing<GenPolynomial<BigRational>>(pfac, rl, to);
1362
1363        //System.out.println("pfac  = " + pfac);
1364        //System.out.println("rfac  = " + rfac);
1365
1366        GenPolynomial<GenPolynomial<BigRational>> a, c;
1367        GenPolynomial<GenPolynomial<BigRational>> b;
1368        for (int i = 0; i < 5; i++) {
1369            a = rfac.random(kl, ll, el, q);
1370            //System.out.println("a = " + a);
1371            b = PolyUtil.<BigRational> switchVariables(a);
1372            c = PolyUtil.<BigRational> switchVariables(b);
1373            //System.out.println("b = " + b);
1374            //System.out.println("c = " + c);
1375            //System.out.println("a == c " + a.equals(c));
1376            assertEquals("a == c ", a, c);
1377        }
1378    }
1379
1380
1381    /**
1382     * Test algebraic conversions.
1383     */
1384    public void testAlgebraicConversions() {
1385
1386        BigRational cfac = new BigRational(1);
1387        String[] alpha = new String[] { "alpha" };
1388        //String[] vars = new String[] { "z" };
1389        GenPolynomialRing<BigRational> pfac = new GenPolynomialRing<BigRational>(cfac, 1, to, alpha);
1390        GenPolynomial<BigRational> agen = pfac.univariate(0, 2);
1391        agen = agen.sum(pfac.getONE()); // x^2 + 1
1392        AlgebraicNumberRing<BigRational> afac = new AlgebraicNumberRing<BigRational>(agen, true);
1393        GenPolynomialRing<AlgebraicNumber<BigRational>> apfac 
1394           = new GenPolynomialRing<AlgebraicNumber<BigRational>>(afac, rl, to);
1395        GenPolynomialRing<GenPolynomial<BigRational>> rfac 
1396           = new GenPolynomialRing<GenPolynomial<BigRational>>(pfac, rl, to);
1397
1398        //System.out.println("agen  = " + agen);
1399        //System.out.println("afac  = " + afac);
1400        //System.out.println("apfac = " + apfac);
1401        //System.out.println("pfac  = " + pfac);
1402        //System.out.println("rfac  = " + rfac);
1403
1404        GenPolynomial<AlgebraicNumber<BigRational>> a, c;
1405        GenPolynomial<GenPolynomial<BigRational>> b;
1406        for (int i = 0; i < 5; i++) {
1407            a = apfac.random(kl, ll, el, q);
1408            //System.out.println("a = " + a);
1409            b = PolyUtil.<BigRational> fromAlgebraicCoefficients(rfac, a);
1410            c = PolyUtil.<BigRational> convertRecursiveToAlgebraicCoefficients(apfac, b);
1411            //System.out.println("b = " + b);
1412            //System.out.println("c = " + c);
1413            //System.out.println("a == c " + a.equals(c));
1414            assertEquals("a == c ", a, c);
1415        }
1416    }
1417
1418
1419    /**
1420     * Test Taylor series.
1421     */
1422    public void testTaylorSeries() {
1423        GenPolynomial<BigRational> a;
1424        GenPolynomial<BigRational> b;
1425        GenPolynomial<BigRational> c;
1426        GenPolynomialRing<BigRational> dfac;
1427        BigRational cfac;
1428
1429        cfac = new BigRational(1);
1430        String[] vars = new String[] { "x" };
1431        dfac = new GenPolynomialRing<BigRational>(cfac, 1, to, vars);
1432
1433        a = dfac.random(kl, ll, el, q);
1434        //System.out.println("a = " + a);
1435
1436        BigRational v = cfac.getZERO();
1437        //System.out.println("v = " + v);
1438
1439        b = PolyUtil.<BigRational> seriesOfTaylor(a, v);
1440        //System.out.println("taylor(a,0) = " + b);
1441        assertTrue("taylor(a,0) == a ", a.equals(b));
1442
1443        v = cfac.random(kl);
1444        //System.out.println("v = " + v);
1445
1446        b = PolyUtil.<BigRational> seriesOfTaylor(a, v);
1447        //System.out.println("taylor(a,v) = " + b);
1448
1449        c = PolyUtil.<BigRational> seriesOfTaylor(b, v.negate());
1450        //System.out.println("tailor(taylor(a,v),-v) = " + c);
1451        assertTrue("tailor(taylor(a,v),-v) == a ", a.equals(c));
1452    }
1453
1454
1455    /**
1456     * Test Complex real and imaginary part.
1457     */
1458    public void testComplexParts() {
1459        BigRational rf = new BigRational(1);
1460        GenPolynomialRing<BigRational> rfac = new GenPolynomialRing<BigRational>(rf, rl, to);
1461
1462        ComplexRing<BigRational> cf = new ComplexRing<BigRational>(new BigRational(1));
1463        GenPolynomialRing<Complex<BigRational>> cfac = new GenPolynomialRing<Complex<BigRational>>(cf, rl, to);
1464
1465        Complex<BigRational> imag = cf.getIMAG();
1466
1467        GenPolynomial<BigRational> rp;
1468        GenPolynomial<BigRational> ip;
1469        GenPolynomial<Complex<BigRational>> crp;
1470        GenPolynomial<Complex<BigRational>> cip;
1471        GenPolynomial<Complex<BigRational>> cp;
1472        GenPolynomial<Complex<BigRational>> ap;
1473
1474        for (int i = 0; i < 3; i++) {
1475            cp = cfac.random(kl + 2 * i, ll * (i + 1), el + i, q);
1476
1477            assertTrue("length( c" + i + " ) <> 0", cp.length() >= 0);
1478            assertTrue(" not isZERO( c" + i + " )", !cp.isZERO());
1479            assertTrue(" not isONE( c" + i + " )", !cp.isONE());
1480
1481            rp = PolyUtil.<BigRational> realPartFromComplex(rfac, cp);
1482            ip = PolyUtil.<BigRational> imaginaryPartFromComplex(rfac, cp);
1483
1484            crp = PolyUtil.<BigRational> toComplex(cfac, rp);
1485            cip = PolyUtil.<BigRational> toComplex(cfac, ip);
1486
1487            ap = crp.sum(cip.multiply(imag));
1488
1489            //System.out.println("cp = " + cp);
1490            //System.out.println("rp = " + rp);
1491            //System.out.println("ip = " + ip);
1492            //System.out.println("crp = " + crp);
1493            //System.out.println("cip = " + cip);
1494            //System.out.println("ap  = " + ap);
1495
1496            assertEquals("re(c)+i*im(c) = c", cp, ap);
1497        }
1498    }
1499
1500
1501    /**
1502     * Test product represenation conversion, rational numbers.
1503     */
1504    public void testProductConversionRN() {
1505        GenPolynomialRing<BigRational> ufac;
1506        ufac = new GenPolynomialRing<BigRational>(new BigRational(1), 1);
1507
1508        ProductRing<GenPolynomial<BigRational>> pfac;
1509        pfac = new ProductRing<GenPolynomial<BigRational>>(ufac, rl);
1510
1511        GenPolynomialRing<BigRational> dfac = new GenPolynomialRing<BigRational>(new BigRational(1), rl, to);
1512
1513        GenPolynomial<BigRational> c;
1514        Product<GenPolynomial<BigRational>> cp;
1515
1516        c = dfac.getONE();
1517        //System.out.println("c = " + c);
1518 
1519        cp = PolyUtil.<BigRational> toProduct(pfac, c);
1520        //System.out.println("cp = " + cp);
1521        assertTrue("isONE( cp )", cp.isONE());
1522
1523        c = dfac.random(kl, ll, el, q);
1524        //System.out.println("c = " + c);
1525
1526        cp = PolyUtil.<BigRational> toProduct(pfac, c);
1527        //System.out.println("cp = " + cp);
1528        assertTrue("!isONE( cp )", !cp.isONE());
1529    }
1530
1531
1532    /**
1533     * Test polynomal over product represenation conversion, algebraic numbers.
1534     */
1535    public void testPolyProductConversionAN() {
1536        GenPolynomialRing<BigRational> ufac;
1537        ufac = new GenPolynomialRing<BigRational>(new BigRational(1), 1);
1538
1539        GenPolynomial<BigRational> m;
1540        m = ufac.univariate(0, 2);
1541        m = m.subtract(ufac.univariate(0, 1));
1542        //System.out.println("m = " + m);
1543
1544        AlgebraicNumberRing<BigRational> afac;
1545        afac = new AlgebraicNumberRing<BigRational>(m);
1546        //System.out.println("afac = " + afac);
1547
1548        ProductRing<AlgebraicNumber<BigRational>> pfac;
1549        pfac = new ProductRing<AlgebraicNumber<BigRational>>(afac, rl);
1550
1551        GenPolynomialRing<Product<AlgebraicNumber<BigRational>>> dpfac;
1552        dpfac = new GenPolynomialRing<Product<AlgebraicNumber<BigRational>>>(pfac, 2);
1553
1554        GenPolynomialRing<AlgebraicNumber<BigRational>> dfac;
1555        dfac = new GenPolynomialRing<AlgebraicNumber<BigRational>>(afac, 2, to);
1556
1557
1558        GenPolynomial<AlgebraicNumber<BigRational>> c;
1559        GenPolynomial<Product<AlgebraicNumber<BigRational>>> cp;
1560
1561        c = dfac.getONE();
1562        //System.out.println("c = " + c);
1563
1564        cp = PolyUtil.<AlgebraicNumber<BigRational>> toProductGen(dpfac, c);
1565        //System.out.println("cp = " + cp);
1566        assertTrue("isZERO( cp )", cp.isONE());
1567
1568        c = dfac.random(kl, ll, el, q);
1569        //System.out.println("c = " + c);
1570
1571        cp = PolyUtil.<AlgebraicNumber<BigRational>> toProductGen(dpfac, c);
1572        //System.out.println("cp = " + cp);
1573        assertTrue("!isONE( cp )", !cp.isONE());
1574    }
1575
1576
1577    /**
1578     * Test remove unused upper varaibles.
1579     */
1580    public void testRemoveUnusedUpper() {
1581        //System.out.println("dfac = " + dfac);
1582        a = dfac.univariate(3, 2);
1583        b = a.subtract(dfac.univariate(1, 1));
1584        //System.out.println("a = " + a);
1585        //System.out.println("b = " + b);
1586
1587        c = PolyUtil.<BigInteger> removeUnusedUpperVariables(b);
1588        //System.out.println("c = " + c + ", fac = " + c.ring);
1589        assertTrue("#var == 4: " + c.ring.nvar, c.ring.nvar == 4);
1590
1591        a = dfac.univariate(3, 2);
1592        //System.out.println("a = " + a);
1593
1594        c = PolyUtil.<BigInteger> removeUnusedUpperVariables(a);
1595        //System.out.println("c = " + c + ", fac = " + c.ring);
1596        assertTrue("#var == 2: " + c.ring.nvar, c.ring.nvar == 2);
1597
1598        a = dfac.univariate(1, 2);
1599        //System.out.println("a = " + a);
1600
1601        c = PolyUtil.<BigInteger> removeUnusedUpperVariables(a);
1602        //System.out.println("c = " + c + ", fac = " + c.ring);
1603        assertTrue("#var == 4: " + c.ring.nvar, c.ring.nvar == 4);
1604    }
1605
1606
1607    /**
1608     * Test remove unused lower varaibles.
1609     */
1610    public void testRemoveUnusedLower() {
1611        //System.out.println("dfac = " + dfac);
1612        a = dfac.univariate(3, 2);
1613        b = a.subtract(dfac.univariate(1, 1));
1614        //System.out.println("a = " + a);
1615        //System.out.println("b = " + b);
1616
1617        c = PolyUtil.<BigInteger> removeUnusedLowerVariables(b);
1618        //System.out.println("c = " + c + ", fac = " + c.ring);
1619        assertTrue("#var == 4: " + c.ring.nvar, c.ring.nvar == 4);
1620
1621        a = dfac.univariate(3, 2);
1622        //System.out.println("a = " + a);
1623
1624        c = PolyUtil.<BigInteger> removeUnusedLowerVariables(a);
1625        //System.out.println("c = " + c + ", fac = " + c.ring);
1626        assertTrue("#var == 4: " + c.ring.nvar, c.ring.nvar == 4);
1627
1628        a = dfac.univariate(1, 2);
1629        //System.out.println("a = " + a);
1630
1631        c = PolyUtil.<BigInteger> removeUnusedLowerVariables(a);
1632        //System.out.println("c = " + c + ", fac = " + c.ring);
1633        assertTrue("#var == 2: " + c.ring.nvar, c.ring.nvar == 2);
1634    }
1635
1636
1637    /**
1638     * Test remove unused middle varaibles.
1639     */
1640    public void testRemoveUnusedMiddle() {
1641        //System.out.println("dfac = " + dfac);
1642        a = dfac.univariate(4, 2);
1643        b = a.subtract(dfac.univariate(0, 1));
1644        //System.out.println("a = " + a);
1645        //System.out.println("b = " + b);
1646
1647        c = PolyUtil.<BigInteger> removeUnusedLowerVariables(b);
1648        //System.out.println("c = " + c + ", fac = " + c.ring);
1649        assertTrue("#var == 5: " + c.ring.nvar, c.ring.nvar == 5);
1650        c = PolyUtil.<BigInteger> removeUnusedUpperVariables(c);
1651        //System.out.println("c = " + c + ", fac = " + c.ring);
1652        assertTrue("#var == 5: " + c.ring.nvar, c.ring.nvar == 5);
1653
1654        c = PolyUtil.<BigInteger> removeUnusedMiddleVariables(c);
1655        //System.out.println("c = " + c + ", fac = " + c.ring);
1656        assertTrue("#var == 2: " + c.ring.nvar, c.ring.nvar == 2);
1657
1658        a = dfac.univariate(3, 2);
1659        b = a.subtract(dfac.univariate(1, 1));
1660        //System.out.println("a = " + a);
1661        //System.out.println("b = " + b);
1662
1663        try {
1664             c = PolyUtil.<BigInteger> removeUnusedMiddleVariables(b);
1665             fail("c = " + c + ", fac = " + c.ring);
1666        } catch (RuntimeException e) {
1667            // success
1668        }
1669
1670        c = PolyUtil.<BigInteger> removeUnusedLowerVariables(b);
1671        //System.out.println("c = " + c + ", fac = " + c.ring);
1672        assertTrue("#var == 4: " + c.ring.nvar, c.ring.nvar == 4);
1673        c = PolyUtil.<BigInteger> removeUnusedUpperVariables(c);
1674        //System.out.println("c = " + c + ", fac = " + c.ring);
1675        assertTrue("#var == 3: " + c.ring.nvar, c.ring.nvar == 3);
1676
1677        c = PolyUtil.<BigInteger> removeUnusedMiddleVariables(c);
1678        //System.out.println("c = " + c + ", fac = " + c.ring);
1679        assertTrue("#var == 2: " + c.ring.nvar, c.ring.nvar == 2);
1680    }
1681
1682}