Source code

001/*
002 * $Id: GCDPrimitiveTest.java 5863 2018-07-20 11:13:34Z kredel $
003 */
004
005package edu.jas.fd;
006
007
008import java.util.List;
009
010
011import edu.jas.arith.BigRational;
012import edu.jas.kern.ComputerThreads;
013import edu.jas.poly.GenPolynomial;
014import edu.jas.poly.GenSolvablePolynomial;
015import edu.jas.poly.GenSolvablePolynomialRing;
016import edu.jas.poly.PolyUtil;
017import edu.jas.poly.PolynomialList;
018import edu.jas.poly.RecSolvablePolynomial;
019import edu.jas.poly.RecSolvablePolynomialRing;
020import edu.jas.poly.RelationGenerator;
021import edu.jas.poly.TermOrder;
022import edu.jas.poly.WeylRelationsIterated;
023
024import junit.framework.Test;
025import junit.framework.TestCase;
026import junit.framework.TestSuite;
027
028
029/**
030 * GCD Primitive PRS algorithm tests with JUnit. <b>Note:</b> not in sync with
031 * implementation.
032 * @author Heinz Kredel
033 */
034
035public class GCDPrimitiveTest extends TestCase {
036
037
038    /**
039     * main.
040     */
041    public static void main(String[] args) {
042        junit.textui.TestRunner.run(suite());
043        ComputerThreads.terminate();
044    }
045
046
047    /**
048     * Constructs a <CODE>GCDPrimitiveTest</CODE> object.
049     * @param name String.
050     */
051    public GCDPrimitiveTest(String name) {
052        super(name);
053    }
054
055
056    /**
057     */
058    public static Test suite() {
059        TestSuite suite = new TestSuite(GCDPrimitiveTest.class);
060        return suite;
061    }
062
063
064    GreatestCommonDivisorAbstract<BigRational> fd, fds;
065
066
067    TermOrder to = new TermOrder(TermOrder.INVLEX);
068
069
070    GenSolvablePolynomialRing<BigRational> dfac;
071
072
073    //GenSolvablePolynomialRing<GenPolynomial<BigRational>> rfac;
074    RecSolvablePolynomialRing<BigRational> rfac;
075
076
077    GenSolvablePolynomial<BigRational> a, b, a0, b0, c, d, e, a1, b1;
078
079
080    GenSolvablePolynomial<GenPolynomial<BigRational>> ar, br, ar0, br0, cr, dr, er, sr;
081
082
083    int rl = 4;
084
085
086    int kl = 2;
087
088
089    int ll = 2;
090
091
092    int el = 3;
093
094
095    float q = 0.25f;
096
097
098    @Override
099    protected void setUp() {
100        a = b = c = d = e = null;
101        ar = br = cr = dr = er = null;
102        String[] vars = new String[] { "a", "b", "c", "d" };
103        BigRational cf = new BigRational(1);
104        fd = new GreatestCommonDivisorPrimitive<BigRational>(cf);
105        fds = new GreatestCommonDivisorSimple<BigRational>(cf);
106        dfac = new GenSolvablePolynomialRing<BigRational>(cf, rl, to, vars);
107        RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>();
108        dfac.addRelations(wl);
109        rfac = (RecSolvablePolynomialRing<BigRational>) dfac.recursive(1);
110    }
111
112
113    @Override
114    protected void tearDown() {
115        a = b = c = d = e = null;
116        ar = br = cr = dr = er = null;
117        fd = null;
118        dfac = null;
119        rfac = null;
120    }
121
122
123    /**
124     * Test base gcd primitive.
125     */
126    public void testBaseGcdPrimitive() {
127        String[] uvars = new String[] { "x" };
128        dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), 1, to, uvars);
129
130        for (int i = 0; i < 5; i++) {
131            a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q);
132            b = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q);
133            c = dfac.random(kl * (i + 2), ll + 2, el + 2, q);
134            c = c.multiply(dfac.univariate(0));
135            if (c.isZERO()) {
136                // skip for this turn
137                continue;
138            }
139            //a = fd.basePrimitivePart(a);
140            //b = fd.basePrimitivePart(b);
141            c = (GenSolvablePolynomial<BigRational>) fd.leftBasePrimitivePart(c).abs();
142
143            //System.out.println("a  = " + a);
144            //System.out.println("b  = " + b);
145            //System.out.println("c  = " + c);
146            //assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
147
148            a = a.multiply(c);
149            b = b.multiply(c);
150
151            d = fd.leftBaseGcd(a, b);
152            e = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> basePseudoRemainder(d, c);
153            //System.out.println("d  = " + d);
154            //System.out.println("c  = " + c);
155            assertTrue("c | gcd(ac,bc): " + e, e.isZERO());
156
157            e = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> basePseudoRemainder(a, d);
158            //System.out.println("e = " + e);
159            assertTrue("gcd(a,b) | a: " + e, e.isZERO());
160
161            e = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> basePseudoRemainder(b, d);
162            //System.out.println("e = " + e);
163            assertTrue("gcd(a,b) | b " + e, e.isZERO());
164        }
165    }
166
167
168    /**
169     * Test univariate recursive left gcd primitive.
170     */
171    @SuppressWarnings("cast")
172    public void testRecursiveLeftGCDPrimitive() {
173        //String[] vars = new String[] { "a", "b", "c", "d" };
174        String[] vars = new String[] { "a", "b" };
175        dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, vars);
176        RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>();
177        dfac.addRelations(wl);
178        //System.out.println("dfac = " + dfac.toScript());
179        rfac = (RecSolvablePolynomialRing<BigRational>) dfac.recursive(1);
180        //System.out.println("rfac = " + rfac.toScript());
181
182        RecSolvablePolynomialRing<BigRational> rrfacTemp = rfac;
183        GenSolvablePolynomialRing<GenPolynomial<BigRational>> rrfac = rfac;
184
185        GenSolvablePolynomialRing<BigRational> rcfac = (GenSolvablePolynomialRing<BigRational>) rfac.coFac;
186        SolvableQuotientRing<BigRational> qfac = new SolvableQuotientRing<BigRational>(rcfac);
187        QuotSolvablePolynomialRing<BigRational> rqfac = new QuotSolvablePolynomialRing<BigRational>(qfac,
188                        rrfac);
189        List<GenSolvablePolynomial<GenPolynomial<BigRational>>> rl = rrfacTemp.coeffTable.relationList();
190        List<GenPolynomial<GenPolynomial<BigRational>>> rlc = PolynomialList
191                        .<GenPolynomial<BigRational>> castToList(rl);
192        rqfac.polCoeff.coeffTable.addRelations(rlc);
193        //System.out.println("rrfac  = " + rrfac.toScript());
194        //System.out.println("rcfac  = " + rcfac.toScript());
195        //System.out.println("qfac   = " + qfac.toScript());
196        //System.out.println("rqfac  = " + rqfac.toScript());
197
198        //kl = 3; ll = 4; //
199        el = 2;
200
201        ar = rfac.random(kl, ll, el + 1, q);
202        br = rfac.random(kl, ll, el, q);
203        cr = rfac.random(kl, ll, el, q);
204        //cr = (RecSolvablePolynomial<BigRational>) cr.abs();
205        cr = (RecSolvablePolynomial<BigRational>) PolyUtil.<BigRational> monic(cr);
206        //cr = (RecSolvablePolynomial<BigRational>) fd.recursivePrimitivePart(cr).abs();
207        //cr = rfac.getONE();
208        //cr = rfac.parse("a+b+c+d");
209
210        //ar = rfac.parse("1/3 b^3 - 1/6");
211        //ar = rfac.parse("1/3 b^2 - 1/6");
212        //br = rfac.parse("( -1/2 ) b + 3 a");
213        //nok: cr = rfac.parse("b * a - 5 b");
214        //cr = rfac.parse("a - 5");
215
216        //System.out.println("ar = " + ar);
217        //System.out.println("br = " + br);
218        //System.out.println("cr = " + cr);
219
220        if (br.isZERO() || cr.isZERO()) {
221            br = rfac.parse("( -1/2 ) b + 3 a");
222            cr = rfac.parse("a * b - 5 b");
223        }
224
225        //ar = cr.multiply(ar); 
226        //br = cr.multiply(br);
227        ar = ar.multiply(cr);
228        br = br.multiply(cr);
229        //System.out.println("ar = " + ar);
230        //System.out.println("br = " + br);
231        //if (true) return;
232
233        long ts = System.currentTimeMillis();
234        //sr = rfac.getONE(); 
235        sr = fds.leftRecursiveUnivariateGcd(ar, br);
236        ts = System.currentTimeMillis() - ts;
237        //System.out.println("cr = " + cr);
238
239        long tp = System.currentTimeMillis();
240        dr = fd.leftRecursiveUnivariateGcd(ar, br);
241        tp = System.currentTimeMillis() - tp;
242        //System.out.println("cr = " + cr);
243        //System.out.println("dr = " + dr);
244        //System.out.println("sr = " + sr);
245        //System.out.println("time: ts = " + ts + ", tp = " + tp);
246        assertTrue("time: ts = " + ts + ", tp = " + tp, ts + tp > 0);
247
248        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(dr, cr);
249        //System.out.println("er = " + er);
250        assertTrue("c | gcd(ac,bc): " + er, er.isZERO());
251
252        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(ar, dr);
253        //System.out.println("er = " + er);
254        assertTrue("gcd(ac,bc) | ac: " + er, er.isZERO());
255
256        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(br, dr);
257        //System.out.println("er = " + er);
258        assertTrue("gcd(ac,bc) | bc: " + er, er.isZERO());
259
260        GenSolvablePolynomial<SolvableQuotient<BigRational>> ap, bp, dp, gp, ep; // cp, apm, bpm, cpm, dpm, gpm;
261        ap = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, ar);
262        bp = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, br);
263        //cp = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, cr);
264        dp = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, dr);
265        //apm = ap.monic();
266        //bpm = bp.monic();
267        //cpm = cp.monic();
268        //dpm = dp.monic();
269        //System.out.println("ap  = " + ap);
270        //System.out.println("apm = " + apm);
271        //System.out.println("bp  = " + bp);
272        //System.out.println("bpm = " + bpm);
273        //System.out.println("cp  = " + cp);
274        //System.out.println("cpm = " + cpm);
275        //System.out.println("dp  = " + dp);
276        //System.out.println("dpm = " + dpm);
277
278        GreatestCommonDivisorAbstract<SolvableQuotient<BigRational>> fdq = new GreatestCommonDivisorPrimitive<SolvableQuotient<BigRational>>(
279                        qfac);
280        gp = fdq.leftBaseGcd(ap, bp);
281        //gpm = gp.monic();
282        //System.out.println("gp  = " + gp);
283        //System.out.println("gpm = " + gpm);
284
285        ep = FDUtil.<SolvableQuotient<BigRational>> leftBaseSparsePseudoRemainder(gp, dp);
286        //System.out.println("ep  = " + ep);
287        assertTrue("c | gcd(ac,bc): " + ep, ep.isZERO());
288
289        ep = FDUtil.<SolvableQuotient<BigRational>> leftBaseSparsePseudoRemainder(ap, gp);
290        //System.out.println("ep  = " + ep);
291        assertTrue("gcd(ac,bc)| ac): " + ep, ep.isZERO());
292
293        ep = FDUtil.<SolvableQuotient<BigRational>> leftBaseSparsePseudoRemainder(bp, gp);
294        //System.out.println("ep  = " + ep);
295        assertTrue("gcd(ac,bc)| bc): " + ep, ep.isZERO());
296    }
297
298
299    /**
300     * Test univariate recursive right gcd primitive.
301     */
302    @SuppressWarnings("cast")
303    public void testRecursiveRightGCDPrimitive() {
304        //String[] vars = new String[] { "a", "b", "c", "d" };
305        String[] vars = new String[] { "a", "b" };
306        dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, vars);
307        RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>();
308        dfac.addRelations(wl);
309        //System.out.println("dfac = " + dfac.toScript());
310        rfac = (RecSolvablePolynomialRing<BigRational>) dfac.recursive(1);
311        //System.out.println("rfac = " + rfac.toScript());
312
313        RecSolvablePolynomialRing<BigRational> rrfacTemp = rfac;
314        GenSolvablePolynomialRing<GenPolynomial<BigRational>> rrfac = rfac;
315
316        GenSolvablePolynomialRing<BigRational> rcfac = (GenSolvablePolynomialRing<BigRational>) rfac.coFac;
317        SolvableQuotientRing<BigRational> qfac = new SolvableQuotientRing<BigRational>(rcfac);
318        QuotSolvablePolynomialRing<BigRational> rqfac = new QuotSolvablePolynomialRing<BigRational>(qfac,
319                        rrfac);
320        List<GenSolvablePolynomial<GenPolynomial<BigRational>>> rl = rrfacTemp.coeffTable.relationList();
321        List<GenPolynomial<GenPolynomial<BigRational>>> rlc = PolynomialList
322                        .<GenPolynomial<BigRational>> castToList(rl);
323        rqfac.polCoeff.coeffTable.addRelations(rlc);
324        //System.out.println("rrfac  = " + rrfac.toScript());
325        //System.out.println("rcfac  = " + rcfac.toScript());
326        //System.out.println("qfac   = " + qfac.toScript());
327        //System.out.println("rqfac  = " + rqfac.toScript());
328
329        //kl = 3; ll = 4; //
330        el = 3;
331
332        ar = rfac.random(kl, ll, el + 1, q);
333        br = rfac.random(kl, ll, el, q);
334        cr = rfac.random(kl, ll, el, q);
335        //cr = (RecSolvablePolynomial<BigRational>) cr.abs();
336        cr = (RecSolvablePolynomial<BigRational>) PolyUtil.<BigRational> monic(cr);
337        //cr = (RecSolvablePolynomial<BigRational>) fd.recursivePrimitivePart(cr).abs();
338        //cr = rfac.getONE();
339        //cr = rfac.parse("a+b+c+d");
340
341        //ar = rfac.parse("1/3 b^3 - 1/6");
342        //ar = rfac.parse("1/3 b^2 - 1/6");
343        //br = rfac.parse("( -1/2 ) b + 3 a");
344        //nok: cr = rfac.parse("b * a - 5 b");
345        //cr = rfac.parse("a - 5");
346
347        //ar = rfac.parse("359/95 a b^2 + 275/124 a");
348        //br = rfac.parse("814/189 b + 135/44 a");
349        //cr = rfac.parse("b - 612/25");
350
351        //System.out.println("ar = " + ar);
352        //System.out.println("br = " + br);
353        //System.out.println("cr = " + cr);
354
355        if (br.isZERO() || cr.isZERO()) {
356            br = rfac.parse("( -1/2 ) b + 3 a");
357            cr = rfac.parse("a * b - 5 b");
358        }
359
360        ar = cr.multiply(ar);
361        br = cr.multiply(br);
362        //System.out.println("ar = " + ar);
363        //System.out.println("br = " + br);
364
365        long ts = System.currentTimeMillis();
366        //sr = rfac.getONE(); 
367        sr = fds.rightRecursiveUnivariateGcd(ar, br);
368        ts = System.currentTimeMillis() - ts;
369        //System.out.println("cr = " + cr);
370
371        long tp = System.currentTimeMillis();
372        dr = fd.rightRecursiveUnivariateGcd(ar, br);
373        tp = System.currentTimeMillis() - tp;
374        //System.out.println("cr = " + cr);
375        //System.out.println("dr = " + dr);
376        //System.out.println("sr = " + sr);
377        //System.out.println("time: ts = " + ts + ", tp = " + tp);
378        assertTrue("time: ts = " + ts + ", tp = " + tp, ts + tp > 0);
379
380        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(dr,
381                        cr);
382        //System.out.println("er = " + er);
383        assertTrue("c | gcd(ca,cb): " + er, er.isZERO());
384
385        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(ar,
386                        dr);
387        //System.out.println("er = " + er);
388        assertTrue("gcd(ca,cb) | ca: " + er, er.isZERO());
389
390        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(br,
391                        dr);
392        //System.out.println("er = " + er);
393        assertTrue("gcd(ca,cb) | cb: " + er, er.isZERO());
394    }
395
396
397    /**
398     * Test arbitrary recursive gcd primitive.
399     */
400    @SuppressWarnings("cast")
401    public void testArbitraryRecursiveGCDPrimitive() {
402        String[] cvars = new String[] { "a", "b" };
403        String[] vars = new String[] { "c" };
404        dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, cvars);
405        RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>();
406        dfac.addRelations(wl);
407        //System.out.println("dfac = " + dfac.toScript());
408        rfac = new RecSolvablePolynomialRing<BigRational>(dfac, to, vars);
409        //rfac = (RecSolvablePolynomialRing<BigRational>) dfac.recursive(1);
410        //System.out.println("rfac = " + rfac.toScript());
411
412        //kl = 3; ll = 2;
413        el = 2;
414
415        ar0 = rfac.random(kl, ll, el + 1, q);
416        br0 = rfac.random(kl, ll, el, q);
417        cr = rfac.random(kl, ll, el, q);
418
419        //ar0 = rfac.parse("a + b c^2 ");
420        //br0 = rfac.parse("( a^2 - 1/3  ) c - 1/4");
421        //cr = rfac.parse("(b - 1/2 a^2) c");
422
423        //cr = (RecSolvablePolynomial<BigRational>) fd.recursivePrimitivePart(cr).abs();
424        cr = (RecSolvablePolynomial<BigRational>) cr.monic();
425        if (cr.isZERO()) {
426            cr = rfac.getONE();
427        }
428
429        //System.out.println("ar = " + ar);
430        //System.out.println("br = " + br);
431        //System.out.println("cr = " + cr);
432
433        // left gcd
434        ar = ar0.multiply(cr);
435        br = br0.multiply(cr);
436        //System.out.println("ar = " + ar);
437        //System.out.println("br = " + br);
438
439        dr = fd.leftRecursiveGcd(ar, br);
440        //System.out.println("cr = " + cr);
441        //System.out.println("dr = " + dr);
442
443        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(dr, cr);
444        //System.out.println("er = " + er);
445        assertTrue("c | gcd(ac,bc): " + er, er.isZERO());
446
447        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(ar, dr);
448        //System.out.println("er = " + er);
449        assertTrue("gcd(a,b) | a: " + er, er.isZERO());
450
451        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(br, dr);
452        //System.out.println("er = " + er);
453        assertTrue("gcd(a,b) | b: " + er, er.isZERO());
454
455        // right gcd
456        ar = cr.multiply(ar0);
457        br = cr.multiply(br0);
458        //System.out.println("ar = " + ar);
459        //System.out.println("br = " + br);
460
461        dr = fd.rightRecursiveGcd(ar, br);
462        //System.out.println("cr = " + cr);
463        //System.out.println("dr = " + dr);
464
465        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(dr,
466                        cr);
467        //System.out.println("er = " + er);
468        assertTrue("c | gcd(ca,cb) " + er, er.isZERO());
469
470        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(ar,
471                        dr);
472        //System.out.println("er = " + er);
473        assertTrue("gcd(ca,cb) | ca " + er, er.isZERO());
474
475        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(br,
476                        dr);
477        //System.out.println("er = " + er);
478        assertTrue("gcd(ca,cb) | cb " + er, er.isZERO());
479    }
480
481
482    /**
483     * Test full gcd primitive.
484     */
485    public void testGCDPrimitive() {
486        String[] vars = new String[] { "a", "b", "c", "d" };
487        //String[] vars = new String[] { "a", "b" };
488        dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, vars);
489        RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>();
490        dfac.addRelations(wl);
491        //System.out.println("dfac = " + dfac.toScript());
492
493        //kl = 3; 
494        ll = 4;
495        el = 4;
496
497        //a = dfac.random(kl, ll, el, q);
498        //b = dfac.random(kl, ll, el, q);
499        //c = dfac.random(kl, ll, el, q);
500        //c = c.multiply(dfac.univariate(0));
501
502        a = dfac.parse("1/3 b^3 - 1/6 + d");
503        b = dfac.parse("( -1/2 ) b + 3 a^2 + d");
504        ////b = dfac.parse("( -1/2 ) b + 3 a^2 + c");
505        ////c = dfac.parse("(a - 5 b) + c + d");
506        ////ok: c = dfac.parse("(a - b) c");
507        ////c = dfac.parse("c (a - b)");
508        //c = dfac.parse("(a - b) + c + d ");
509        c = dfac.parse("(a - b) + c");
510        //c = dfac.parse("(a - b) + b^3");
511        //c = dfac.parse("(a - b) + d");
512
513        //a = dfac.parse("2 b^3 * d^2 + 2/3 a + 3/2");
514        //b = dfac.parse("2/3 d + 1/2 a^3 + 3/4");
515        //c = dfac.parse("c^2 * d - 1/2 a^3 * d + 5/4 d");
516
517        //c = (GenSolvablePolynomial<BigRational>) fd.primitivePart(c).abs();
518        c = c.monic();
519        if (c.isZERO()) {
520            c = dfac.getONE();
521        }
522        //System.out.println("a = " + a);
523        //System.out.println("b = " + b);
524        //System.out.println("c = " + c);
525
526        // left
527        a0 = a;
528        b0 = b;
529        a = a0.multiply(c);
530        b = b0.multiply(c);
531        //System.out.println("a = " + a);
532        //System.out.println("b = " + b);
533        //System.out.println("c = " + c);
534
535        d = fd.leftGcd(a, b);
536        //System.out.println("c = " + c);
537        //System.out.println("d = " + d);
538
539        e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(d, c);
540        //System.out.println("e = " + e);
541        assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
542
543        e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(a, c);
544        //System.out.println("e = " + e);
545        assertTrue("c | ac " + e, e.isZERO());
546        e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(a, d);
547        //System.out.println("e = " + e);
548        assertTrue("gcd(a,b) | a " + e, e.isZERO());
549
550        e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(b, c);
551        //System.out.println("e = " + e);
552        assertTrue("c | bc " + e, e.isZERO());
553        e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(b, d);
554        //System.out.println("e = " + e);
555        assertTrue("gcd(a,b) | b " + e, e.isZERO());
556
557
558        // right
559        a = c.multiply(a0);
560        b = c.multiply(b0);
561        //System.out.println("a = " + a);
562        //System.out.println("b = " + b);
563        //System.out.println("c = " + c);
564
565        d = fd.rightGcd(a, b);
566        //System.out.println("c  = " + c);
567        //System.out.println("d  = " + d);
568
569        e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(d, c);
570        //System.out.println("e = " + e);
571        assertTrue("c | gcd(ac,bc): " + e, e.isZERO());
572
573        e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(a, c);
574        //System.out.println("e = " + e);
575        assertTrue("c | ac: " + e, e.isZERO());
576        e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(b, c);
577        //System.out.println("e = " + e);
578        assertTrue("c | bc: " + e, e.isZERO());
579
580        e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(a, d);
581        //System.out.println("e = " + e);
582        //e = FDUtil.<BigRational> divideRightPolynomial(a,d);
583        //System.out.println("e = " + e);
584        assertTrue("gcd(a,b) | a: " + e, e.isZERO());
585
586        e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(b, d);
587        //System.out.println("e = " + e);
588        //e = FDUtil.<BigRational> divideRightPolynomial(b,d);
589        //System.out.println("e = " + e);
590        assertTrue("gcd(a,b) | b: " + e, e.isZERO());
591    }
592
593}