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