Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.poly;
006
007
008import java.util.List;
009
010import edu.jas.arith.BigInteger;
011import edu.jas.arith.BigRational;
012
013import junit.framework.Test;
014import junit.framework.TestCase;
015import junit.framework.TestSuite;
016
017
018/**
019 * Residue test with JUnit.
020 * @author Heinz Kredel
021 */
022
023public class ResidueTest extends TestCase {
024
025
026    /**
027     * main.
028     */
029    public static void main(String[] args) {
030        junit.textui.TestRunner.run(suite());
031    }
032
033
034    /**
035     * Constructs a <CODE>ResidueTest</CODE> object.
036     * @param name String.
037     */
038    public ResidueTest(String name) {
039        super(name);
040    }
041
042
043    /**
044     * suite.
045     */
046    public static Test suite() {
047        TestSuite suite = new TestSuite(ResidueTest.class);
048        return suite;
049    }
050
051    ResidueRing<BigInteger> fac;
052
053
054    GenPolynomialRing<BigRational> pfac;
055
056
057    ResidueRing<GenPolynomial<BigRational>> mfac;
058
059
060    Residue<BigInteger> a, b, c, d, e;
061
062
063    Residue<GenPolynomial<BigRational>> ap, bp, cp, dp, ep;
064
065
066    int rl = 1;
067
068
069    int kl = 13;
070
071
072    int ll = 7;
073
074
075    int el = 3;
076
077
078    float q = 0.4f;
079
080
081    int il = 2;
082
083
084    long p = 1152921504606846883L; // 2^60-93;
085
086    @Override
087    protected void setUp() {
088        a = b = c = d = e = null;
089        ap = bp = cp = dp = ep = null;
090        BigInteger cfac = new BigInteger(1);
091        fac = new ResidueRing<BigInteger>(cfac, new BigInteger(p));
092        pfac = new GenPolynomialRing<BigRational>(new BigRational(1), 1);
093        GenPolynomial<BigRational> mo = pfac.random(kl, ll, el + 2, q);
094        while (mo.isConstant()) {
095            mo = pfac.random(kl, ll, el, q);
096        }
097        mfac = new ResidueRing<GenPolynomial<BigRational>>(pfac, mo.monic());
098        //System.out.println("fac = " + fac);
099        //System.out.println("mfac = " + mfac);
100    }
101
102
103    @Override
104    protected void tearDown() {
105        a = b = c = d = e = null;
106        ap = bp = cp = dp = ep = null;
107        fac = null;
108        pfac = null;
109        mfac = null;
110    }
111
112
113    /**
114     * Test factory for integer.
115     */
116    public void testIntRing() {
117        assertTrue("#ring infinite", fac.isFinite());
118        assertTrue("associative ring", fac.isAssociative());
119        assertTrue("commutative ring", fac.isCommutative());
120        assertTrue("characteristic p", fac.characteristic().signum() > 0);
121        assertFalse("no field", fac.isField());
122    }
123
124
125    /**
126     * Test factory for polynomial.
127     */
128    public void testPolyRing() {
129        assertFalse("#ring infinite", mfac.isFinite());
130        assertTrue("associative ring", mfac.isAssociative());
131        assertTrue("commutative ring", mfac.isCommutative());
132        assertTrue("characteristic zero", mfac.characteristic().signum() == 0);
133        assertFalse("no field", mfac.isField());
134    }
135
136
137    /**
138     * Test constructor for integer.
139     */
140    public void testIntConstruction() {
141        c = fac.getONE();
142        //System.out.println("c = " + c);
143        assertTrue("isZERO( c )", !c.isZERO());
144        assertTrue("isONE( c )", c.isONE());
145
146        d = fac.getZERO();
147        //System.out.println("d = " + d);
148        assertTrue("isZERO( d )", d.isZERO());
149        assertTrue("isONE( d )", !d.isONE());
150
151        List<Residue<BigInteger>> gens = fac.generators();
152        //System.out.println("gens = " + gens);
153        assertTrue("#gens == 1: ", gens.size() == 1);
154        for (Residue<BigInteger> v : gens) {
155            a = fac.parse(v.toString());
156            assertEquals("a == v", a, v);
157        }
158    }
159
160
161    /**
162     * Test constructor for polynomial.
163     */
164    public void testPolyConstruction() {
165        cp = mfac.getONE();
166        assertTrue("isZERO( cp )", !cp.isZERO());
167        assertTrue("isONE( cp )", cp.isONE());
168
169        dp = mfac.getZERO();
170        assertTrue("isZERO( dp )", dp.isZERO());
171        assertTrue("isONE( dp )", !dp.isONE());
172
173        List<Residue<GenPolynomial<BigRational>>> gens = mfac.generators();
174        //System.out.println("gens = " + gens);
175        assertTrue("#gens == 2: ", gens.size() == 2);
176        for (Residue<GenPolynomial<BigRational>> v : gens) {
177            ap = mfac.parse(v.toString());
178            assertEquals("ap == v", ap, v);
179        }
180    }
181
182
183    /**
184     * Test random integer.
185     */
186    public void testIntRandom() {
187        for (int i = 0; i < 7; i++) {
188            a = fac.random(kl * (i + 1));
189            if (a.isZERO()) {
190                continue;
191            }
192            //a = fac.random(kl*(i+1), ll+2*i, el+i, q );
193            //System.out.println("a = " + a);
194            assertTrue(" not isZERO( a" + i + " )", !a.isZERO());
195            assertTrue(" not isONE( a" + i + " )", !a.isONE());
196        }
197    }
198
199
200    /**
201     * Test random polynomial.
202     */
203    public void testPolyRandom() {
204        for (int i = 0; i < 7; i++) {
205            ap = mfac.random(kl + i);
206            if (ap.isZERO()) {
207                continue;
208            }
209            assertTrue(" not isZERO( ap" + i + " )", !ap.isZERO());
210            assertTrue(" not isONE( ap" + i + " )", !ap.isONE());
211        }
212    }
213
214
215    /**
216     * Test integer addition.
217     */
218    public void testIntAddition() {
219        a = fac.random(kl);
220        b = fac.random(kl);
221
222        c = a.sum(b);
223        d = c.subtract(b);
224        assertEquals("a+b-b = a", a, d);
225
226        c = a.sum(b);
227        d = b.sum(a);
228        assertEquals("a+b = b+a", c, d);
229
230        c = fac.random(kl);
231        d = c.sum(a.sum(b));
232        e = c.sum(a).sum(b);
233        assertEquals("c+(a+b) = (c+a)+b", d, e);
234
235
236        c = a.sum(fac.getZERO());
237        d = a.subtract(fac.getZERO());
238        assertEquals("a+0 = a-0", c, d);
239
240        c = fac.getZERO().sum(a);
241        d = fac.getZERO().subtract(a.negate());
242        assertEquals("0+a = 0+(-a)", c, d);
243    }
244
245
246    /**
247     * Test polynomial addition.
248     */
249    public void testPolyAddition() {
250        ap = mfac.random(kl);
251        bp = mfac.random(kl);
252        //System.out.println("a = " + a);
253        //System.out.println("b = " + b);
254
255        cp = ap.sum(bp);
256        dp = cp.subtract(bp);
257        assertEquals("a+b-b = a", ap, dp);
258
259        cp = ap.sum(bp);
260        dp = bp.sum(ap);
261        //System.out.println("c = " + c);
262        //System.out.println("d = " + d);
263
264        assertEquals("a+b = b+a", cp, dp);
265
266        cp = mfac.random(kl);
267        dp = cp.sum(ap.sum(bp));
268        ep = cp.sum(ap).sum(bp);
269        assertEquals("c+(a+b) = (c+a)+b", dp, ep);
270
271
272        cp = ap.sum(mfac.getZERO());
273        dp = ap.subtract(mfac.getZERO());
274        assertEquals("a+0 = a-0", cp, dp);
275
276        cp = mfac.getZERO().sum(ap);
277        dp = mfac.getZERO().subtract(ap.negate());
278        assertEquals("0+a = 0+(-a)", cp, dp);
279    }
280
281
282    /**
283     * Test integer multiplication.
284     */
285    public void testIntMultiplication() {
286        a = fac.random(kl);
287        if (a.isZERO()) {
288            return;
289        }
290        assertTrue("not isZERO( a )", !a.isZERO());
291
292        b = fac.random(kl);
293        if (b.isZERO()) {
294            return;
295        }
296        assertTrue("not isZERO( b )", !b.isZERO());
297
298        c = b.multiply(a);
299        d = a.multiply(b);
300        assertTrue("not isZERO( c )", !c.isZERO());
301        assertTrue("not isZERO( d )", !d.isZERO());
302
303        //System.out.println("a = " + a);
304        //System.out.println("b = " + b);
305        e = d.subtract(c);
306        assertTrue("isZERO( a*b-b*a ) " + e, e.isZERO());
307
308        assertTrue("a*b = b*a", c.equals(d));
309        assertEquals("a*b = b*a", c, d);
310
311        c = fac.random(kl);
312        //System.out.println("c = " + c);
313        d = a.multiply(b.multiply(c));
314        e = (a.multiply(b)).multiply(c);
315
316        //System.out.println("d = " + d);
317        //System.out.println("e = " + e);
318
319        //System.out.println("d-e = " + d.subtract(c) );
320
321        assertEquals("a(bc) = (ab)c", d, e);
322        assertTrue("a(bc) = (ab)c", d.equals(e));
323
324        c = a.multiply(fac.getONE());
325        d = fac.getONE().multiply(a);
326        assertEquals("a*1 = 1*a", c, d);
327
328        if (a.isUnit()) {
329            c = a.inverse();
330            d = c.multiply(a);
331            //System.out.println("a = " + a);
332            //System.out.println("c = " + c);
333            //System.out.println("d = " + d);
334            assertTrue("a*1/a = 1", d.isONE());
335
336            Residue<BigInteger>[] qr;
337            c = b.multiply(a);
338            qr = c.quotientRemainder(a);
339            if (qr[1].isZERO()) {
340                //System.out.println("qr = " + qr[0] + " rem " + qr[1]);
341                assertEquals("b*a / a == b", qr[0], b);
342                assertTrue("b*a rem a == 0", qr[1].isZERO());
343            }
344        }
345    }
346
347
348    /**
349     * Test polynomial multiplication.
350     */
351    public void testPolyMultiplication() {
352        ap = mfac.random(kl);
353        if (ap.isZERO()) {
354            return;
355        }
356        assertTrue("not isZERO( a )", !ap.isZERO());
357
358        bp = mfac.random(kl);
359        if (bp.isZERO()) {
360            return;
361        }
362        assertTrue("not isZERO( b )", !bp.isZERO());
363
364        cp = bp.multiply(ap);
365        dp = ap.multiply(bp);
366        assertTrue("not isZERO( c )", !cp.isZERO());
367        assertTrue("not isZERO( d )", !dp.isZERO());
368
369        //System.out.println("a = " + a);
370        //System.out.println("b = " + b);
371        ep = dp.subtract(cp);
372        assertTrue("isZERO( a*b-b*a ) " + ep, ep.isZERO());
373
374        assertTrue("a*b = b*a", cp.equals(dp));
375        assertEquals("a*b = b*a", cp, dp);
376
377        cp = mfac.random(kl);
378        //System.out.println("c = " + c);
379        dp = ap.multiply(bp.multiply(cp));
380        ep = (ap.multiply(bp)).multiply(cp);
381
382        //System.out.println("d = " + d);
383        //System.out.println("e = " + e);
384
385        //System.out.println("d-e = " + d.subtract(c) );
386
387        assertEquals("a(bc) = (ab)c", dp, ep);
388        assertTrue("a(bc) = (ab)c", dp.equals(ep));
389
390        cp = ap.multiply(mfac.getONE());
391        dp = mfac.getONE().multiply(ap);
392        assertEquals("a*1 = 1*a", cp, dp);
393
394        if (ap.isUnit()) {
395            cp = ap.inverse();
396            dp = cp.multiply(ap);
397            //System.out.println("a = " + a);
398            //System.out.println("c = " + c);
399            //System.out.println("d = " + d);
400            assertTrue("a*1/a = 1", dp.isONE());
401
402            Residue<GenPolynomial<BigRational>>[] qr;
403            cp = bp.multiply(ap);
404            qr = cp.quotientRemainder(ap);
405            if (qr[1].isZERO()) {
406                //System.out.println("qr = " + qr[0] + " rem " + qr[1]);
407                assertEquals("b*a / a == b", qr[0], bp);
408                assertTrue("b*a rem a == 0", qr[1].isZERO());
409            }
410        }
411    }
412
413}