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