Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.fd;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011
012import edu.jas.arith.BigRational;
013import edu.jas.gb.SolvableGroebnerBaseAbstract;
014import edu.jas.gb.SolvableGroebnerBaseSeq;
015import edu.jas.kern.ComputerThreads;
016import edu.jas.poly.GenPolynomial;
017import edu.jas.poly.GenSolvablePolynomial;
018import edu.jas.poly.GenSolvablePolynomialRing;
019import edu.jas.poly.PolyUtil;
020import edu.jas.poly.PolynomialList;
021import edu.jas.poly.RecSolvablePolynomial;
022import edu.jas.poly.RecSolvablePolynomialRing;
023import edu.jas.poly.RelationGenerator;
024import edu.jas.poly.TermOrder;
025import edu.jas.poly.WeylRelationsIterated;
026
027import junit.framework.Test;
028import junit.framework.TestCase;
029import junit.framework.TestSuite;
030
031
032/**
033 * GCD Fake PRS algorithm tests with JUnit. <b>Note:</b> not in sync with
034 * implementation.
035 * @author Heinz Kredel
036 */
037
038public class GCDFakeTest extends TestCase {
039
040
041    /**
042     * main.
043     */
044    public static void main(String[] args) {
045        junit.textui.TestRunner.run(suite());
046        ComputerThreads.terminate();
047    }
048
049
050    /**
051     * Constructs a <CODE>GCDFakeTest</CODE> object.
052     * @param name String.
053     */
054    public GCDFakeTest(String name) {
055        super(name);
056    }
057
058
059    /**
060     */
061    public static Test suite() {
062        TestSuite suite = new TestSuite(GCDFakeTest.class);
063        return suite;
064    }
065
066
067    GreatestCommonDivisorAbstract<BigRational> fd;
068
069
070    TermOrder to = new TermOrder(TermOrder.INVLEX);
071
072
073    GenSolvablePolynomialRing<BigRational> dfac;
074
075
076    //GenSolvablePolynomialRing<GenPolynomial<BigRational>> rfac;
077    RecSolvablePolynomialRing<BigRational> rfac;
078
079
080    GenSolvablePolynomial<BigRational> a, b, a0, b0, c, d, e;
081
082
083    GenSolvablePolynomial<GenPolynomial<BigRational>> ar, br, cr, dr, er, ar0, br0;
084
085
086    int rl = 4;
087
088
089    int kl = 2;
090
091
092    int ll = 2;
093
094
095    int el = 3;
096
097
098    float q = 0.25f;
099
100
101    @Override
102    protected void setUp() {
103        a = b = c = d = e = null;
104        ar = br = cr = dr = er = null;
105        String[] vars = new String[] { "a", "b", "c", "d" };
106        BigRational cf = new BigRational(1);
107        fd = new GreatestCommonDivisorFake<BigRational>(cf);
108        dfac = new GenSolvablePolynomialRing<BigRational>(cf, rl, to, vars);
109        RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>();
110        dfac.addRelations(wl);
111        rfac = (RecSolvablePolynomialRing<BigRational>) dfac.recursive(1);
112        //System.out.println("dfac = " + dfac);
113    }
114
115
116    @Override
117    protected void tearDown() {
118        a = b = c = d = e = null;
119        ar = br = cr = dr = er = null;
120        fd = null;
121        dfac = null;
122        rfac = null;
123    }
124
125
126    /**
127     * Test base gcd simple.
128     */
129    public void testBaseGcdFake() {
130        String[] uvars = new String[] { "x" };
131        dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), 1, to, uvars);
132        for (int i = 0; i < 3; i++) {
133            a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q);
134            b = dfac.random(kl * (i + 1), ll + i, el + 2, q);
135            c = dfac.random(kl * (i + 1), ll + 1, el + 1, q);
136            c = c.multiply(dfac.univariate(0));
137            if (c.isZERO()) {
138                // skip for this turn
139                continue;
140            }
141            //a = fd.basePrimitivePart(a);
142            //b = fd.basePrimitivePart(b);
143            //c = (GenSolvablePolynomial<BigRational>) fd.basePrimitivePart(c).abs();
144            //System.out.println("a  = " + a);
145            //System.out.println("b  = " + b);
146            //System.out.println("c  = " + c);
147
148            a = a.multiply(c);
149            b = b.multiply(c);
150
151            d = fd.leftBaseGcd(a, b);
152            e = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> baseSparsePseudoRemainder(d, c);
153            //System.out.println("d  = " + d);
154            //System.out.println("c  = " + c);
155            assertTrue("c | gcd(ac,bc) " + e, e.isZERO() || d.isONE());
156
157            e = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> baseSparsePseudoRemainder(a, d);
158            //System.out.println("e = " + e);
159            assertTrue("gcd(a,b) | a " + e, e.isZERO());
160
161            e = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> baseSparsePseudoRemainder(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 simple.
170     */
171    @SuppressWarnings("cast")
172    public void testRecursiveLeftGCDFake() {
173        String[] vars = new String[] { "a", "b" };
174        dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, vars);
175        RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>();
176        dfac.addRelations(wl);
177        //System.out.println("dfac = " + dfac.toScript());
178        rfac = (RecSolvablePolynomialRing<BigRational>) dfac.recursive(1);
179        //System.out.println("rfac = " + rfac.toScript());
180
181        RecSolvablePolynomialRing<BigRational> rrfacTemp = rfac;
182        GenSolvablePolynomialRing<GenPolynomial<BigRational>> rrfac = rfac;
183
184        GenSolvablePolynomialRing<BigRational> rcfac = (GenSolvablePolynomialRing<BigRational>) rfac.coFac;
185        SolvableQuotientRing<BigRational> qfac = new SolvableQuotientRing<BigRational>(rcfac);
186        QuotSolvablePolynomialRing<BigRational> rqfac = new QuotSolvablePolynomialRing<BigRational>(qfac,
187                        rrfac);
188        List<GenSolvablePolynomial<GenPolynomial<BigRational>>> rl = rrfacTemp.coeffTable.relationList();
189        List<GenPolynomial<GenPolynomial<BigRational>>> rlc = PolynomialList
190                        .<GenPolynomial<BigRational>> castToList(rl);
191        rqfac.polCoeff.coeffTable.addRelations(rlc);
192        //System.out.println("rrfac  = " + rrfac.toScript());
193        //System.out.println("rcfac  = " + rcfac.toScript());
194        //System.out.println("qfac   = " + qfac.toScript());
195        //System.out.println("rqfac  = " + rqfac.toScript());
196
197        //kl = 3; 
198        ll = 3;
199        el = 3;
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("( ( -31/19 )  ) b^3 - ( 781/260 a - 641/372  )");
211        //br = rfac.parse("( ( -1/5 ) a - 1/4  ) b^2 - 11/12  b - ( 47/17 a + 29/30  )");
212        //cr = rfac.parse(" ( a + 9/8  ) b + ( 285/208 a + 191/280  )");
213
214        //ar = rfac.parse("b^3 - ( a )");
215        //br = rfac.parse("( a ) b^2 - 1/2 b");
216        //cr = rfac.parse("b + ( a )");
217
218        //ar = rfac.parse("( 2/23 a - 1/2  ) b^3 + 617/672  b^2 - ( 5 a + 307/154  )");
219        //br = rfac.parse("( ( -673/330 )  ) b - ( 2/5 a - 566969/1651860  )");
220        //cr = rfac.parse("( a - 2287945/213324  )");
221
222        //ar = rfac.parse("( b^2 + 1/2 )");
223        //br = rfac.parse("( a^2 b - ( a - 1/3 ) )");
224        //cr = rfac.parse("( b + a - 1/5 )");
225
226        //System.out.println("ar = " + ar);
227        //System.out.println("br = " + br);
228        //System.out.println("cr = " + cr);
229
230        if (cr.isZERO()) {
231            cr = rfac.getONE();
232        }
233        //ar = cr.multiply(ar);
234        //br = cr.multiply(br);
235        ar = ar.multiply(cr);
236        br = br.multiply(cr);
237        //System.out.println("ar = " + ar);
238        //System.out.println("br = " + br);
239
240        dr = fd.leftRecursiveUnivariateGcd(ar, br);
241        //System.out.println("cr = " + cr);
242        //System.out.println("dr = " + dr);
243
244        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(dr, cr);
245        //System.out.println("er = " + er);
246        assertTrue("c | gcd(ac,bc) " + er, er.isZERO() || dr.isONE());
247
248        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(ar, dr);
249        //System.out.println("er = " + er);
250        assertTrue("gcd(a,b) | a " + er, er.isZERO());
251
252        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(br, dr);
253        //System.out.println("er = " + er);
254        assertTrue("gcd(a,b) | b " + er, er.isZERO());
255
256        //if (true) return;
257        GenSolvablePolynomial<SolvableQuotient<BigRational>> ap, bp, cp, dp, gp, ep, apm, bpm, cpm, dpm, gpm;
258        ap = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, ar);
259        bp = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, br);
260        cp = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, cr);
261        dp = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, dr);
262        apm = ap.monic();
263        bpm = bp.monic();
264        cpm = cp.monic();
265        dpm = dp.monic();
266        //System.out.println("ap  = " + ap);
267        //System.out.println("apm = " + apm);
268        //System.out.println("bp  = " + bp);
269        //System.out.println("bpm = " + bpm);
270        //System.out.println("cp  = " + cp);
271        //System.out.println("cpm = " + cpm);
272        //System.out.println("dp  = " + dp);
273        //System.out.println("dpm = " + dpm);
274        assertTrue("", apm.leadingBaseCoefficient().isONE());
275        assertTrue("", bpm.leadingBaseCoefficient().isONE());
276        assertTrue("", cpm.leadingBaseCoefficient().isONE());
277        assertTrue("", dpm.leadingBaseCoefficient().isONE());
278
279        GreatestCommonDivisorAbstract<SolvableQuotient<BigRational>> fdq = new GreatestCommonDivisorFake<SolvableQuotient<BigRational>>(
280                        qfac);
281        gp = fdq.leftBaseGcd(ap, bp);
282        gpm = gp.monic();
283        //System.out.println("gp  = " + gp);
284        //System.out.println("gpm = " + gpm);
285        assertTrue("", gpm.leadingBaseCoefficient().isONE());
286
287        ep = FDUtil.<SolvableQuotient<BigRational>> leftBaseSparsePseudoRemainder(gp, dp);
288        //System.out.println("ep  = " + ep);
289        assertTrue("c | gcd(ac,bc): " + ep, ep.isZERO());
290
291        ep = FDUtil.<SolvableQuotient<BigRational>> leftBaseSparsePseudoRemainder(ap, gp);
292        //System.out.println("ep  = " + ep);
293        assertTrue("gcd(ac,bc)| ac): " + ep, ep.isZERO());
294
295        ep = FDUtil.<SolvableQuotient<BigRational>> leftBaseSparsePseudoRemainder(bp, gp);
296        //System.out.println("ep  = " + ep);
297        assertTrue("gcd(ac,bc)| bc): " + ep, ep.isZERO());
298    }
299
300
301    /**
302     * Test univariate recursive right gcd simple.
303     */
304    @SuppressWarnings("cast")
305    public void testRecursiveRightGCDFake() {
306        String[] vars = new String[] { "a", "b" };
307        dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, vars);
308        RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>();
309        dfac.addRelations(wl);
310        //System.out.println("dfac = " + dfac.toScript());
311        rfac = (RecSolvablePolynomialRing<BigRational>) dfac.recursive(1);
312        //System.out.println("rfac = " + rfac.toScript());
313
314        RecSolvablePolynomialRing<BigRational> rrfacTemp = rfac;
315        GenSolvablePolynomialRing<GenPolynomial<BigRational>> rrfac = rfac;
316
317        GenSolvablePolynomialRing<BigRational> rcfac = (GenSolvablePolynomialRing<BigRational>) rfac.coFac;
318        SolvableQuotientRing<BigRational> qfac = new SolvableQuotientRing<BigRational>(rcfac);
319        QuotSolvablePolynomialRing<BigRational> rqfac = new QuotSolvablePolynomialRing<BigRational>(qfac,
320                        rrfac);
321        List<GenSolvablePolynomial<GenPolynomial<BigRational>>> rl = rrfacTemp.coeffTable.relationList();
322        List<GenPolynomial<GenPolynomial<BigRational>>> rlc = PolynomialList
323                        .<GenPolynomial<BigRational>> castToList(rl);
324        rqfac.polCoeff.coeffTable.addRelations(rlc);
325        //System.out.println("rrfac  = " + rrfac.toScript());
326        //System.out.println("rcfac  = " + rcfac.toScript());
327        //System.out.println("qfac   = " + qfac.toScript());
328        //System.out.println("rqfac  = " + rqfac.toScript());
329
330        //kl = 3; 
331        int ll = 3;
332        int el = 3;
333
334        ar = rfac.random(kl, ll, el + 1, q);
335        br = rfac.random(kl, ll, el, q);
336        cr = rfac.random(kl, ll, el, q);
337        ////cr = (RecSolvablePolynomial<BigRational>) cr.abs();
338        cr = (RecSolvablePolynomial<BigRational>) PolyUtil.<BigRational> monic(cr);
339        //cr = (RecSolvablePolynomial<BigRational>) fd.recursivePrimitivePart(cr).abs();
340        //cr = rfac.getONE();
341
342        //System.out.println("ar = " + ar);
343        //System.out.println("br = " + br);
344        //System.out.println("cr = " + cr);
345
346        if (cr.isZERO()) {
347            cr = rfac.getONE();
348        }
349        ar = cr.multiply(ar);
350        br = cr.multiply(br);
351        //ar = ar.multiply(cr);
352        //br = br.multiply(cr);
353        //System.out.println("ar = " + ar);
354        //System.out.println("br = " + br);
355
356        dr = fd.rightRecursiveUnivariateGcd(ar, br);
357        //System.out.println("cr = " + cr);
358        //System.out.println("dr = " + dr);
359
360        //er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightPseudoQuotient(dr, cr);
361        //System.out.println("dr/cr = " + er);
362
363        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(dr,
364                        cr);
365        //System.out.println("er = " + er);
366        assertTrue("c | gcd(ac,bc) " + er, er.isZERO() || dr.isONE());
367
368        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(ar,
369                        dr);
370        //System.out.println("er = " + er);
371        assertTrue("gcd(a,b) | a " + er, er.isZERO());
372
373        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(br,
374                        dr);
375        //System.out.println("er = " + er);
376        assertTrue("gcd(a,b) | b " + er, er.isZERO());
377    }
378
379
380    /**
381     * Test arbitrary recursive gcd simple.
382     */
383    @SuppressWarnings("cast")
384    public void testArbitraryRecursiveGCDFake() {
385        String[] cvars = new String[] { "a", "b" };
386        String[] vars = new String[] { "c" };
387        dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, cvars);
388        RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>();
389        dfac.addRelations(wl);
390        //System.out.println("dfac = " + dfac.toScript());
391        rfac = new RecSolvablePolynomialRing<BigRational>(dfac, to, vars);
392        //System.out.println("rfac = " + rfac.toScript());
393
394        //kl = 3; ll = 2;
395        int el = 2;
396
397        ar0 = rfac.random(kl, ll, el + 1, q);
398        br0 = rfac.random(kl, ll, el, q);
399        cr = rfac.random(kl, ll, el, q);
400
401        //ar = rfac.parse("a + b c^2 ");
402        //br = rfac.parse("( a^2 - 1/3  ) c - 1/4");
403        //cr = rfac.parse("(b - 1/2 a^2) c");
404        //ar = rfac.parse("( 2/11 a * b^2 + 11/24 b - 11/6 a^2 )");
405        //br = rfac.parse("( 14/13 b^2 - 1/69 )");
406        //cr = rfac.parse("c + 33/133 a");
407        //ar0 = rfac.parse("( a * b^2 + 1/2 b - 1/6 a^2 )");
408        //br0 = rfac.parse("( b^2 - 1/5 )");
409        //cr = rfac.parse("c + 3/13 a");
410
411        //cr = (RecSolvablePolynomial<BigRational>) fd.recursivePrimitivePart(cr).abs();
412        cr = (RecSolvablePolynomial<BigRational>) cr.monic();
413        if (cr.isZERO()) {
414            cr = rfac.getONE();
415        }
416        //System.out.println("ar = " + ar);
417        //System.out.println("br = " + br);
418        //System.out.println("cr = " + cr);
419
420        // left gcd
421        ar = ar0.multiply(cr);
422        br = br0.multiply(cr);
423        //System.out.println("ar = " + ar);
424        //System.out.println("br = " + br);
425
426        dr = fd.leftRecursiveGcd(ar, br);
427        //System.out.println("cr = " + cr);
428        //System.out.println("dr = " + dr);
429
430        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(dr, cr);
431        //System.out.println("er = " + er);
432        assertTrue("c | gcd(ac,bc) " + er, er.isZERO() || dr.isONE());
433
434        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(ar, dr);
435        //System.out.println("er = " + er);
436        assertTrue("gcd(ac,bc) | ac " + er, er.isZERO());
437
438        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(br, dr);
439        //System.out.println("er = " + er);
440        assertTrue("gcd(ac,bc) | bc " + er, er.isZERO());
441
442
443        // right gcd
444        ar = cr.multiply(ar0);
445        br = cr.multiply(br0);
446        //System.out.println("ar = " + ar);
447        //System.out.println("br = " + br);
448
449        dr = fd.rightRecursiveGcd(ar, br);
450        //System.out.println("cr = " + cr);
451        //System.out.println("dr = " + dr);
452
453        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(dr,
454                        cr);
455        //System.out.println("er = " + er);
456        assertTrue("c | gcd(ca,cb) " + er, er.isZERO() || dr.isONE());
457
458        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(ar,
459                        dr);
460        //System.out.println("er = " + er);
461        assertTrue("gcd(ca,cb) | ca " + er, er.isZERO());
462
463        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(br,
464                        dr);
465        //System.out.println("er = " + er);
466        assertTrue("gcd(ca,cb) | cb " + er, er.isZERO());
467    }
468
469
470    /**
471     * Test full gcd simple, 4 variables.
472     */
473    public void testGCDFake() {
474        String[] vars = new String[] { "a", "b", "c", "d" };
475        //String[] vars = new String[] { "a", "b" };
476        dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, vars);
477        RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>();
478        //RelationGenerator<BigRational> wl = new WeylRelations<BigRational>();
479        dfac.addRelations(wl);
480        //System.out.println("dfac = " + dfac.toScript());
481
482        //kl = 3; 
483        ll = 4;
484        el = 4;
485
486        //a = dfac.random(kl, ll, el, q);
487        //b = dfac.random(kl, ll, el, q);
488        //c = dfac.random(kl, ll, el, q);
489        //c = c.multiply(dfac.univariate(0));
490
491        a0 = dfac.parse("b^3 - 1/6 + d");
492        b0 = dfac.parse("b + 3 a^2 + d");
493        //b = dfac.parse("( -1/2 ) b + 3 a^2 + d");
494        //c = dfac.parse("(a - 5 b) + c + d");
495        //ok: c = dfac.parse("(a - b) c");
496        //c = dfac.parse("(a - b) + c + d ");
497        //c = dfac.parse("(a - b) + c");
498        //c = dfac.parse("(a - b) + b^2");
499        c = dfac.parse("c - a - b");
500        //c = dfac.parse("d - c - b - a");
501        //c = dfac.parse("(a - b) + d");
502        //c = dfac.parse("b + d");
503        //c = dfac.parse("a + d");
504
505        //a = dfac.parse("2 b^3 * d^2 + 2/3 a + 3/2");
506        //b = dfac.parse("2/3 d + 1/2 a^3 + 3/4");
507        //c = dfac.parse("c^2 * d - 1/2 a^3 * d + 5/4 d");
508
509        //c = (GenSolvablePolynomial<BigRational>) fd.primitivePart(c).abs();
510        c = c.monic();
511        if (c.isZERO()) {
512            c = dfac.getONE();
513        }
514        //System.out.println("a = " + a);
515        //System.out.println("b = " + b);
516        //System.out.println("c = " + c);
517
518        a = a0.multiply(c);
519        b = b0.multiply(c);
520        //System.out.println("a = " + a);
521        //System.out.println("b = " + b);
522        //System.out.println("c = " + c);
523
524
525        List<GenSolvablePolynomial<BigRational>> L = new ArrayList<GenSolvablePolynomial<BigRational>>();
526        L.add(a);
527        L.add(b);
528        SolvableGroebnerBaseAbstract<BigRational> sbb = new SolvableGroebnerBaseSeq<BigRational>();
529
530        // left 
531        List<GenSolvablePolynomial<BigRational>> Llgb = sbb.leftGB(L);
532        //System.out.println("leftGB = " + Llgb);
533        //List<GenSolvablePolynomial<BigRational>> Ltgb = sbb.twosidedGB(L);
534        //System.out.println("twosidedGB = " + Ltgb);
535
536        d = fd.leftGcd(a, b);
537        //System.out.println("gb = " + Llgb);
538        //System.out.println("c  = " + c);
539        //System.out.println("d  = " + d);
540        assertTrue("d in leftGB", sbb.sred.leftNormalform(Llgb, d).isZERO() || d.isONE());
541
542        e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(d, c);
543        //System.out.println("e = " + e);
544        assertTrue("c | gcd(ac,bc): " + e, e.isZERO() || d.isONE());
545
546        e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(a, c);
547        //System.out.println("e = " + e);
548        assertTrue("c | ac: " + e, e.isZERO());
549        e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(b, c);
550        //System.out.println("e = " + e);
551        assertTrue("c | bc: " + e, e.isZERO());
552
553        e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(a, d);
554        //System.out.println("e = " + e);
555        //e = FDUtil.<BigRational> divideRightPolynomial(a,d);
556        //System.out.println("e = " + e);
557        assertTrue("gcd(a,b) | a: " + e, e.isZERO());
558
559        e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(b, d);
560        //System.out.println("e = " + e);
561        //e = FDUtil.<BigRational> divideRightPolynomial(b,d);
562        //System.out.println("e = " + e);
563        assertTrue("gcd(a,b) | b: " + e, e.isZERO());
564
565
566        // right
567        a = c.multiply(a0);
568        b = c.multiply(b0);
569        //System.out.println("a = " + a);
570        //System.out.println("b = " + b);
571        //System.out.println("c = " + c);
572
573        //List<GenSolvablePolynomial<BigRational>> Lrgb = sbb.rightGB(L); // too long
574        //System.out.println("rightGB = " + Lrgb);
575        //List<GenSolvablePolynomial<BigRational>> Ltgb = sbb.twosidedGB(L);
576        //System.out.println("twosidedGB = " + Ltgb);
577
578        d = fd.rightGcd(a, b);
579        //System.out.println("gb = " + Llgb);
580        //System.out.println("c  = " + c);
581        //System.out.println("d  = " + d);
582
583        e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(d, c);
584        //System.out.println("e = " + e);
585        assertTrue("c | gcd(ac,bc): " + e, e.isZERO() || d.isONE());
586
587        e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(a, c);
588        //System.out.println("e = " + e);
589        assertTrue("c | ac: " + e, e.isZERO());
590        e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(b, c);
591        //System.out.println("e = " + e);
592        assertTrue("c | bc: " + e, e.isZERO());
593
594        e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(a, d);
595        //System.out.println("e = " + e);
596        //e = FDUtil.<BigRational> divideRightPolynomial(a,d);
597        //System.out.println("e = " + e);
598        assertTrue("gcd(a,b) | a: " + e, e.isZERO());
599
600        e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(b, d);
601        //System.out.println("e = " + e);
602        //e = FDUtil.<BigRational> divideRightPolynomial(b,d);
603        //System.out.println("e = " + e);
604        assertTrue("gcd(a,b) | b: " + e, e.isZERO());
605    }
606
607
608    /**
609     * Test rational coefficients gcd polynomial cofactor tests.
610     */
611    public void testRatCofactors() {
612        //System.out.println("dfac = " + dfac.toScript());
613        do {
614            a = dfac.random(kl, ll*2, el, q);
615        } while (a.isZERO()||a.isConstant());
616        do {
617            b = dfac.random(kl, ll*2, el, q/2f);
618        } while (b.isZERO()||b.isConstant());
619        do {
620            c = dfac.random(kl, ll, el, q);
621        } while (c.isZERO()||c.isConstant());
622        c = c.monic();
623        //System.out.println("a = " + a);
624        //System.out.println("b = " + b);
625        //System.out.println("c = " + c);
626
627        // non commutative left
628        //System.out.println("right: ");
629        d = c.multiply(a);
630        e = c.multiply(b);
631        //System.out.println("d = " + d);
632        //System.out.println("e = " + e);
633
634        GenSolvablePolynomial<BigRational>[] gco = fd.leftGcdCofactors(dfac, d, e);
635        //System.out.println("left gco[0] = " + gco[0]);
636        //System.out.println("gco[1] = " + gco[1]);
637        //System.out.println("gco[2] = " + gco[2]);
638
639        GenSolvablePolynomial<BigRational> ca, cb;
640        ca = gco[0].multiply(gco[1]);
641        cb = gco[0].multiply(gco[2]);
642        //System.out.println("ca = " + ca);
643        //System.out.println("d = " + d);
644        //System.out.println("cb = " + cb);
645        //System.out.println("e = " + e);
646        assertEquals("ca = c*a: ", ca, d);
647        assertEquals("cb = c*b: ", cb, e);
648
649        // non commutative right
650        //System.out.println("left: ");
651        d = a.multiply(c);
652        e = b.multiply(c);
653        //System.out.println("d = " + d);
654        //System.out.println("e = " + e);
655
656        gco = fd.rightGcdCofactors(dfac, d, e);
657        //System.out.println("right gco[0] = " + gco[0]);
658        //System.out.println("gco[1] = " + gco[1]);
659        //System.out.println("gco[2] = " + gco[2]);
660
661        GenSolvablePolynomial<BigRational> ac, bc;
662        ac = gco[1].multiply(gco[0]);
663        bc = gco[2].multiply(gco[0]);
664        //System.out.println("ac = " + ac);
665        //System.out.println("d = " + d);
666        //System.out.println("bc = " + bc);
667        //System.out.println("e = " + e);
668        assertEquals("ac = a*c: ", ac, d);
669        assertEquals("bc = b*c: ", bc, e);
670    }
671
672}