Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.poly;
006
007
008import java.util.ArrayList;
009import java.util.Iterator;
010import java.util.List;
011import java.util.Map;
012import java.util.Spliterator;
013
014import edu.jas.arith.BigInteger;
015import edu.jas.arith.BigRational;
016import edu.jas.arith.ModInteger;
017import edu.jas.arith.ModIntegerRing;
018import edu.jas.structure.RingElem;
019import edu.jas.structure.UnaryFunctor;
020import edu.jas.util.ListUtil;
021import edu.jas.util.MapEntry;
022import edu.jas.vector.GenMatrix;
023import edu.jas.vector.GenMatrixRing;
024
025import junit.framework.Test;
026import junit.framework.TestCase;
027import junit.framework.TestSuite;
028
029
030/**
031 * GenPolynomial tests with JUnit.
032 * @author Heinz Kredel
033 */
034
035public class GenPolynomialTest extends TestCase {
036
037
038    /**
039     * main
040     */
041    public static void main(String[] args) {
042        junit.textui.TestRunner.run(suite());
043    }
044
045
046    /**
047     * Constructs a <CODE>GenPolynomialTest</CODE> object.
048     * @param name String.
049     */
050    public GenPolynomialTest(String name) {
051        super(name);
052    }
053
054
055    /**
056     * suite.
057     */
058    public static Test suite() {
059        TestSuite suite = new TestSuite(GenPolynomialTest.class);
060        return suite;
061    }
062
063
064    int rl = 6;
065
066
067    int kl = 5;
068
069
070    int ll = 7;
071
072
073    int el = 4;
074
075
076    float q = 0.5f;
077
078
079    @Override
080    protected void setUp() {
081    }
082
083
084    @Override
085    protected void tearDown() {
086    }
087
088
089    /**
090     * Test constructors and factory.
091     */
092    public void testConstructors() {
093        // rational numbers
094        BigRational rf = new BigRational();
095        // System.out.println("rf = " + rf);
096
097        //BigRational r = rf.fromInteger( 99 );
098        // System.out.println("r = " + r);
099        //r = rf.random( 9 ).sum(r);
100        // System.out.println("r = " + r);
101        //assertFalse("r.isZERO() = ", r.isZERO());
102
103        //RingElem<BigRational> re = new BigRational( 3 );
104        // System.out.println("re = " + re);
105        //rf = (BigRational) re;
106
107        //RingFactory<BigRational> ref = new BigRational( 3 );
108        // System.out.println("re = " + re);
109        //rf = (BigRational) ref;
110
111        // polynomials over rational numbers
112        GenPolynomialRing<BigRational> pf = new GenPolynomialRing<BigRational>(rf, 2);
113        // System.out.println("pf = " + pf);
114
115        GenPolynomial<BigRational> p = pf.getONE();
116        // System.out.println("p = " + p);
117        p = pf.random(9);
118        // System.out.println("p = " + p);
119        p = pf.getZERO();
120        // System.out.println("p = " + p);
121
122        RingElem<GenPolynomial<BigRational>> pe = new GenPolynomial<BigRational>(pf);
123        //System.out.println("pe = " + pe);
124        //System.out.println("p.equals(pe) = " + p.equals(pe) );
125        //System.out.println("p.equals(p) = " + p.equals(p) );
126        assertTrue("p.equals(pe) = ", p.equals(pe));
127        assertTrue("p.equals(p) = ", p.equals(p));
128
129        pe = pe.sum(p); // why not p = p.add(pe) ?
130        //System.out.println("pe = " + pe);
131        assertTrue("pe.isZERO() = ", pe.isZERO());
132        p = pf.random(9);
133        p = p.subtract(p);
134        //System.out.println("p = " + p);
135        //System.out.println("p.isZERO() = " + p.isZERO());
136        assertTrue("p.isZERO() = ", p.isZERO());
137
138        // polynomials over (polynomials over rational numbers)
139        GenPolynomialRing<GenPolynomial<BigRational>> ppf = new GenPolynomialRing<GenPolynomial<BigRational>>(
140                        pf, 3);
141        // System.out.println("ppf = " + ppf);
142
143        GenPolynomial<GenPolynomial<BigRational>> pp = ppf.getONE();
144        // System.out.println("pp = " + pp);
145        pp = ppf.random(2);
146        // System.out.println("pp = " + pp);
147        pp = ppf.getZERO();
148        // System.out.println("pp = " + pp);
149
150        RingElem<GenPolynomial<GenPolynomial<BigRational>>> ppe = new GenPolynomial<GenPolynomial<BigRational>>(
151                        ppf);
152        // System.out.println("ppe = " + ppe);
153        // System.out.println("pp.equals(ppe) = " + pp.equals(ppe) );
154        // System.out.println("pp.equals(pp) = " + pp.equals(pp) );
155        assertTrue("pp.equals(ppe) = ", pp.equals(ppe));
156        assertTrue("pp.equals(pp) = ", pp.equals(pp));
157
158        ppe = ppe.sum(pp); // why not pp = pp.add(ppe) ?
159        //System.out.println("ppe = " + ppe);
160        assertTrue("ppe.isZERO() = ", ppe.isZERO());
161        pp = ppf.random(2);
162        pp = pp.subtract(pp);
163        //System.out.println("pp = " + pp);
164        //System.out.println("pp.isZERO() = " + pp.isZERO());
165        assertTrue("pp.isZERO() = ", pp.isZERO());
166
167        // polynomials over (polynomials over (polynomials over rational numbers))
168        GenPolynomialRing<GenPolynomial<GenPolynomial<BigRational>>> pppf = new GenPolynomialRing<GenPolynomial<GenPolynomial<BigRational>>>(
169                        ppf, 4);
170        // System.out.println("pppf = " + pppf);
171
172        GenPolynomial<GenPolynomial<GenPolynomial<BigRational>>> ppp = pppf.getONE();
173        //System.out.println("ppp = " + ppp);
174        ppp = pppf.random(2);
175        // System.out.println("ppp = " + ppp);
176        ppp = pppf.getZERO();
177        // System.out.println("ppp = " + ppp);
178
179        RingElem<GenPolynomial<GenPolynomial<GenPolynomial<BigRational>>>> pppe = new GenPolynomial<GenPolynomial<GenPolynomial<BigRational>>>(
180                        pppf);
181        // System.out.println("pppe = " + pppe);
182        // System.out.println("ppp.equals(pppe) = " + ppp.equals(pppe) );
183        // System.out.println("ppp.equals(ppp) = " + ppp.equals(ppp) );
184        assertTrue("ppp.equals(pppe) = ", ppp.equals(pppe));
185        assertTrue("ppp.equals(ppp) = ", ppp.equals(ppp));
186
187        pppe = pppe.sum(ppp); // why not ppp = ppp.add(pppe) ?
188        // System.out.println("pppe = " + pppe);
189        assertTrue("pppe.isZERO() = ", pppe.isZERO());
190        ppp = pppf.random(2);
191        ppp = ppp.subtract(ppp);
192        // System.out.println("ppp = " + ppp);
193        // System.out.println("ppp.isZERO() = " + ppp.isZERO());
194        assertTrue("ppp.isZERO() = ", ppp.isZERO());
195
196        // some tests
197        //GenPolynomial<BigRational> pfx = new GenPolynomial<BigRational>();
198        //System.out.println("pfx = " + pfx);
199    }
200
201
202    /**
203     * Test extension and contraction.
204     */
205    public void testExtendContract() {
206        // rational numbers
207        BigRational cf = new BigRational(99);
208        // System.out.println("cf = " + cf);
209
210        // polynomials over rational numbers
211        GenPolynomialRing<BigRational> pf = new GenPolynomialRing<BigRational>(cf, rl);
212        // System.out.println("pf = " + pf);
213
214        GenPolynomial<BigRational> a = pf.random(kl, ll, el, q);
215        //System.out.println("a = " + a);
216
217        int k = rl;
218        GenPolynomialRing<BigRational> pfe = pf.extend(k);
219        GenPolynomialRing<BigRational> pfec = pfe.contract(k);
220        assertEquals("pf == pfec", pf, pfec);
221
222        GenPolynomial<BigRational> ae = a.extend(pfe, 0, 0);
223
224        Map<ExpVector, GenPolynomial<BigRational>> m = ae.contract(pfec);
225        List<GenPolynomial<BigRational>> ml = new ArrayList<GenPolynomial<BigRational>>(m.values());
226        GenPolynomial<BigRational> aec = ml.get(0);
227        assertEquals("a == aec", a, aec);
228        //System.out.println("ae = " + ae);
229        //System.out.println("aec = " + aec);
230    }
231
232
233    /**
234     * Test reversion.
235     */
236    public void testReverse() {
237        // rational numbers
238        BigRational cf = new BigRational(99);
239        // System.out.println("cf = " + cf);
240
241        // polynomials over rational numbers
242        GenPolynomialRing<BigRational> pf = new GenPolynomialRing<BigRational>(cf, rl);
243        //System.out.println("pf = " + pf);
244
245        GenPolynomial<BigRational> a = pf.random(kl, ll, el, q);
246        //System.out.println("a = " + a);
247
248        GenPolynomialRing<BigRational> pfr = pf.reverse();
249        GenPolynomialRing<BigRational> pfrr = pfr.reverse();
250        assertEquals("pf == pfrr", pf, pfrr);
251        //System.out.println("pfr = " + pfr);
252
253        GenPolynomial<BigRational> ar = a.reverse(pfr);
254        GenPolynomial<BigRational> arr = ar.reverse(pfrr);
255        assertEquals("a == arr", a, arr);
256        //System.out.println("ar = " + ar);
257        //System.out.println("arr = " + arr);
258    }
259
260
261    /**
262     * Test accessors.
263     */
264    public void testAccessors() {
265        // rational numbers
266        BigRational rf = new BigRational();
267        // System.out.println("rf = " + rf);
268
269        // polynomials over rational numbers
270        GenPolynomialRing<BigRational> pf = new GenPolynomialRing<BigRational>(rf, rl);
271        // System.out.println("pf = " + pf);
272
273        // test 1
274        GenPolynomial<BigRational> p = pf.getONE();
275        // System.out.println("p = " + p);
276
277        ExpVector e = p.leadingExpVector();
278        BigRational c = p.leadingBaseCoefficient();
279
280        GenPolynomial<BigRational> f = new GenPolynomial<BigRational>(pf, c, e);
281        assertEquals("1 == 1 ", p, f);
282
283        GenPolynomial<BigRational> r = p.reductum();
284        assertTrue("red(1) == 0 ", r.isZERO());
285
286        // test 0
287        p = pf.getZERO();
288        // System.out.println("p = " + p);
289        e = p.leadingExpVector();
290        c = p.leadingBaseCoefficient();
291
292        f = new GenPolynomial<BigRational>(pf, c, e);
293        assertEquals("0 == 0 ", p, f);
294
295        r = p.reductum();
296        assertTrue("red(0) == 0 ", r.isZERO());
297
298        // test random
299        p = pf.random(kl, 2 * ll, el, q);
300        // System.out.println("p = " + p);
301        e = p.leadingExpVector();
302        c = p.leadingBaseCoefficient();
303        r = p.reductum();
304
305        f = new GenPolynomial<BigRational>(pf, c, e);
306        f = r.sum(f);
307        assertEquals("p == lm(f)+red(f) ", p, f);
308
309        // test iteration over random
310        GenPolynomial<BigRational> g;
311        g = p;
312        f = pf.getZERO();
313        while (!g.isZERO()) {
314            e = g.leadingExpVector();
315            c = g.leadingBaseCoefficient();
316            //System.out.println("c e = " + c + " " + e);
317            r = g.reductum();
318            f = f.sum(c, e);
319            g = r;
320        }
321        assertEquals("p == lm(f)+lm(red(f))+... ", p, f);
322    }
323
324
325    /**
326     * Test homogeneous.
327     */
328    public void testHomogeneous() {
329        // rational numbers
330        BigRational rf = new BigRational();
331        // System.out.println("rf = " + rf);
332
333        // polynomials over rational numbers
334        GenPolynomialRing<BigRational> pf = new GenPolynomialRing<BigRational>(rf, 2); //rl);
335        // System.out.println("pf = " + pf);
336
337        // test 1
338        GenPolynomial<BigRational> p = pf.getONE();
339        // System.out.println("p = " + p);
340        assertTrue("1 is homogeneous " + p, p.isHomogeneous());
341
342        // test 0
343        p = pf.getZERO();
344        // System.out.println("p = " + p);
345        assertTrue("0 is homogeneous " + p, p.isHomogeneous());
346
347        // test random
348        p = pf.random(kl, 2 * ll, el, q);
349        //p = pf.random(kl,ll,el,q);
350        //System.out.println("p = " + p);
351        assertFalse("rnd is homogeneous " + p, p.isHomogeneous());
352
353        // make homogeneous
354        GenPolynomialRing<BigRational> pfh = pf.extend(1);
355        //System.out.println("pfh = " + pfh);
356        // remove block order
357        TermOrder to = new TermOrder(TermOrder.IGRLEX);
358        pfh = new GenPolynomialRing<BigRational>(pfh, to);
359        //System.out.println("pfh = " + pfh);
360
361        GenPolynomial<BigRational> ph = p.homogenize(pfh);
362        //System.out.println("ph = " + ph);
363        assertTrue("ph is homogeneous " + ph, ph.isHomogeneous());
364        GenPolynomial<BigRational> ps = ph.deHomogenize(pf);
365        //System.out.println("ps = " + ps);
366        assertEquals("phs == p ", ps, p); // findbugs
367        //System.out.println("p is homogeneous = " + p.isHomogeneous());
368        //System.out.println("ph is homogeneous = " + ph.isHomogeneous());
369
370        GenPolynomial<BigRational> s = pf.random(kl, ll, el, q);
371        //System.out.println("s = " + s);
372        assertFalse("rnd is homogeneous " + s, s.isHomogeneous() && !s.isConstant());
373
374        GenPolynomial<BigRational> sh = s.homogenize(pfh);
375        //System.out.println("sh = " + sh);
376        assertTrue("sh is homogeneous " + sh, sh.isHomogeneous());
377        GenPolynomial<BigRational> ss = sh.deHomogenize(pf);
378        //System.out.println("ss = " + ss);
379        assertEquals("ss = s ", ss, s);
380
381        GenPolynomial<BigRational> th = ph.multiply(sh);
382        //System.out.println("th = " + th);
383        assertTrue("th is homogeneous " + th, th.isHomogeneous());
384
385        GenPolynomial<BigRational> t = p.multiply(s);
386        //System.out.println("t = " + t);
387
388        GenPolynomial<BigRational> ts = th.deHomogenize(pf);
389        //System.out.println("ts = " + ts);
390        assertEquals("ts = t ", ts, t);
391    }
392
393
394    /**
395     * Test weight homogeneous.
396     */
397    public void testWeightHomogeneous() {
398        // rational numbers
399        BigRational rf = new BigRational();
400        // System.out.println("rf = " + rf);
401
402        // weight term order
403        long[] weight = new long[] { 2, 3, 4, 5 };
404        TermOrder to = TermOrderByName.weightOrder(weight);
405        // System.out.println("to = " + to);
406
407        // polynomials over rational numbers
408        GenPolynomialRing<BigRational> pf = new GenPolynomialRing<BigRational>(rf, 4, to);
409        // System.out.println("pf = " + pf.toScript());
410
411        // test 1
412        GenPolynomial<BigRational> p = pf.getONE();
413        // System.out.println("p = " + p);
414        assertTrue("1 is weight homogeneous " + p, p.isWeightHomogeneous());
415
416        // test 0
417        p = pf.getZERO();
418        // System.out.println("p = " + p);
419        assertTrue("0 is weight homogeneous " + p, p.isWeightHomogeneous());
420
421        // test random
422        p = pf.random(kl, 3 * ll, el, q);
423        // System.out.println("p = " + p);
424        assertFalse("rnd is weight homogeneous " + p, p.isWeightHomogeneous());
425
426        GenPolynomial<BigRational> pl = p.leadingWeightPolynomial();
427        // System.out.println("pl = " + pl);
428        assertTrue("lw(rnd) is weight homogeneous " + pl, pl.isWeightHomogeneous());
429
430        GenPolynomial<BigRational> r = pf.random(kl, 3 * ll, el, q);
431        // System.out.println("r = " + r);
432        assertFalse("rnd is weight homogeneous " + r, r.isWeightHomogeneous());
433
434        GenPolynomial<BigRational> rl = r.leadingWeightPolynomial();
435        // System.out.println("rl = " + rl);
436        assertTrue("lw(rnd) is weight homogeneous " + rl, rl.isWeightHomogeneous());
437
438        GenPolynomial<BigRational> t = pl.multiply(rl);
439        // System.out.println("t = " + t);
440        assertTrue("lw(rnd)*lw(rnd) is weight homogeneous " + t, t.isWeightHomogeneous());
441    }
442
443
444    /**
445     * Test univariate.
446     */
447    public void testUnivariate() {
448        BigInteger rf = new BigInteger();
449        // System.out.println("rf = " + rf);
450
451        // polynomials over integral numbers
452        GenPolynomialRing<BigInteger> pf = new GenPolynomialRing<BigInteger>(rf, rl);
453        //System.out.println("pf = " + pf);
454
455        GenPolynomial<BigInteger> a, b, c, d;
456
457        // x**1
458        a = pf.univariate(pf.nvar - 1);
459        //System.out.println("a = " + a);
460        assertTrue("deg(a) = 1: ", a.degree() == 1);
461        assertEquals("xi == xi: ", pf.vars[0], a.toString());
462
463        b = pf.univariate(pf.vars[0]);
464        //System.out.println("b = " + b);
465        assertTrue("deg(b) = 1: ", b.degree() == 1);
466        assertEquals("xi == xi: ", pf.vars[0], b.toString());
467
468        c = pf.univariate(0);
469        //System.out.println("c = " + c);
470        assertTrue("deg(c) = 1: ", c.degree() == 1);
471        assertEquals("xi == xi: ", pf.vars[pf.nvar - 1], c.toString());
472
473        d = pf.univariate(pf.vars[pf.nvar - 1]);
474        //System.out.println("d = " + d);
475        assertTrue("deg(c) = 1: ", c.degree() == 1);
476        assertEquals("xi == xi: ", pf.vars[pf.nvar - 1], d.toString());
477
478        // x**7
479        a = pf.univariate(pf.nvar - 1, 7);
480        //System.out.println("a = " + a);
481        assertTrue("deg(a) = 7: ", a.degree() == 7);
482        assertEquals("xi == xi: ", pf.vars[0] + "^7", a.toString());
483
484        b = pf.univariate(pf.vars[0], 7);
485        //System.out.println("b = " + b);
486        assertTrue("deg(b) = 7: ", b.degree() == 7);
487        assertEquals("xi == xi: ", pf.vars[0] + "^7", b.toString());
488
489        c = pf.univariate(0, 7);
490        //System.out.println("c = " + c);
491        assertTrue("deg(c) = 7: ", c.degree() == 7);
492        assertEquals("xi == xi: ", pf.vars[pf.nvar - 1] + "^7", c.toString());
493
494        d = pf.univariate(pf.vars[pf.nvar - 1], 7);
495        //System.out.println("d = " + d);
496        assertTrue("deg(c) = 7: ", c.degree() == 7);
497        assertEquals("xi == xi: ", pf.vars[pf.nvar - 1] + "^7", d.toString());
498    }
499
500
501    /**
502     * Test iterators.
503     */
504    public void testIterators() {
505        // integers
506        BigInteger rf = new BigInteger();
507        // System.out.println("rf = " + rf);
508
509        // polynomials over integral numbers
510        GenPolynomialRing<BigInteger> pf = new GenPolynomialRing<BigInteger>(rf, rl);
511        // System.out.println("pf = " + pf);
512
513        // random polynomial
514        GenPolynomial<BigInteger> p = pf.random(kl, 2 * ll, el, q);
515        //System.out.println("p = " + p);
516
517        // test monomials
518        Monomial<BigInteger> one = new Monomial<BigInteger>(pf.getONE().leadingMonomial());
519        for (Monomial<BigInteger> m : p) {
520            //System.out.println("m = " + m);
521            assertFalse("m.c == 0 ", m.coefficient().isZERO());
522            assertFalse("m.e < (0) ", m.exponent().signum() < 0);
523            if (!m.exponent().isZERO()) {
524                assertFalse("m != 1: ", m.equals(one));
525            }
526            String s = m.toString() + ",  " + m.toScript();
527            //System.out.println("s = " + s);
528            assertTrue("#s >= 2*rl + 5: ", s.length() >= 2 * rl + 5);
529        }
530
531        // test exponents
532        Iterator<ExpVector> et = p.exponentIterator();
533        while (et.hasNext()) {
534            ExpVector e = et.next();
535            //System.out.println("e = " + e);
536            assertFalse("e < (0) ", e.signum() < 0);
537        }
538
539        // test coefficients
540        Iterator<BigInteger> ct = p.coefficientIterator();
541        while (ct.hasNext()) {
542            BigInteger i = ct.next();
543            //System.out.println("i = " + i);
544            assertFalse("i == 0 ", i.isZERO());
545        }
546    }
547
548
549    /**
550     * Test spliterators.
551     */
552    public void testSpliterators() {
553        // integers
554        BigInteger rf = new BigInteger();
555        BigInteger num = rf.fromInteger(1);
556        // polynomials over integral numbers
557        GenPolynomialRing<BigInteger> pf = new GenPolynomialRing<BigInteger>(rf, rl);
558        //System.out.println("pf = " + pf.toScript());
559        // random polynomial
560        GenPolynomial<BigInteger> p = pf.random(kl, 22 * ll, el, q);
561        //System.out.println("p = " + p.length());
562        List<BigInteger> coeffs = new ArrayList<BigInteger>();
563
564        // create spliterator and run on it
565        PolySpliterator<BigInteger> psplit = new PolySpliterator<BigInteger>(p.val);
566        //System.out.println("ps = " + psplit);
567        //System.out.println("ps = "); printCharacteristic(psplit);
568        //psplit.forEachRemaining( m -> System.out.print(m.c.toScript() + ", "));
569        //System.out.println("\n");
570        psplit.forEachRemaining(m -> coeffs.add(m.c.multiply(num)));
571        assertTrue("#coeffs == size: ", p.val.size() == coeffs.size());
572        coeffs.clear();
573
574        // create spliterator and split it
575        //psplit = new PolySpliterator<BigInteger>(p.val);
576        Spliterator<Monomial<BigInteger>> split = p.spliterator();
577        //System.out.println("ps = " + split);
578        //PolySpliterator<BigInteger> rest = split.trySplit();
579        Spliterator<Monomial<BigInteger>> rest = split.trySplit();
580        //System.out.println("rest = "); printCharacteristic(rest);
581        //System.out.println("ps = "); printCharacteristic(split);
582
583        //System.out.println("rest = " + rest);
584        //rest.forEachRemaining( m -> System.out.print(m.c.toScript() + ", "));
585        rest.forEachRemaining(m -> coeffs.add(m.c.multiply(num)));
586        //System.out.println("\nps = " + split);
587        //split.forEachRemaining( m -> System.out.print(m.c.toScript() + ", "));
588        split.forEachRemaining(m -> coeffs.add(m.c.multiply(num)));
589        assertTrue("#coeffs == size: ", p.val.size() == coeffs.size());
590
591        assertTrue("coeffs == p.coefficients: ", ListUtil.<BigInteger> equals(coeffs, p.val.values()));
592    }
593
594
595    void printCharacteristic(Spliterator sp) {
596        for (int c = 0x0; c < 0x4000; c++) {
597            if (sp.hasCharacteristics(c)) {
598                System.out.println(String.format("char: %3x", c));
599            }
600        }
601    }
602
603
604    /**
605     * Test coefficient map function.
606     */
607    public void testMap() {
608        // integers
609        BigInteger rf = new BigInteger();
610        // System.out.println("rf = " + rf);
611
612        // polynomials over integral numbers
613        GenPolynomialRing<BigInteger> pf = new GenPolynomialRing<BigInteger>(rf, rl);
614        // System.out.println("pf = " + pf);
615
616        // random polynomial
617        GenPolynomial<BigInteger> p = pf.random(kl, 2 * ll, el, q);
618        //System.out.println("p = " + p);
619
620        // test times 1
621        GenPolynomial<BigInteger> q;
622        q = p.map(new Multiply<BigInteger>(rf.getONE()));
623        assertEquals("p == q ", p, q);
624
625        // test times 0
626        q = p.map(new Multiply<BigInteger>(rf.getZERO()));
627        assertTrue("q == 0: " + q, q.isZERO());
628
629        // test times -1
630        q = p.map(new Multiply<BigInteger>(rf.getONE().negate()));
631        assertEquals("p == q ", p.negate(), q);
632    }
633
634
635    /**
636     * Test streams.
637     */
638    public void testStreams() {
639        // modular integers
640        ModIntegerRing rf = new ModIntegerRing(32003);
641        ModInteger num = rf.fromInteger(-1);
642        // polynomials over integral numbers
643        GenPolynomialRing<ModInteger> pf = new GenPolynomialRing<ModInteger>(rf, rl);
644        //System.out.println("pf = " + pf.toScript());
645        // random polynomial
646        GenPolynomial<ModInteger> p = pf.random(kl, 222 * ll, 2 + el, q);
647        //System.out.println("p = " + p.length());
648        GenPolynomial<ModInteger> q;
649
650        // negate coefficients 
651        long tn = System.nanoTime();
652        q = p.negate();
653        tn = System.nanoTime() - tn;
654        //System.out.println("q = " + q.length() + ", neg time = " + tn);
655        assertTrue("time >= 0 ", tn >= 0);
656        //System.out.println("p+q = " + p.sum(q));
657        assertTrue("p+q == 0 ", p.sum(q).isZERO());
658
659        // map multiply to coefficients
660        long tm = System.nanoTime();
661        q = p.map(c -> c.multiply(num));
662        tm = System.nanoTime() - tm;
663        //System.out.println("q = " + q.length() + ", old time = " + tm);
664        assertTrue("time >= 0 ", tm >= 0);
665        //System.out.println("p+q = " + p.sum(q));
666        assertTrue("p+q == 0 ", p.sum(q).isZERO());
667
668        // map multiply to coefficients stream
669        long ts = System.nanoTime();
670        q = p.mapOnStream(me -> new MapEntry<ExpVector, ModInteger>(me.getKey(), me.getValue().multiply(num)),
671                        false);
672        ts = System.nanoTime() - ts;
673        //System.out.println("q = " + q.length() + ", seq time = " + ts);
674        assertTrue("time >= 0 ", ts >= 0);
675        //System.out.println("p+q = " + p.sum(q));
676        assertTrue("p+q == 0 ", p.sum(q).isZERO());
677
678        // map multiply to coefficients parallel stream
679        long tp = System.nanoTime();
680        q = p.mapOnStream(me -> new MapEntry<ExpVector, ModInteger>(me.getKey(), me.getValue().multiply(num)),
681                        true);
682        tp = System.nanoTime() - tp;
683        //System.out.println("q = " + q.length() + ", par time = " + tp);
684        assertTrue("time >= 0 ", tp >= 0);
685        //System.out.println("p+q = " + p.sum(q));
686        assertTrue("p+q == 0 ", p.sum(q).isZERO());
687        System.out.println("map time: neg, old, seq, par, = " + tn + ", " + tm + ", " + ts + ", " + tp);
688
689        //System.out.println("ForkJoinPool: " + ForkJoinPool.commonPool());
690    }
691
692
693    /**
694     * Test bitLength.
695     */
696    public void testBitLength() {
697        // integers
698        BigInteger rf = new BigInteger();
699        // System.out.println("rf = " + rf);
700
701        // polynomials over integral numbers
702        GenPolynomialRing<BigInteger> pf = new GenPolynomialRing<BigInteger>(rf, 5);
703        // System.out.println("pf = " + pf);
704
705        GenPolynomial<BigInteger> a, b, c;
706        a = pf.getZERO();
707        assertEquals("blen(0) = 0", 0, a.bitLength());
708
709        a = pf.getONE();
710        assertEquals("blen(1) = 7", 7, a.bitLength());
711
712        // random polynomials
713        a = pf.random(kl, 2 * ll, el, q);
714        //System.out.println("a = " + a);
715        //System.out.println("blen(a) = " + a.bitLength());
716        assertTrue("blen(random) >= 0", 0 <= a.bitLength());
717
718        b = pf.random(kl, 2 * ll, el, q);
719        //System.out.println("b = " + b);
720        //System.out.println("blen(b) = " + b.bitLength());
721        assertTrue("blen(random) >= 0", 0 <= b.bitLength());
722
723        //c = a.multiply(b);
724        c = a.sum(b);
725        //System.out.println("c = " + c);
726        //System.out.println("blen(a)+blen(b) = " + (a.bitLength()+b.bitLength()));
727        //System.out.println("blen(c) = " + c.bitLength());
728        assertTrue("blen(random) >= 0", 0 <= c.bitLength());
729        assertTrue("blen(random)+blen(random) >= blen(random+random)",
730                        a.bitLength() + b.bitLength() >= c.bitLength());
731    }
732
733
734    /**
735     * Test matrix and vector.
736     */
737    public void testMatrix() {
738        // rational numbers
739        BigRational rf = new BigRational();
740        // System.out.println("rf = " + rf);
741
742        // polynomials over rational numbers
743        String[] vars = new String[] { "lambda" };
744        GenPolynomialRing<BigRational> pf = new GenPolynomialRing<BigRational>(rf, vars);
745        //System.out.println("pf = " + pf.toScript());
746
747        // matrix over rational numbers
748        int r = 11;
749        GenMatrixRing<BigRational> mf = new GenMatrixRing<BigRational>(rf, r, r);
750        //System.out.println("mf = " + mf.toScript());
751
752        GenMatrix<BigRational> A = mf.getONE();
753        //System.out.println("A = " + A);
754        GenPolynomial<BigRational> cf = pf.charPolynomial(A);
755        //System.out.println("cf = " + cf);
756        assertTrue("tcf(charPol(A)) == 1", cf.trailingBaseCoefficient().abs().isONE());
757        //System.out.println("det = " + pf.determinantFromCharPol(cf));
758        assertTrue("det(charPol(A)) == 1", pf.determinantFromCharPol(cf).abs().isONE());
759        //System.out.println("trace = " + pf.traceFromCharPol(cf));
760        assertEquals("trace(charPol(A)) == rl", pf.traceFromCharPol(cf), pf.coFac.fromInteger(r));
761
762        A = mf.getZERO();
763        //System.out.println("A = " + A);
764        cf = pf.charPolynomial(A);
765        //System.out.println("cf = " + cf);
766        assertTrue("charPol(A) == 0", cf.isZERO());
767
768        A = mf.randomUpper(3, 0.6f);
769        //System.out.println("A = " + A);
770        cf = pf.charPolynomial(A); // mostly == 0
771        //System.out.println("cf = " + cf);
772        assertTrue("tcf(charPol(A)) == 0: " + cf, cf.trailingBaseCoefficient().isZERO());
773
774        A = mf.random(3, 0.6f);
775        //System.out.println("A = " + A);
776        cf = pf.charPolynomial(A); // mostly != 0
777        //System.out.println("cf = " + cf);
778        assertFalse("tcf(charPol(A)) == 0: " + cf, cf.trailingBaseCoefficient().isZERO());
779    }
780
781}
782
783
784/**
785 * Internal scalar multiplication functor.
786 */
787class Multiply<C extends RingElem<C>> implements UnaryFunctor<C, C> {
788
789
790    C x;
791
792
793    public Multiply(C x) {
794        this.x = x;
795    }
796
797
798    public C eval(C c) {
799        return c.multiply(x);
800    }
801}