001/*
002 * $Id: GCDTimingTest.java 3789 2011-10-01 18:54:43Z kredel $
003 */
004
005package edu.jas.ufd;
006
007
008import junit.framework.Test;
009import junit.framework.TestCase;
010import junit.framework.TestSuite;
011
012import edu.jas.arith.BigInteger;
013import edu.jas.poly.GenPolynomial;
014import edu.jas.poly.GenPolynomialRing;
015import edu.jas.poly.PolyUtil;
016import edu.jas.poly.TermOrder;
017
018
019/**
020 * GreatestCommonDivisor timing tests with JUnit.
021 * @author Heinz Kredel.
022 */
023
024public 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}