001 /*
002 * $Id: GCDPartFracRatTest.java 2845 2009-11-01 10:44:18Z kredel $
003 */
004
005 package edu.jas.ufd;
006
007
008 import java.util.ArrayList;
009 import java.util.List;
010 import java.util.SortedMap;
011 import java.util.TreeMap;
012
013 import junit.framework.Test;
014 import junit.framework.TestCase;
015 import junit.framework.TestSuite;
016
017 import edu.jas.arith.BigRational;
018 import edu.jas.poly.ExpVector;
019 import edu.jas.poly.GenPolynomial;
020 import edu.jas.poly.GenPolynomialRing;
021 import edu.jas.poly.PolyUtil;
022 import edu.jas.poly.TermOrder;
023
024
025 /**
026 * GCD partial fraction with rational coefficients algorithm tests with JUnit.
027 * @author Heinz Kredel.
028 */
029
030 public 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 }