Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.arith;
006
007
008import java.io.StringReader;
009import java.util.ArrayList;
010import java.util.List;
011
012import edu.jas.kern.PrettyPrint;
013import edu.jas.structure.NotInvertibleException;
014
015import junit.framework.Test;
016import junit.framework.TestCase;
017import junit.framework.TestSuite;
018
019
020/**
021 * ModInt tests with JUnit.
022 * @author Heinz Kredel
023 */
024
025public class ModIntTest extends TestCase {
026
027
028    /**
029     * main.
030     */
031    public static void main(String[] args) {
032        junit.textui.TestRunner.run(suite());
033    }
034
035
036    /**
037     * Constructs a <CODE>ModIntTest</CODE> object.
038     * @param name String
039     */
040    public ModIntTest(String name) {
041        super(name);
042    }
043
044
045    /**
046     */
047    public static Test suite() {
048        TestSuite suite = new TestSuite(ModIntTest.class);
049        return suite;
050    }
051
052
053    ModIntRing zm, z1, z2;
054
055
056    ModInt a, b, c, d, e;
057
058
059    @Override
060    protected void setUp() {
061        zm = z1 = z2 = null;
062        a = b = c = d = e = null;
063    }
064
065
066    @Override
067    protected void tearDown() {
068        zm = z1 = z2 = null;
069        a = b = c = d = e = null;
070    }
071
072
073    protected static java.math.BigInteger getPrime1() {
074        int prime = 2; //2^15-135; //2^60-93; // 2^30-35; //19; knuth (2,390)
075        for (int i = 1; i < 15; i++) {
076            prime *= 2;
077        }
078        prime -= 135;
079        //System.out.println("p1 = " + prime);
080        return new java.math.BigInteger("" + prime);
081    }
082
083
084    protected static java.math.BigInteger getPrime2() {
085        int prime = 2; //2^60-93; // 2^30-35; //19; knuth (2,390)
086        for (int i = 1; i < 30; i++) {
087            prime *= 2;
088        }
089        prime -= 35;
090        //System.out.println("p2 = " + prime);
091        return new java.math.BigInteger("" + prime);
092    }
093
094
095    protected static java.math.BigInteger getPrime3() {
096        int prime = 37;
097        //System.out.println("p2 = " + prime);
098        return new java.math.BigInteger("" + prime);
099    }
100
101
102    /**
103     * Test static initialization and constants.
104     */
105    public void testConstants() {
106        zm = new ModIntRing(5);
107        d = new ModInt(zm, 11);
108        a = zm.getZERO();
109        b = zm.getONE();
110        c = b.subtract(b);
111
112        assertEquals("1-1 = 0", c, a);
113        assertTrue("1-1 = 0", c.isZERO());
114        assertTrue("1 = 1", b.isONE());
115    }
116
117
118    /**
119     * Test bitLength.
120     */
121    public void testBitLength() {
122        zm = new ModIntRing(163);
123        a = zm.getZERO();
124        b = zm.getONE();
125        c = zm.random(30);
126        //System.out.println("c = " + c);
127        //System.out.println("len(c) = " + c.bitLength());
128
129        assertEquals("len(0) = 1", 1L, a.bitLength());
130        assertEquals("len(1) = 2", 2, b.bitLength());
131        assertEquals("len(-1) = len(mod)", BigInteger.bitLength(zm.modul), b.negate().bitLength());
132        assertTrue("len(random) >= 1", 1 <= c.bitLength());
133    }
134
135
136    /**
137     * Test constructor and toString.
138     */
139    public void testConstructor() {
140        zm = new ModIntRing("5");
141        a = new ModInt(zm, "64");
142        b = new ModInt(zm, "34");
143
144        assertEquals("64(5) = 34(5)", a, b);
145
146        zm = new ModIntRing("7");
147        a = new ModInt(zm, "-4");
148        b = new ModInt(zm, "3");
149
150        assertEquals("-4(7) = 3(7)", a, b);
151
152        String s = "61111111111111111";
153        zm = new ModIntRing("10");
154        try {
155            a = new ModInt(zm, s);
156            fail("s to large");
157        } catch (NumberFormatException e) {
158            // pass
159        }
160        s = "611111111";
161        a = new ModInt(zm, s);
162        String t = a.toString();
163
164        if (PrettyPrint.isTrue()) {
165            String st = "1";
166            assertEquals("stringConstr = toString", st, t);
167        } else {
168            String st = "1 mod(10)";
169            assertEquals("stringConstr = toString", st, t);
170        }
171
172        zm = new ModIntRing(7);
173        a = new ModInt(zm, 1);
174        b = new ModInt(zm, -1);
175        c = b.sum(a);
176
177        assertTrue("1 = 1", a.isONE());
178        assertTrue("1 = 1", b.isUnit());
179        assertEquals("1+(-1) = 0", c, zm.getZERO());
180
181        zm = new ModIntRing(5);
182        a = new ModInt(zm, 3);
183        b = new ModInt(zm, 0);
184        c = zm.parse(" 13 ");
185        assertEquals("3(5) = 3(5)", a, c);
186
187        StringReader sr = new StringReader("  13\n w ");
188        c = zm.parse(sr);
189        assertEquals("3(5) = 3(5)", a, c);
190        //System.out.println("c = " + c);
191    }
192
193
194    /**
195     * Test random modular integers.
196     */
197    public void testRandom() {
198        zm = new ModIntRing(19);
199        a = zm.random(500);
200        b = a.copy();
201        c = b.subtract(a);
202
203        assertEquals("a-b = 0", c, zm.getZERO());
204
205        d = new ModInt(new ModIntRing(b.getModul()), b.getVal());
206        assertEquals("sign(a-a) = 0", 0, b.compareTo(d));
207    }
208
209
210    /**
211     * Test addition.
212     * 
213     */
214    public void testAddition() {
215        zm = new ModIntRing(19);
216
217        a = zm.random(100);
218        b = a.sum(a);
219        c = b.subtract(a);
220
221        assertEquals("a+a-a = a", c, a);
222        assertEquals("a+a-a = a", 0, c.compareTo(a));
223
224        d = a.sum(zm.getZERO());
225        assertEquals("a+0 = a", d, a);
226        d = a.subtract(zm.getZERO());
227        assertEquals("a-0 = a", d, a);
228        d = a.subtract(a);
229        assertEquals("a-a = 0", d, zm.getZERO());
230
231    }
232
233
234    /**
235     * Test multiplication.
236     */
237    @SuppressWarnings("unchecked")
238    public void testMultiplication() {
239        zm = new ModIntRing(5);
240        d = new ModInt(zm, 11);
241
242        a = zm.random(100);
243        if (a.isZERO()) {
244            a = d;
245        }
246        b = a.multiply(a);
247        c = b.divide(a);
248
249        assertEquals("a*a/a = a", c, a);
250        assertEquals("a*a/a = a", 0, c.compareTo(a));
251
252        d = a.multiply(zm.getONE());
253        assertEquals("a*1 = a", d, a);
254        d = a.divide(zm.getONE());
255        assertEquals("a/1 = a", d, a);
256
257        a = zm.random(100);
258        if (a.isZERO()) {
259            a = d;
260        }
261        b = a.inverse();
262        c = a.multiply(b);
263
264        assertTrue("a*1/a = 1", c.isONE());
265
266        try {
267            a = zm.getZERO().inverse();
268            fail("0 invertible");
269        } catch (NotInvertibleException expected) {
270            //ok
271        }
272
273        zm = new ModIntRing(5 * 3);
274        a = new ModInt(zm, 5);
275        assertFalse("5 !unit mod 15", a.isUnit());
276
277        try {
278            b = a.inverse();
279            fail("5 invertible");
280        } catch (ModularNotInvertibleException expected) {
281            //ok
282            //expected.printStackTrace();
283            assertTrue("f  = 15 ", expected.f.equals(new BigInteger(15)));
284            assertTrue("f1 =  5 ", expected.f1.equals(new BigInteger(5)));
285            assertTrue("f2 =  3 ", expected.f2.equals(new BigInteger(3)));
286            assertTrue("f  =  f1*f2 ", expected.f.equals(expected.f1.multiply(expected.f2)));
287        } catch (NotInvertibleException e) {
288            //e.printStackTrace();
289            fail("wrong exception " + e);
290        }
291    }
292
293
294    /**
295     * Test chinese remainder.
296     */
297    public void testChineseRemainder() {
298        zm = new ModIntRing(19 * 13);
299        a = zm.random(9);
300        //System.out.println("a = " + a);
301        z1 = new ModIntRing(19);
302        b = new ModInt(z1, a.getVal());
303        //System.out.println("b = " + b);
304        z2 = new ModIntRing(13);
305        c = new ModInt(z2, a.getVal());
306        //System.out.println("c = " + c);
307        d = new ModInt(z2, 19);
308        d = d.inverse();
309        //System.out.println("d = " + d);
310
311        e = zm.chineseRemainder(b, d, c);
312        //System.out.println("e = " + e);
313
314        assertEquals("cra(a mod 19,a mod 13) = a", a, e);
315
316        java.math.BigInteger p1 = getPrime2();
317        try {
318            z1 = new ModIntRing(p1);
319            fail("p1 too large");
320        } catch (IllegalArgumentException e) {
321            //pass
322        }
323        p1 = getPrime3();
324        java.math.BigInteger p2 = new java.math.BigInteger("19");
325        java.math.BigInteger p1p2 = p1.multiply(p2);
326        //System.out.println("p1p2 = " + p1p2);
327        //System.out.println("prime p1 ? = " + p1.isProbablePrime(66));
328        //System.out.println("prime p2 ? = " + p2.isProbablePrime(33));
329        //System.out.println("prime p1p1 ? = " + p1p2.isProbablePrime(3));
330        zm = new ModIntRing(p1p2);
331        z1 = new ModIntRing(p1);
332        z2 = new ModIntRing(p2);
333
334        for (int i = 0; i < 5; i++) {
335            a = zm.random((59 + 29) / 2); //60+30 );
336            //System.out.println("a = " + a);
337            b = new ModInt(z1, a.getVal());
338            //System.out.println("b = " + b);
339            c = new ModInt(z2, a.getVal());
340            //System.out.println("c = " + c);
341            ModInt di = new ModInt(z2, p1);
342            d = di.inverse();
343            //System.out.println("d = " + d);
344
345            e = zm.chineseRemainder(b, d, c);
346            //System.out.println("e = " + e);
347
348            assertEquals("cra(a mod p1,a mod p2) = a ", a, e);
349        }
350    }
351
352
353    /**
354     * Test chinese remainder of lists.
355     */
356    public void testChineseRemainderLists() {
357        zm = new ModIntRing(19 * 13);
358        z1 = new ModIntRing(19);
359        z2 = new ModIntRing(13);
360
361        List<ModInt> L1 = new ArrayList<ModInt>();
362        List<ModInt> L2 = new ArrayList<ModInt>();
363        List<ModInt> L;
364
365        for (int i = 0; i < 7; i++) {
366            a = zm.random(9);
367            //System.out.println("a = " + a);
368            b = new ModInt(z1, a.getVal());
369            //System.out.println("b = " + b);
370            c = new ModInt(z2, a.getVal());
371            //System.out.println("c = " + c);
372            L1.add(b);
373            L2.add(c);
374        }
375        //System.out.println("L1 = " + L1);
376        //System.out.println("L2 = " + L2);
377
378        L = ModIntRing.chineseRemainder(z1.getONE(), z2.getONE(), L1, L2);
379        //System.out.println("L = " + L);
380        assertEquals("19 * 13) = a.modul: ", zm, L.get(0).ring);
381
382        for (ModInt d : L) {
383            b = new ModInt(z1, d.getVal());
384            //System.out.println("b = " + b);
385            c = new ModInt(z2, d.getVal());
386            //System.out.println("c = " + c);
387            assertTrue("cra(a mod 19, a mod 13) = a: ", L1.contains(b));
388            assertTrue("cra(a mod 19, a mod 13) = a: ", L2.contains(c));
389        }
390    }
391
392
393    /**
394     * Test timing ModInt to ModInteger.
395     */
396    public void testTiming() {
397        zm = new ModIntRing(getPrime1());
398        a = zm.random(9);
399        //System.out.println("a = " + a);
400        b = zm.random(9);
401        //System.out.println("b = " + b);
402        c = zm.getONE();
403        //System.out.println("c = " + c);
404
405        ModIntegerRing ZM = new ModIntegerRing(zm.modul);
406        ModInteger A = new ModInteger(ZM, a.getVal());
407        ModInteger B = new ModInteger(ZM, b.getVal());
408        ModInteger C = ZM.getONE();
409
410        int run = 1000; //000;
411        long t = System.currentTimeMillis();
412        for (int i = 0; i < run; i++) {
413            if (c.isZERO()) {
414                c = zm.getONE();
415            }
416            c = a.sum(b.divide(c));
417        }
418        t = System.currentTimeMillis() - t;
419        //System.out.println("long time = " + t);
420
421        ModInteger D = new ModInteger(ZM, c.getVal());
422        t = System.currentTimeMillis();
423        for (int i = 0; i < run; i++) {
424            if (C.isZERO()) {
425                C = ZM.getONE();
426            }
427            C = A.sum(B.divide(C));
428        }
429        t = System.currentTimeMillis() - t;
430        //System.out.println("BigInteger time = " + t);
431
432        assertEquals("C == D ", C, D);
433    }
434
435
436    /**
437     * Test iterator.
438     */
439    public void testIterator() {
440        int m = 5 * 2;
441        zm = new ModIntRing(m);
442        ModInt j = null;
443        for (ModInt i : zm) {
444            //System.out.println("i = " + i);
445            j = i;
446        }
447        ModInt end = new ModInt(zm, m - 1);
448        assertTrue("j == m-1 ", j.equals(end));
449    }
450
451}