Source code

001/*
002 * $Id: RatGenPolynomialTest.java 5949 2018-10-28 11:33:58Z kredel $
003 */
004
005package edu.jas.poly;
006
007import java.util.Map;
008import java.util.SortedMap;
009
010import junit.framework.Test;
011import junit.framework.TestCase;
012import junit.framework.TestSuite;
013
014import edu.jas.arith.BigRational;
015import edu.jas.arith.Roots;
016
017
018/**
019 * BigRational coefficients GenPolynomial tests with JUnit.
020 * @author Heinz Kredel
021 */
022
023public class RatGenPolynomialTest extends TestCase {
024
025    /**
026     * main.
027     */
028    public static void main (String[] args) {
029        junit.textui.TestRunner.run( suite() );
030    }
031
032    /**
033     * Constructs a <CODE>RatGenPolynomialTest</CODE> object.
034     * @param name String.
035     */
036    public RatGenPolynomialTest(String name) {
037        super(name);
038    }
039
040    /**
041     */ 
042    public static Test suite() {
043        TestSuite suite= new TestSuite(RatGenPolynomialTest.class);
044        return suite;
045    }
046
047    GenPolynomialRing<BigRational> fac;
048
049    GenPolynomial<BigRational> a, b, c, d, e;
050
051    int rl = 7; 
052    int kl = 10;
053    int ll = 10;
054    int el = 5;
055    float q = 0.5f;
056
057    protected void setUp() {
058        a = b = c = d = e = null;
059        fac = new GenPolynomialRing<BigRational>(new BigRational(1),rl);
060    }
061
062    protected void tearDown() {
063        a = b = c = d = e = null;
064        fac = null;
065    }
066
067    
068    /**
069     * Test constructor and toString.
070     */
071    public void testConstruction() {
072        c = fac.getONE();
073        assertTrue("length( c ) = 1", c.length() == 1);
074        assertTrue("isZERO( c )", !c.isZERO() );
075        assertTrue("isONE( c )", c.isONE() );
076
077        d = fac.getZERO();
078        assertTrue("length( d ) = 0", d.length() == 0);
079        assertTrue("isZERO( d )", d.isZERO() );
080        assertTrue("isONE( d )", !d.isONE() );
081    }
082
083
084    /**
085     * Test random polynomial.
086     */
087    public void testRandom() {
088        for (int i = 0; i < 7; i++) {
089            //a = fac.random(ll);
090            a = fac.random(kl*(i+1), ll+2*i, el+i, q );
091            //System.out.println("a = " + a);
092
093            assertTrue("length( a"+i+" ) <> 0", a.length() >= 0);
094            assertTrue(" not isZERO( a"+i+" )", !a.isZERO() );
095            assertTrue(" not isONE( a"+i+" )", !a.isONE() );
096        }
097    }
098
099
100    /**
101     * Test addition.
102     */
103    public void testAddition() {
104        a = fac.random(ll);
105        b = fac.random(ll);
106
107        c = a.sum(b);
108        d = c.subtract(b);
109        assertEquals("a+b-b = a",a,d);
110
111        c = fac.random(ll);
112
113        ExpVector u = ExpVector.random(rl,el,q);
114        BigRational x = BigRational.RNRAND(kl);
115
116        b = new GenPolynomial<BigRational>(fac,x, u);
117        c = a.sum(b);
118        d = a.sum(x,u);
119        assertEquals("a+p(x,u) = a+(x,u)",c,d);
120
121        c = a.subtract(b);
122        d = a.subtract(x,u);
123        assertEquals("a-p(x,u) = a-(x,u)",c,d);
124
125        a = new GenPolynomial<BigRational>(fac);
126        b = new GenPolynomial<BigRational>(fac,x, u);
127        c = b.sum(a);
128        d = a.sum(x,u);
129        assertEquals("a+p(x,u) = a+(x,u)",c,d);
130
131        c = a.subtract(b);
132        d = a.subtract(x,u);
133        assertEquals("a-p(x,u) = a-(x,u)",c,d);
134    }
135
136
137    /**
138     * Test object multiplication.
139     */
140    public void testMultiplication() {
141        a = fac.random(ll);
142        assertTrue("not isZERO( a )", !a.isZERO() );
143
144        b = fac.random(ll);
145        assertTrue("not isZERO( b )", !b.isZERO() );
146
147        c = b.multiply(a);
148        d = a.multiply(b);
149        assertTrue("not isZERO( c )", !c.isZERO() );
150        assertTrue("not isZERO( d )", !d.isZERO() );
151
152        //System.out.println("a = " + a);
153        //System.out.println("b = " + b);
154        e = d.subtract(c);
155        assertTrue("isZERO( a*b-b*a ) " + e, e.isZERO() );
156
157        assertTrue("a*b = b*a", c.equals(d) );
158        assertEquals("a*b = b*a",c,d);
159
160        c = fac.random(ll);
161        //System.out.println("c = " + c);
162        d = a.multiply( b.multiply(c) );
163        e = (a.multiply(b)).multiply(c);
164
165        //System.out.println("d = " + d);
166        //System.out.println("e = " + e);
167
168        //System.out.println("d-e = " + d.subtract(c) );
169
170        assertEquals("a(bc) = (ab)c",d,e);
171        assertTrue("a(bc) = (ab)c", d.equals(e) );
172
173        BigRational x = a.leadingBaseCoefficient().inverse();
174        c = a.monic();
175        d = a.multiply(x);
176        assertEquals("a.monic() = a(1/ldcf(a))",c,d);
177
178        BigRational y = b.leadingBaseCoefficient().inverse();
179        c = b.monic();
180        d = b.multiply(y);
181        assertEquals("b.monic() = b(1/ldcf(b))",c,d);
182
183        e = new GenPolynomial<BigRational>(fac,y);
184        d = b.multiply(e);
185        assertEquals("b.monic() = b(1/ldcf(b))",c,d);
186
187        d = e.multiply(b);
188        assertEquals("b.monic() = (1/ldcf(b) (0))*b",c,d);
189    }
190
191
192    /**
193     * Test BLAS level 1.
194     */
195    public void testBLAS1() {
196        a = fac.random(kl,ll,el,q);
197        b = fac.random(kl,ll,el,q);
198        c = fac.random(kl,3,el*el,q);
199        ExpVector ev = ExpVector.random(rl,el,q);
200        BigRational lc = BigRational.RNRAND(kl);
201
202        d = a.subtractMultiple(lc,b);
203        e = a.subtract( b.multiply(lc) );
204        assertEquals("a - (lc) b == a - ((lc) b)",d,e);
205
206        d = a.subtractMultiple(lc,ev,b);
207        e = a.subtract( b.multiply(lc,ev) );
208        assertEquals("a - (lc ev) b == a - ((lc ev) b)",d,e);
209
210        ExpVector fv = ExpVector.random(rl,el,q);
211        BigRational tc = BigRational.RNRAND(kl);
212
213        d = a.scaleSubtractMultiple(tc,lc,ev,b);
214        e = a.multiply(tc).subtract( b.multiply(lc,ev) );
215        assertEquals("(tc) a - (lc ev) b == ((tc) a - ((lc ev) b))",d,e);
216
217        d = a.scaleSubtractMultiple(tc,fv,lc,ev,b);
218        e = a.multiply(tc,fv).subtract( b.multiply(lc,ev) );
219        assertEquals("(tc fv) a - (lc ev) b == ((tc fv) a - ((lc ev) b))",d,e);
220    }
221
222
223    /**
224     * Test distributive law.
225     */
226    public void testDistributive() {
227        a = fac.random(kl,ll,el,q);
228        b = fac.random(kl,ll,el,q);
229        c = fac.random(kl,ll,el,q);
230
231        d = a.multiply( b.sum(c) );
232        e = a.multiply( b ).sum( a.multiply(c) );
233
234        assertEquals("a(b+c) == ab+ac",d,e);
235    }
236
237
238    /**
239     * Test object quotient and remainder.
240     */
241    public void testQuotRem() {
242        fac = new GenPolynomialRing<BigRational>(new BigRational(1),1);
243
244        a = fac.random(ll).monic();
245        assertTrue("not isZERO( a )", !a.isZERO() );
246
247        b = fac.random(ll).monic();
248        assertTrue("not isZERO( b )", !b.isZERO() );
249
250        GenPolynomial<BigRational> h = a;
251        GenPolynomial<BigRational> g = fac.random(ll).monic();
252        assertTrue("not isZERO( g )", !g.isZERO() );
253        a = a.multiply(g);
254        b = b.multiply(g);
255        //System.out.println("a = " + a);
256        //System.out.println("b = " + b);
257        //System.out.println("g = " + g);
258
259        GenPolynomial<BigRational>[] qr;
260        qr = b.quotientRemainder(a);
261        c = qr[0];
262        d = qr[1];
263        //System.out.println("q = " + c);
264        //System.out.println("r = " + d);
265        e = c.multiply(a).sum(d);
266        assertEquals("b = q a + r", b, e );
267
268        qr = a.quotientRemainder(b);
269        c = qr[0];
270        d = qr[1];
271        //System.out.println("q = " + c);
272        //System.out.println("r = " + d);
273        e = c.multiply(b).sum(d);
274        assertEquals("a = q b + r", a, e );
275
276
277        // gcd tests -------------------------------
278        c = a.gcd(b);
279        //System.out.println("gcd = " + c);
280        assertTrue("a mod gcd(a,b) = 0", a.remainder(c).isZERO() );
281        assertTrue("b mod gcd(a,b) = 0", b.remainder(c).isZERO() );
282        assertEquals("g = gcd(a,b)", c, g );
283
284
285        GenPolynomial<BigRational>[] gst;
286        gst = a.egcd(b);
287        //System.out.println("egcd = " + gst[0]);
288        //System.out.println(", s = " + gst[1] + ", t = " + gst[2]);
289        c = gst[0];
290        d = gst[1];
291        e = gst[2];
292        assertEquals("g = gcd(a,b)", c, g );
293
294        GenPolynomial<BigRational> x;
295        x = a.multiply(d).sum( b.multiply(e) ).monic(); 
296        //System.out.println("x = " + x);
297        assertEquals("gcd(a,b) = a s + b t", c, x );
298
299
300        gst = a.hegcd(b);
301        //System.out.println("hegcd = " + gst[0]);
302        //System.out.println("s = " + gst[1]);
303        c = gst[0];
304        d = gst[1];
305        assertEquals("g = gcd(a,b)", c, g );
306
307        x = a.multiply(d).remainder(b).monic(); 
308        //System.out.println("x = " + x);
309        assertEquals("gcd(a,b) = a s mod b", c, x );
310
311        //System.out.println("g = " + g);
312        //System.out.println("h = " + h);
313        c = h.modInverse(g);
314        //System.out.println("c = " + c);
315        x = c.multiply(h).remainder( g ).monic(); 
316        //System.out.println("x = " + x);
317        assertTrue("h invertible mod g", x.isONE() );
318    }
319
320
321    /**
322     * Test addition speed.
323     */
324    public void testAdditionSpeed() {
325        int ll = 100;
326        long t = 1000;
327        boolean print = false;
328        int jit = 1;
329        for (int j = 1; j < 5; j++) {
330            for (int i = 1; i < 5; i++) {
331                a = fac.random(kl, i*ll, el, q);
332                b = fac.random(kl, ll,   el, q);
333                for (int k = 0; k < jit; k++) {
334                    long t1 = System.nanoTime();
335                    c = a.sum(b);
336                    t1 = System.nanoTime() - t1;
337                    assertTrue("c != 0", !c.isZERO() );
338
339                    long t2 = System.nanoTime();
340                    d = b.sum(a);
341                    t2 = System.nanoTime() - t2;
342                    assertTrue("d != 0", !d.isZERO() );
343                    if (print) {
344                        System.out.print("#a = " + a.length() + ", #b = " + b.length() );
345                        System.out.println(",\t t1 = " + (t1/t) + ", t2 = " + (t2/t) );
346                    }
347                    //assertTrue("t2 <= t1", ((t1/t) >= (t2/t)) );
348                }
349                if (print) System.out.println();
350                assertEquals("c == d", c, d );
351            }
352            ll = 3 * ll;
353        }
354    }
355
356    
357    /**
358     * Test absolute norm.
359     */
360    public void testAbsNorm() {
361        BigRational r;
362        a = fac.getONE().negate();
363        //System.out.println("a = " + a);
364
365        r = PolyUtil.<BigRational> absNorm(a);
366        //System.out.println("r = " + r);
367        assertTrue("isONE( absNorm(-1) )", r.isONE() );
368
369        a = fac.random(kl*2, ll+2, el, q );
370        //System.out.println("a = " + a);
371
372        r = PolyUtil.<BigRational> absNorm(a);
373        //System.out.println("r = " + r);
374        assertTrue(" not isZERO( absNorm(a) )", !r.isZERO() || a.isZERO() );
375        // is now in absNorm
376        //ar = Roots.sqrt( r ); 
377        //System.out.println("ar = " + ar);
378        //assertTrue(" not isZERO( sqrt(abs(a)) )", !ar.isZERO() || a.isZERO() );
379    }
380
381}