Source code

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