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