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