Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.poly;
006
007
008import java.util.HashSet;
009import java.util.List;
010import java.util.Set;
011
012import edu.jas.arith.BigRational;
013import edu.jas.arith.BigInteger;
014import edu.jas.poly.PolyUtil;
015
016import junit.framework.Test;
017import junit.framework.TestCase;
018import junit.framework.TestSuite;
019
020
021/**
022 * BigRational coefficients GenPolynomial tests with JUnit.
023 * @author Heinz Kredel
024 */
025
026public class RatGenPolynomialTest extends TestCase {
027
028
029    /**
030     * main.
031     */
032    public static void main(String[] args) {
033        junit.textui.TestRunner.run(suite());
034    }
035
036
037    /**
038     * Constructs a <CODE>RatGenPolynomialTest</CODE> object.
039     * @param name String.
040     */
041    public RatGenPolynomialTest(String name) {
042        super(name);
043    }
044
045
046    /**
047     */
048    public static Test suite() {
049        TestSuite suite = new TestSuite(RatGenPolynomialTest.class);
050        return suite;
051    }
052
053    GenPolynomialRing<BigRational> fac;
054
055
056    GenPolynomial<BigRational> a, b, c, d, e;
057
058
059    int rl = 7;
060
061
062    int kl = 10;
063
064
065    int ll = 10;
066
067
068    int el = 5;
069
070
071    float q = 0.5f;
072
073    @Override
074    protected void setUp() {
075        a = b = c = d = e = null;
076        String[] vars = new String[] { "a", "b", "c", "d", "e", "f", "g" };
077        fac = new GenPolynomialRing<BigRational>(new BigRational(1), vars);
078    }
079
080
081    @Override
082    protected void tearDown() {
083        a = b = c = d = e = null;
084        fac = null;
085    }
086
087
088    /**
089     * Test generate.
090     */
091    public void testGenerate() {
092        assertEquals("rl == #vars: ", rl, fac.nvar);
093        String s = fac.toScript();
094        //System.out.println("fac.toScript: " + s + ", " + s.length());
095        assertTrue("#s == 50: " + s.length(), s.length() <= 50);
096
097        List<GenPolynomial<BigRational>> gens = fac.generators();
098        assertFalse("#gens != () ", gens.isEmpty());
099        //System.out.println("generators: " + gens);
100
101        // test equals
102        Set<GenPolynomial<BigRational>> set = new HashSet<GenPolynomial<BigRational>>(gens);
103        //System.out.println("gen set: " + set);
104        assertEquals("#gens == #set: ", gens.size(), set.size());
105
106        // test for elements 0, 1
107        a = fac.getZERO();
108        b = fac.getONE();
109        assertFalse("0 not in #set: ", set.contains(a));
110        assertTrue("1 in #set: ", set.contains(b));
111
112        // specific tests
113        assertEquals("#gens == rl+1 ", rl + 1, gens.size());
114        Set<Integer> iset = new HashSet<Integer>(set.size());
115        for (GenPolynomial<BigRational> p : gens) {
116            //System.out.println("p = " + p.toScript() + ", # = " + p.hashCode() + ", red = " + p.reductum());
117            assertTrue("red(p) == 0 ", p.reductum().isZERO());
118            iset.add(p.hashCode());
119        }
120        assertEquals("#gens == #iset: ", gens.size(), iset.size());
121    }
122
123
124    /**
125     * Test constructor and toString.
126     */
127    public void testConstruction() {
128        c = fac.getONE();
129        assertTrue("length( c ) = 1", c.length() == 1);
130        assertTrue("isZERO( c )", !c.isZERO());
131        assertTrue("isONE( c )", c.isONE());
132
133        d = fac.getZERO();
134        assertTrue("length( d ) = 0", d.length() == 0);
135        assertTrue("isZERO( d )", d.isZERO());
136        assertTrue("isONE( d )", !d.isONE());
137    }
138
139
140    /**
141     * Test random polynomial.
142     */
143    public void testRandom() {
144        for (int i = 0; i < 7; i++) {
145            //a = fac.random(ll);
146            a = fac.random(kl * (i + 1), ll + 2 * i, el + i, q);
147            //System.out.println("a = " + a);
148
149            assertTrue("length( a" + i + " ) <> 0", a.length() >= 0);
150            assertTrue(" not isZERO( a" + i + " )", !a.isZERO());
151            assertTrue(" not isONE( a" + i + " )", !a.isONE());
152        }
153    }
154
155
156    /**
157     * Test addition.
158     */
159    public void testAddition() {
160        a = fac.random(ll);
161        b = fac.random(ll);
162
163        c = a.sum(b);
164        d = c.subtract(b);
165        assertEquals("a+b-b = a", a, d);
166
167        c = fac.random(ll);
168
169        ExpVector u = ExpVector.random(rl, el, q);
170        BigRational x = BigRational.RNRAND(kl);
171
172        b = new GenPolynomial<BigRational>(fac, x, u);
173        c = a.sum(b);
174        d = a.sum(x, u);
175        assertEquals("a+p(x,u) = a+(x,u)", c, d);
176
177        c = a.subtract(b);
178        d = a.subtract(x, u);
179        assertEquals("a-p(x,u) = a-(x,u)", c, d);
180
181        a = new GenPolynomial<BigRational>(fac);
182        b = new GenPolynomial<BigRational>(fac, x, u);
183        c = b.sum(a);
184        d = a.sum(x, u);
185        assertEquals("a+p(x,u) = a+(x,u)", c, d);
186
187        c = a.subtract(b);
188        d = a.subtract(x, u);
189        assertEquals("a-p(x,u) = a-(x,u)", c, d);
190    }
191
192
193    /**
194     * Test object multiplication.
195     */
196    public void testMultiplication() {
197        a = fac.random(ll);
198        assertTrue("not isZERO( a )", !a.isZERO());
199
200        b = fac.random(ll);
201        assertTrue("not isZERO( b )", !b.isZERO());
202
203        c = b.multiply(a);
204        d = a.multiply(b);
205        assertTrue("not isZERO( c )", !c.isZERO());
206        assertTrue("not isZERO( d )", !d.isZERO());
207
208        //System.out.println("a = " + a);
209        //System.out.println("b = " + b);
210        e = d.subtract(c);
211        assertTrue("isZERO( a*b-b*a ) " + e, e.isZERO());
212
213        assertTrue("a*b = b*a", c.equals(d));
214        assertEquals("a*b = b*a", c, d);
215
216        c = fac.random(ll);
217        //System.out.println("c = " + c);
218        d = a.multiply(b.multiply(c));
219        e = (a.multiply(b)).multiply(c);
220
221        //System.out.println("d = " + d);
222        //System.out.println("e = " + e);
223
224        //System.out.println("d-e = " + d.subtract(c) );
225
226        assertEquals("a(bc) = (ab)c", d, e);
227        assertTrue("a(bc) = (ab)c", d.equals(e));
228
229        BigRational x = a.leadingBaseCoefficient().inverse();
230        c = a.monic();
231        d = a.multiply(x);
232        assertEquals("a.monic() = a(1/ldcf(a))", c, d);
233
234        BigRational y = b.leadingBaseCoefficient().inverse();
235        c = b.monic();
236        d = b.multiply(y);
237        assertEquals("b.monic() = b(1/ldcf(b))", c, d);
238
239        e = new GenPolynomial<BigRational>(fac, y);
240        d = b.multiply(e);
241        assertEquals("b.monic() = b(1/ldcf(b))", c, d);
242
243        d = e.multiply(b);
244        assertEquals("b.monic() = (1/ldcf(b) (0))*b", c, d);
245    }
246
247
248    /**
249     * Test BLAS level 1.
250     */
251    public void testBLAS1() {
252        a = fac.random(kl, ll, el, q);
253        b = fac.random(kl, ll, el, q);
254        c = fac.random(kl, 3, el * el, q);
255        ExpVector ev = ExpVector.random(rl, el, q);
256        BigRational lc = BigRational.RNRAND(kl);
257
258        d = a.subtractMultiple(lc, b);
259        e = a.subtract(b.multiply(lc));
260        assertEquals("a - (lc) b == a - ((lc) b)", d, e);
261
262        d = a.subtractMultiple(lc, ev, b);
263        e = a.subtract(b.multiply(lc, ev));
264        assertEquals("a - (lc ev) b == a - ((lc ev) b)", d, e);
265
266        ExpVector fv = ExpVector.random(rl, el, q);
267        BigRational tc = BigRational.RNRAND(kl);
268
269        d = a.scaleSubtractMultiple(tc, lc, ev, b);
270        e = a.multiply(tc).subtract(b.multiply(lc, ev));
271        assertEquals("(tc) a - (lc ev) b == ((tc) a - ((lc ev) b))", d, e);
272
273        d = a.scaleSubtractMultiple(tc, fv, lc, ev, b);
274        e = a.multiply(tc, fv).subtract(b.multiply(lc, ev));
275        assertEquals("(tc fv) a - (lc ev) b == ((tc fv) a - ((lc ev) b))", d, e);
276    }
277
278
279    /**
280     * Test distributive law.
281     */
282    public void testDistributive() {
283        a = fac.random(kl, ll, el, q);
284        b = fac.random(kl, ll, el, q);
285        c = fac.random(kl, ll, el, q);
286
287        d = a.multiply(b.sum(c));
288        e = a.multiply(b).sum(a.multiply(c));
289
290        assertEquals("a(b+c) == ab+ac", d, e);
291    }
292
293
294    /**
295     * Test object quotient and remainder.
296     */
297    public void testQuotRem() {
298        fac = new GenPolynomialRing<BigRational>(new BigRational(1), 1);
299
300        a = fac.random(ll).monic();
301        assertTrue("not isZERO( a )", !a.isZERO());
302
303        b = fac.random(ll).monic();
304        assertTrue("not isZERO( b )", !b.isZERO());
305
306        GenPolynomial<BigRational> h = a;
307        GenPolynomial<BigRational> g = fac.random(ll).monic();
308        assertTrue("not isZERO( g )", !g.isZERO());
309        a = a.multiply(g);
310        b = b.multiply(g);
311        //System.out.println("a = " + a);
312        //System.out.println("b = " + b);
313        //System.out.println("g = " + g);
314
315        GenPolynomial<BigRational>[] qr;
316        qr = b.quotientRemainder(a);
317        c = qr[0];
318        d = qr[1];
319        //System.out.println("q = " + c);
320        //System.out.println("r = " + d);
321        e = c.multiply(a).sum(d);
322        assertEquals("b = q a + r", b, e);
323
324        qr = a.quotientRemainder(b);
325        c = qr[0];
326        d = qr[1];
327        //System.out.println("q = " + c);
328        //System.out.println("r = " + d);
329        e = c.multiply(b).sum(d);
330        assertEquals("a = q b + r", a, e);
331
332
333        // gcd tests -------------------------------
334        c = a.gcd(b);
335        //System.out.println("gcd = " + c);
336        assertTrue("a mod gcd(a,b) = 0", a.remainder(c).isZERO());
337        assertTrue("b mod gcd(a,b) = 0", b.remainder(c).isZERO());
338        assertEquals("g = gcd(a,b)", c, g);
339
340
341        GenPolynomial<BigRational>[] gst;
342        gst = a.egcd(b);
343        //System.out.println("egcd = " + gst[0]);
344        //System.out.println(", s = " + gst[1] + ", t = " + gst[2]);
345        c = gst[0];
346        d = gst[1];
347        e = gst[2];
348        assertEquals("g = gcd(a,b)", c, g);
349
350        GenPolynomial<BigRational> x;
351        x = a.multiply(d).sum(b.multiply(e)).monic();
352        //System.out.println("x = " + x);
353        assertEquals("gcd(a,b) = a s + b t", c, x);
354
355
356        gst = a.hegcd(b);
357        //System.out.println("hegcd = " + gst[0]);
358        //System.out.println("s = " + gst[1]);
359        c = gst[0];
360        d = gst[1];
361        assertEquals("g = gcd(a,b)", c, g);
362
363        x = a.multiply(d).remainder(b).monic();
364        //System.out.println("x = " + x);
365        assertEquals("gcd(a,b) = a s mod b", c, x);
366
367        //System.out.println("g = " + g);
368        //System.out.println("h = " + h);
369        c = h.modInverse(g);
370        //System.out.println("c = " + c);
371        x = c.multiply(h).remainder(g).monic();
372        //System.out.println("x = " + x);
373        assertTrue("h invertible mod g", x.isONE());
374    }
375
376
377    /**
378     * Test addition speed.
379     */
380    public void testAdditionSpeed() {
381        int ll = 100;
382        long t = 1000;
383        boolean print = false;
384        int jit = 1;
385        for (int j = 1; j < 5; j++) {
386            for (int i = 1; i < 5; i++) {
387                a = fac.random(kl, i * ll, el, q);
388                b = fac.random(kl, ll, el, q);
389                for (int k = 0; k < jit; k++) {
390                    long t1 = System.nanoTime();
391                    c = a.sum(b);
392                    t1 = System.nanoTime() - t1;
393                    assertTrue("c != 0", !c.isZERO());
394
395                    long t2 = System.nanoTime();
396                    d = b.sum(a);
397                    t2 = System.nanoTime() - t2;
398                    assertTrue("d != 0", !d.isZERO());
399                    if (print) {
400                        System.out.print("#a = " + a.length() + ", #b = " + b.length());
401                        System.out.println(",\t t1 = " + (t1 / t) + ", t2 = " + (t2 / t));
402                    }
403                    //assertTrue("t2 <= t1", ((t1/t) >= (t2/t)) );
404                }
405                if (print)
406                    System.out.println();
407                assertEquals("c == d", c, d);
408            }
409            ll = 3 * ll;
410        }
411    }
412
413
414    /**
415     * Test absolute norm.
416     */
417    public void testAbsNorm() {
418        BigRational r;
419        a = fac.getONE().negate();
420        //System.out.println("a = " + a);
421
422        r = PolyUtil.<BigRational> absNorm(a);
423        //System.out.println("r = " + r);
424        assertTrue("isONE( absNorm(-1) )", r.isONE());
425
426        a = fac.random(kl * 2, ll + 2, el, q);
427        //System.out.println("a = " + a);
428
429        r = PolyUtil.<BigRational> absNorm(a);
430        //System.out.println("r = " + r);
431        assertTrue(" not isZERO( absNorm(a) )", !r.isZERO() || a.isZERO());
432    }
433
434
435    /**
436     * Test max norm.
437     */
438    public void testMaxNorm() {
439        BigRational r, s;
440        a = fac.getZERO();
441        //System.out.println("a = " + a);
442
443        r = a.maxNorm();
444        //System.out.println("r = " + r);
445        assertTrue("isONE( maxNorm(0) )", r.isZERO());
446
447        r = a.sumNorm();
448        //System.out.println("r = " + r);
449        assertTrue("isONE( sumNorm(0) )", r.isZERO());
450
451        a = fac.getONE().negate();
452        //System.out.println("a = " + a);
453
454        r = a.maxNorm();
455        //System.out.println("r = " + r);
456        assertTrue("isONE( maxNorm(-1) )", r.isONE());
457
458        r = a.sumNorm();
459        //System.out.println("r = " + r);
460        assertTrue("isONE( sumNorm(-1) )", r.isONE());
461
462        a = fac.random(kl * 2, ll + 2, el, q);
463        //System.out.println("a = " + a);
464
465        r = a.maxNorm();
466        //System.out.println("r = " + r);
467        assertTrue("not isZERO( maxNorm(a) )", !r.isZERO() || a.isZERO());
468
469        //s = a.multiply(a).maxNorm();
470        //System.out.println("s = " + s + ", r*r = " + r.multiply(r));
471        //assertEquals("s*s == maxNorm(a*a) )", r.multiply(r), s );
472
473        r = a.sumNorm();
474        //System.out.println("r = " + r);
475        assertTrue("not isZERO( maxNorm(a) )", !r.isZERO() || a.isZERO());
476
477        //s = a.multiply(a).sumNorm();
478        //System.out.println("s = " + s + ", r*r = " + r.multiply(r));
479        //assertEquals("s*s == sumNorm(a*a) )", r.multiply(r), s );
480    }
481
482
483    /**
484     * Test monic and coefficient primitive part.
485     */
486    public void testMonicCPP() {
487        BigInteger bfac = new BigInteger(1);
488        GenPolynomialRing<BigInteger> ifac = new GenPolynomialRing<BigInteger>(bfac, fac);
489
490        GenPolynomial<BigInteger> ai = ifac.random(kl * 2, ll + 2, el, q);
491        ai = ai.multiply(bfac.random(kl));
492        //System.out.println("ai = " + ai);
493        GenPolynomial<BigInteger> bi = ai.coeffPrimitivePart();
494        //System.out.println("bi = " + bi);
495
496        a = PolyUtil.<BigRational> fromIntegerCoefficients(fac, ai).monic();
497        //System.out.println("a = " + a);
498        b = PolyUtil.<BigRational> fromIntegerCoefficients(fac, bi).monic();
499        //System.out.println("b = " + b);
500        assertEquals("a == b: " + a + " != " + b, a, b);
501    }
502
503}