Source code

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