001 /*
002 * $Id: GCDTimingTest.java 2724 2009-07-09 20:16:03Z kredel $
003 */
004
005 package edu.jas.ufd;
006
007
008 import junit.framework.Test;
009 import junit.framework.TestCase;
010 import junit.framework.TestSuite;
011
012 import edu.jas.arith.BigInteger;
013 import edu.jas.poly.GenPolynomial;
014 import edu.jas.poly.GenPolynomialRing;
015 import edu.jas.poly.PolyUtil;
016 import edu.jas.poly.TermOrder;
017
018
019 /**
020 * GreatestCommonDivisor timing tests with JUnit.
021 * @author Heinz Kredel.
022 */
023
024 public class GCDTimingTest extends TestCase {
025
026
027 /**
028 * main.
029 */
030 public static void main(String[] args) {
031 //BasicConfigurator.configure();
032 junit.textui.TestRunner.run(suite());
033 }
034
035
036 /**
037 * Constructs a <CODE>GCDTimingTest</CODE> object.
038 * @param name String.
039 */
040 public GCDTimingTest(String name) {
041 super(name);
042 }
043
044
045 /**
046 */
047 public static Test suite() {
048 TestSuite suite = new TestSuite(GCDTimingTest.class);
049 return suite;
050 }
051
052
053 //private final static int bitlen = 100;
054
055 GreatestCommonDivisorAbstract<BigInteger> ufd_si;
056
057
058 GreatestCommonDivisorAbstract<BigInteger> ufd_pp;
059
060
061 GreatestCommonDivisorSubres<BigInteger> ufd_sr; // because of non sparse pseudo remainder
062
063
064 GreatestCommonDivisorAbstract<BigInteger> ufd_mosi;
065
066
067 GreatestCommonDivisorAbstract<BigInteger> ufd_moevsi;
068
069
070 TermOrder to = new TermOrder(TermOrder.INVLEX);
071
072
073 GenPolynomialRing<BigInteger> dfac;
074
075
076 GenPolynomialRing<BigInteger> cfac;
077
078
079 GenPolynomialRing<GenPolynomial<BigInteger>> rfac;
080
081
082 BigInteger ai;
083
084
085 BigInteger bi;
086
087
088 BigInteger ci;
089
090
091 BigInteger di;
092
093
094 BigInteger ei;
095
096
097 GenPolynomial<BigInteger> a;
098
099
100 GenPolynomial<BigInteger> b;
101
102
103 GenPolynomial<BigInteger> c;
104
105
106 GenPolynomial<BigInteger> d;
107
108
109 GenPolynomial<BigInteger> e;
110
111
112 GenPolynomial<GenPolynomial<BigInteger>> ar;
113
114
115 GenPolynomial<GenPolynomial<BigInteger>> br;
116
117
118 GenPolynomial<GenPolynomial<BigInteger>> cr;
119
120
121 GenPolynomial<GenPolynomial<BigInteger>> dr;
122
123
124 GenPolynomial<GenPolynomial<BigInteger>> er;
125
126
127 int rl = 5;
128
129
130 int kl = 4;
131
132
133 int ll = 5;
134
135
136 int el = 3;
137
138
139 float q = 0.3f;
140
141
142 @Override
143 protected void setUp() {
144 a = b = c = d = e = null;
145 ai = bi = ci = di = ei = null;
146 ar = br = cr = dr = er = null;
147 ufd_si = new GreatestCommonDivisorSimple<BigInteger>();
148 ufd_pp = new GreatestCommonDivisorPrimitive<BigInteger>();
149 ufd_sr = new GreatestCommonDivisorSubres<BigInteger>();
150 ufd_mosi = new GreatestCommonDivisorModular(true);
151 ufd_moevsi = new GreatestCommonDivisorModular();
152 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl, to);
153 cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl - 1, to);
154 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to);
155 }
156
157
158 @Override
159 protected void tearDown() {
160 a = b = c = d = e = null;
161 ai = bi = ci = di = ei = null;
162 ar = br = cr = dr = er = null;
163 ufd_si = null;
164 ufd_pp = null;
165 ufd_sr = null;
166 dfac = null;
167 cfac = null;
168 rfac = null;
169 }
170
171
172 /**
173 * Test dummy for junit.
174 *
175 */
176 public void testDummy() {
177 assertTrue("ufd_pp != null", ufd_pp != null);
178 }
179
180
181 /**
182 * Test base gcd simple.
183 *
184 */
185 public void xtestBaseGcd() {
186
187 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 1, to);
188
189 long t;
190
191 for (int i = 0; i < 10; i++) {
192 a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q);
193 b = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q);
194 c = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q);
195 c = c.multiply(dfac.univariate(0));
196 //a = ufd.basePrimitivePart(a);
197 //b = ufd.basePrimitivePart(b);
198 //c = ufd.basePrimitivePart(c).abs();
199
200 //System.out.println("a = " + a);
201 //System.out.println("b = " + b);
202 //System.out.println("c = " + c);
203
204 if (a.isZERO() || b.isZERO() || c.isZERO()) {
205 // skip for this turn
206 continue;
207 }
208 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
209 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
210 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
211
212 a = a.multiply(c);
213 b = b.multiply(c);
214
215 System.out
216 .println("\ndegrees: a = " + a.degree() + ", b = " + b.degree() + ", c = " + c.degree());
217 /*
218 t = System.currentTimeMillis();
219 d = ufd_si.baseGcd(a,b);
220 t = System.currentTimeMillis() - t;
221 e = PolyUtil.<BigInteger>basePseudoRemainder(d,c);
222 //System.out.println("d = " + d);
223
224 assertTrue("c | gcd(ac,bc) " + e, e.isZERO() );
225 System.out.println("simple prs time = " + t);
226 */
227
228 t = System.currentTimeMillis();
229 d = ufd_pp.baseGcd(a, b);
230 t = System.currentTimeMillis() - t;
231 e = PolyUtil.<BigInteger> basePseudoRemainder(d, c);
232 //System.out.println("d = " + d);
233
234 assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
235 System.out.println("primitive prs time = " + t);
236
237
238 t = System.currentTimeMillis();
239 d = ufd_sr.baseGcd(a, b);
240 t = System.currentTimeMillis() - t;
241 e = PolyUtil.<BigInteger> basePseudoRemainder(d, c);
242 //System.out.println("d = " + d);
243
244 assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
245 System.out.println("subsresultant prs time = " + t);
246 }
247 }
248
249
250 /**
251 * Test recursive gcd.
252 *
253 */
254 public void xtestRecursiveGCD() {
255
256 cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2 - 1, to);
257 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to);
258
259 long t;
260
261 for (int i = 0; i < 5; i++) {
262 ar = rfac.random(kl, ll, el + i, q);
263 br = rfac.random(kl, ll, el + i, q);
264 cr = rfac.random(kl, ll, el, q);
265 cr = cr.multiply(rfac.univariate(0));
266 //System.out.println("ar = " + ar);
267 //System.out.println("br = " + br);
268 //System.out.println("cr = " + cr);
269
270 if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
271 // skip for this turn
272 continue;
273 }
274 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
275 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
276 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
277
278 ar = ar.multiply(cr);
279 br = br.multiply(cr);
280 //System.out.println("ar = " + ar);
281 //System.out.println("br = " + br);
282
283 System.out.println("\ndegrees: a = " + ar.degree() + ", b = " + br.degree() + ", c = "
284 + cr.degree());
285
286 t = System.currentTimeMillis();
287 dr = ufd_si.recursiveUnivariateGcd(ar, br);
288 t = System.currentTimeMillis() - t;
289 //System.out.println("dr = " + dr);
290
291 //er = PolyUtil.<BigInteger>recursivePseudoRemainder(dr,cr);
292 //System.out.println("er = " + er);
293
294 //assertTrue("c | gcd(ac,bc) " + er, er.isZERO() );
295 System.out.println("simple prs time = " + t);
296 /*
297 */
298
299 t = System.currentTimeMillis();
300 dr = ufd_pp.recursiveUnivariateGcd(ar, br);
301 t = System.currentTimeMillis() - t;
302 //System.out.println("dr = " + dr);
303
304 er = PolyUtil.<BigInteger> recursivePseudoRemainder(dr, cr);
305 //System.out.println("er = " + er);
306
307 assertTrue("c | gcd(ac,bc) " + er, er.isZERO());
308 System.out.println("primitive prs time = " + t);
309
310
311 t = System.currentTimeMillis();
312 dr = ufd_sr.recursiveUnivariateGcd(ar, br);
313 t = System.currentTimeMillis() - t;
314 //System.out.println("dr = " + dr);
315
316 er = ufd_sr.recursivePseudoRemainder(dr, cr);
317 //System.out.println("er = " + er);
318
319 assertTrue("c | gcd(ac,bc) " + er, er.isZERO());
320 System.out.println("subresultant prs time = " + t);
321 }
322 }
323
324
325 /**
326 * Test gcd.
327 *
328 */
329 public void xtestGCD() {
330
331 long t;
332
333 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 3, to);
334
335 for (int i = 0; i < 5; i++) {
336 a = dfac.random(kl + i * 30, ll + i, 2 * el, q);
337 b = dfac.random(kl + i * 30, ll + i, 2 * el, q);
338 c = dfac.random(kl, ll, el, q);
339 //c = dfac.getONE();
340 //c = c.multiply( dfac.univariate(0) ).multiply( dfac.univariate(4) );
341 //c = c.multiply( dfac.univariate(0) );
342 c = ufd_pp.primitivePart(c).abs();
343 //System.out.println("a = " + a);
344 //System.out.println("b = " + b);
345 //System.out.println("c = " + c);
346
347 if (a.isZERO() || b.isZERO() || c.isZERO()) {
348 // skip for this turn
349 continue;
350 }
351 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
352 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
353 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
354
355 a = a.multiply(c);
356 b = b.multiply(c);
357 //System.out.println("a = " + a);
358 //System.out.println("b = " + b);
359 //System.out.println("c = " + c);
360
361 System.out
362 .println("\ndegrees: a = " + a.degree() + ", b = " + b.degree() + ", c = " + c.degree());
363 /*
364 t = System.currentTimeMillis();
365 d = ufd_si.gcd(a,b);
366 t = System.currentTimeMillis() - t;
367 e = PolyUtil.<BigInteger>basePseudoRemainder(d,c);
368 //System.out.println("d = " + d);
369
370 assertTrue("c | gcd(ac,bc) " + e, e.isZERO() );
371 System.out.println("simple prs time = " + t);
372 */
373 /*
374 t = System.currentTimeMillis();
375 d = ufd_pp.gcd(a,b);
376 t = System.currentTimeMillis() - t;
377 e = PolyUtil.<BigInteger>basePseudoRemainder(d,c);
378 //System.out.println("d = " + d);
379
380 assertTrue("c | gcd(ac,bc) " + e, e.isZERO() );
381 System.out.println("primitive prs time = " + t);
382 */
383
384 t = System.currentTimeMillis();
385 d = ufd_sr.gcd(a, b);
386 t = System.currentTimeMillis() - t;
387 e = PolyUtil.<BigInteger> basePseudoRemainder(d, c);
388 //System.out.println("d = " + d);
389
390 assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
391 System.out.println("subsresultant prs time = " + t);
392
393
394 t = System.currentTimeMillis();
395 d = ufd_mosi.gcd(a, b);
396 t = System.currentTimeMillis() - t;
397 e = PolyUtil.<BigInteger> basePseudoRemainder(d, c);
398 //System.out.println("d = " + d);
399
400 assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
401 System.out.println("modular simple time = " + t);
402
403
404 t = System.currentTimeMillis();
405 d = ufd_moevsi.gcd(a, b);
406 t = System.currentTimeMillis() - t;
407 e = PolyUtil.<BigInteger> basePseudoRemainder(d, c);
408 //System.out.println("d = " + d);
409
410 assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
411 System.out.println("modular eval time = " + t);
412 }
413 }
414
415 }