001 /*
002 * $Id: ModLongTest.java 3473 2011-01-07 20:01:05Z kredel $
003 */
004
005 package edu.jas.arith;
006
007
008 import java.io.StringReader;
009
010 import junit.framework.Test;
011 import junit.framework.TestCase;
012 import junit.framework.TestSuite;
013
014 import edu.jas.kern.PrettyPrint;
015 import edu.jas.structure.NotInvertibleException;
016
017
018 /**
019 * ModLong tests with JUnit.
020 * @author Heinz Kredel.
021 */
022
023 public 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.clone();
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 }