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