Source code

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