001/* 002 * $Id$ 003 */ 004 005package edu.jas.ufd; 006 007 008import java.util.ArrayList; 009import java.util.List; 010 011import edu.jas.arith.BigRational; 012import edu.jas.poly.ExpVector; 013import edu.jas.poly.GenPolynomial; 014import edu.jas.poly.GenPolynomialRing; 015import edu.jas.poly.PolyUtil; 016import edu.jas.poly.TermOrder; 017 018import junit.framework.Test; 019import junit.framework.TestCase; 020import junit.framework.TestSuite; 021 022 023/** 024 * GCD Subres with rational coefficients algorithm tests with JUnit. 025 * @author Heinz Kredel 026 */ 027public class GCDSubresRatTest 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>GCDSubresRatTest</CODE> object. 040 * @param name String. 041 */ 042 public GCDSubresRatTest(String name) { 043 super(name); 044 } 045 046 047 /** 048 */ 049 public static Test suite() { 050 TestSuite suite = new TestSuite(GCDSubresRatTest.class); 051 return suite; 052 } 053 054 055 GreatestCommonDivisorSubres<BigRational> ufd; 056 057 058 TermOrder to = new TermOrder(TermOrder.INVLEX); 059 060 061 GenPolynomialRing<BigRational> dfac; 062 063 064 GenPolynomialRing<BigRational> cfac; 065 066 067 GenPolynomialRing<GenPolynomial<BigRational>> rfac; 068 069 070 BigRational mi; 071 072 073 BigRational ai, bi, ci, di, ei; 074 075 076 GenPolynomial<BigRational> a, b, c, d, e; 077 078 079 GenPolynomial<GenPolynomial<BigRational>> ar, br, cr, dr, er; 080 081 082 int rl = 3; 083 084 085 int kl = 2; 086 087 088 int ll = 3; 089 090 091 int el = 3; 092 093 094 float q = 0.25f; 095 096 097 @Override 098 protected void setUp() { 099 a = b = c = d = e = null; 100 ai = bi = ci = di = ei = null; 101 ar = br = cr = dr = er = null; 102 mi = new BigRational(1); 103 ufd = new GreatestCommonDivisorSubres<BigRational>(); 104 String[] vars = ExpVector.STDVARS(rl); 105 String[] cvars = ExpVector.STDVARS(rl - 1); 106 String[] rvars = new String[] { vars[rl - 1] }; 107 dfac = new GenPolynomialRing<BigRational>(mi, rl, to, vars); 108 cfac = new GenPolynomialRing<BigRational>(mi, rl - 1, to, cvars); 109 rfac = new GenPolynomialRing<GenPolynomial<BigRational>>(cfac, 1, to, rvars); 110 //System.out.println("mi = " + mi); 111 } 112 113 114 @Override 115 protected void tearDown() { 116 a = b = c = d = e = null; 117 ai = bi = ci = di = ei = null; 118 ar = br = cr = dr = er = null; 119 mi = null; 120 ufd = null; 121 dfac = null; 122 cfac = null; 123 rfac = null; 124 } 125 126 127 /** 128 * Test gcd. 129 */ 130 public void testGcd() { 131 for (int i = 0; i < 1; i++) { 132 a = dfac.random(kl * (i + 2), ll + 2 * i, el + 0 * i, q); 133 b = dfac.random(kl * (i + 2), ll + 2 * i, el + 0 * i, q); 134 c = dfac.random(kl * (i + 2), ll + 2 * i, el + 0 * i, q); 135 c = c.multiply(dfac.univariate(0)); 136 //a = ufd.basePrimitivePart(a); 137 //b = ufd.basePrimitivePart(b); 138 139 if (a.isZERO() || b.isZERO() || c.isZERO()) { 140 // skip for this turn 141 continue; 142 } 143 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 144 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 145 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 146 147 a = a.multiply(c); 148 b = b.multiply(c); 149 //System.out.println("a = " + a); 150 //System.out.println("b = " + b); 151 152 d = ufd.gcd(a, b); 153 154 c = ufd.basePrimitivePart(c).abs(); 155 e = PolyUtil.<BigRational> baseSparsePseudoRemainder(d, c); 156 //System.out.println("c = " + c); 157 //System.out.println("d = " + d); 158 assertTrue("c | gcd(ac,bc) " + e, e.isZERO()); 159 160 e = PolyUtil.<BigRational> baseSparsePseudoRemainder(a, d); 161 //System.out.println("e = " + e); 162 assertTrue("gcd(a,b) | a" + e, e.isZERO()); 163 164 e = PolyUtil.<BigRational> baseSparsePseudoRemainder(b, d); 165 //System.out.println("e = " + e); 166 assertTrue("gcd(a,b) | b" + e, e.isZERO()); 167 } 168 } 169 170 171 /** 172 * Test base quotioent and remainder. 173 */ 174 public void testBaseQR() { 175 dfac = new GenPolynomialRing<BigRational>(mi, 1, to); 176 177 for (int i = 0; i < 3; i++) { 178 a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q); 179 c = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q); 180 //a = ufd.basePrimitivePart(a).abs(); 181 //c = ufd.basePrimitivePart(c); 182 do { 183 ci = mi.random(kl * (i + 2)); 184 ci = ci.sum(mi.getONE()); 185 } while (ci.isZERO()); 186 187 //System.out.println("a = " + a); 188 //System.out.println("c = " + c); 189 //System.out.println("ci = " + ci); 190 191 if (a.isZERO() || c.isZERO()) { 192 // skip for this turn 193 continue; 194 } 195 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 196 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 197 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 198 199 b = a.multiply(c); 200 //System.out.println("b = " + b); 201 d = PolyUtil.<BigRational> baseSparsePseudoRemainder(b, c); 202 //System.out.println("d = " + d); 203 204 assertTrue("rem(ac,c) == 0", d.isZERO()); 205 206 b = a.multiply(ci); 207 //System.out.println("b = " + b); 208 d = b.divide(ci); 209 //System.out.println("d = " + d); 210 211 assertEquals("a == ac/c", a, d); 212 213 b = a.multiply(c); 214 //System.out.println("b = " + b); 215 d = PolyUtil.<BigRational> basePseudoDivide(b, c); 216 //System.out.println("d = " + d); 217 218 assertEquals("a == ac/c", a, d); 219 } 220 } 221 222 223 /** 224 * Test base content and primitive part. 225 */ 226 public void testBaseContentPP() { 227 for (int i = 0; i < 9; i++) { 228 c = dfac.random(kl * (i + 2), ll + 2 * i, el + i, q); 229 c = c.multiply(mi.random(kl * (i + 2))); 230 231 if (c.isZERO()) { 232 // skip for this turn 233 continue; 234 } 235 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 236 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 237 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 238 239 ci = ufd.baseContent(c); 240 d = ufd.basePrimitivePart(c); 241 //System.out.println("c = " + c); 242 //System.out.println("ci = " + ci); 243 //System.out.println("d = " + d); 244 245 a = d.multiply(ci); 246 assertEquals("c == cont(c)pp(c)", c, a); 247 } 248 } 249 250 251 public void testDiscriminant() { 252 dfac = new GenPolynomialRing<BigRational>(mi, 1, to); 253 for (int i = 0; i < 5; i++) { 254 c = dfac.random(kl * (i + 1), ll + 2 * i, el + i, q * 2); 255 //System.out.println("c = " + c); 256 if (c.isZERO()) { 257 // skip for this turn 258 continue; 259 } 260 c = c.multiply(c); 261 d = ufd.baseDiscriminant(c); 262 //System.out.println("d = " + d); 263 264 assertTrue("disc(c^2) == 0", d.isZERO()); 265 } 266 } 267 268 269 /** 270 * Test base gcd. 271 */ 272 public void testBaseGcd() { 273 dfac = new GenPolynomialRing<BigRational>(mi, 1, to); 274 275 for (int i = 0; i < 3; i++) { 276 a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q); 277 b = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q); 278 c = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q); 279 //a = ufd.basePrimitivePart(a); 280 //b = ufd.basePrimitivePart(b); 281 //c = ufd.basePrimitivePart(c).abs(); 282 283 //System.out.println("a = " + a); 284 //System.out.println("b = " + b); 285 //System.out.println("c = " + c); 286 287 if (a.isZERO() || b.isZERO() || c.isZERO()) { 288 // skip for this turn 289 continue; 290 } 291 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 292 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 293 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 294 295 a = a.multiply(c); 296 b = b.multiply(c); 297 298 d = ufd.baseGcd(a, b); 299 e = PolyUtil.<BigRational> baseSparsePseudoRemainder(d, c); 300 //System.out.println("d = " + d); 301 302 assertTrue("c | gcd(ac,bc) " + e, e.isZERO()); 303 } 304 } 305 306 307 /** 308 * Test recursive quotioent and remainder. 309 */ 310 public void testRecursiveQR() { 311 dfac = new GenPolynomialRing<BigRational>(mi, 2, to); 312 cfac = new GenPolynomialRing<BigRational>(mi, 2 - 1, to); 313 rfac = new GenPolynomialRing<GenPolynomial<BigRational>>(cfac, 1, to); 314 315 for (int i = 0; i < 3; i++) { 316 a = dfac.random(kl * (i + 1), ll + i, el + i, q); 317 a = ufd.basePrimitivePart(a).abs(); 318 319 c = dfac.random(kl * (i + 1), ll + i, el + i, q); 320 c = ufd.basePrimitivePart(a).abs(); 321 cr = PolyUtil.<BigRational> recursive(rfac, c); 322 323 c = cfac.random(kl * (i + 1), ll + 2 * i, el + 2 * i, q); 324 c = ufd.basePrimitivePart(c).abs(); 325 326 ar = PolyUtil.<BigRational> recursive(rfac, a); 327 //System.out.println("ar = " + ar); 328 //System.out.println("a = " + a); 329 //System.out.println("c = " + c); 330 //System.out.println("cr = " + cr); 331 332 if (cr.isZERO() || c.isZERO()) { 333 // skip for this turn 334 continue; 335 } 336 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0); 337 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 338 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 339 340 341 br = ar.multiply(cr); 342 //System.out.println("br = " + br); 343 dr = PolyUtil.<BigRational> recursiveSparsePseudoRemainder(br, cr); 344 //System.out.println("dr = " + dr); 345 d = PolyUtil.<BigRational> distribute(dfac, dr); 346 //System.out.println("d = " + d); 347 348 assertTrue("rem(ac,c) == 0", d.isZERO()); 349 350 br = ar.multiply(c); 351 //System.out.println("br = " + br); 352 dr = PolyUtil.<BigRational> recursiveDivide(br, c); 353 //System.out.println("dr = " + dr); 354 d = PolyUtil.<BigRational> distribute(dfac, dr); 355 //System.out.println("d = " + d); 356 357 assertEquals("a == ac/c", a, d); 358 } 359 } 360 361 362 /** 363 * Test recursive content and primitive part. 364 */ 365 public void testRecursiveContentPP() { 366 dfac = new GenPolynomialRing<BigRational>(mi, 2, to); 367 cfac = new GenPolynomialRing<BigRational>(mi, 2 - 1, to); 368 rfac = new GenPolynomialRing<GenPolynomial<BigRational>>(cfac, 1, to); 369 370 for (int i = 0; i < 3; i++) { 371 cr = rfac.random(kl * (i + 2), ll + 2 * i, el + i, q); 372 //System.out.println("cr = " + cr); 373 374 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0); 375 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 376 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 377 378 c = ufd.recursiveContent(cr); 379 dr = ufd.recursivePrimitivePart(cr); 380 //System.out.println("c = " + c); 381 //System.out.println("dr = " + dr); 382 383 ar = dr.multiply(c); 384 assertEquals("c == cont(c)pp(c)", cr, ar); 385 } 386 } 387 388 389 /** 390 * Test recursive gcd. 391 */ 392 public void testRecursiveGCD() { 393 dfac = new GenPolynomialRing<BigRational>(mi, 2, to); 394 cfac = new GenPolynomialRing<BigRational>(mi, 2 - 1, to); 395 rfac = new GenPolynomialRing<GenPolynomial<BigRational>>(cfac, 1, to); 396 397 for (int i = 0; i < 2; i++) { 398 ar = rfac.random(kl, ll, el + i, q); 399 br = rfac.random(kl, ll, el, q); 400 cr = rfac.random(kl, ll, el, q); 401 //System.out.println("ar = " + ar); 402 //System.out.println("br = " + br); 403 //System.out.println("cr = " + cr); 404 405 if (ar.isZERO() || br.isZERO() || cr.isZERO()) { 406 // skip for this turn 407 continue; 408 } 409 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0); 410 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 411 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 412 413 ar = ar.multiply(cr); 414 br = br.multiply(cr); 415 //System.out.println("ar = " + ar); 416 //System.out.println("br = " + br); 417 418 dr = ufd.recursiveUnivariateGcd(ar, br); 419 //System.out.println("dr = " + dr); 420 421 er = PolyUtil.<BigRational> recursiveSparsePseudoRemainder(dr, cr); 422 //System.out.println("er = " + er); 423 424 assertTrue("c | gcd(ac,bc) " + er, er.isZERO()); 425 } 426 } 427 428 429 /** 430 * Test arbitrary recursive gcd. 431 */ 432 public void testArbitraryRecursiveGCD() { 433 dfac = new GenPolynomialRing<BigRational>(mi, 2, to); 434 cfac = new GenPolynomialRing<BigRational>(mi, 2 - 1, to); 435 rfac = new GenPolynomialRing<GenPolynomial<BigRational>>(cfac, 1, to); 436 437 for (int i = 0; i < 2; i++) { 438 ar = rfac.random(kl, ll, el + i, q); 439 br = rfac.random(kl, ll, el, q); 440 cr = rfac.random(kl, ll, el, q); 441 //System.out.println("ar = " + ar); 442 //System.out.println("br = " + br); 443 //System.out.println("cr = " + cr); 444 445 if (ar.isZERO() || br.isZERO() || cr.isZERO()) { 446 // skip for this turn 447 continue; 448 } 449 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0); 450 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 451 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 452 453 ar = ar.multiply(cr); 454 br = br.multiply(cr); 455 //System.out.println("ar = " + ar); 456 //System.out.println("br = " + br); 457 458 dr = ufd.recursiveGcd(ar, br); 459 //System.out.println("dr = " + dr); 460 461 er = PolyUtil.<BigRational> recursiveSparsePseudoRemainder(dr, cr); 462 //System.out.println("er = " + er); 463 464 assertTrue("c | gcd(ac,bc) " + er, er.isZERO()); 465 } 466 } 467 468 469 /** 470 * Test content and primitive part. 471 */ 472 public void testContentPP() { 473 dfac = new GenPolynomialRing<BigRational>(mi, 3, to); 474 475 for (int i = 0; i < 3; i++) { 476 c = dfac.random(kl * (i + 2), ll + 2 * i, el + i, q); 477 //System.out.println("cr = " + cr); 478 479 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 480 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 481 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 482 483 a = ufd.content(c); 484 e = a.extend(dfac, 0, 0L); 485 b = ufd.primitivePart(c); 486 //System.out.println("c = " + c); 487 //System.out.println("a = " + a); 488 //System.out.println("e = " + e); 489 //System.out.println("b = " + b); 490 491 d = e.multiply(b); 492 assertEquals("c == cont(c)pp(c)", d, c); 493 } 494 } 495 496 497 /** 498 * Test gcd 3 variables. 499 */ 500 public void testGCD3() { 501 dfac = new GenPolynomialRing<BigRational>(mi, 3, to); 502 503 for (int i = 0; i < 3; i++) { 504 a = dfac.random(kl, ll, el + i, q); 505 b = dfac.random(kl, ll, el, q); 506 c = dfac.random(kl, ll, el, q); 507 //System.out.println("a = " + a); 508 //System.out.println("b = " + b); 509 //System.out.println("c = " + c); 510 511 if (a.isZERO() || b.isZERO() || c.isZERO()) { 512 // skip for this turn 513 continue; 514 } 515 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 516 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 517 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 518 519 a = a.multiply(c); 520 b = b.multiply(c); 521 //System.out.println("a = " + a); 522 //System.out.println("b = " + b); 523 524 d = ufd.gcd(a, b); 525 //System.out.println("d = " + d); 526 527 e = PolyUtil.<BigRational> baseSparsePseudoRemainder(d, c); 528 //System.out.println("e = " + e); 529 530 assertTrue("c | gcd(ac,bc) " + e, e.isZERO()); 531 } 532 } 533 534 535 /** 536 * Test gcd. 537 */ 538 public void testGCD() { 539 // dfac = new GenPolynomialRing<BigRational>(mi,3,to); 540 541 for (int i = 0; i < 1; i++) { 542 a = dfac.random(kl, ll, el, q); 543 b = dfac.random(kl, ll, el, q); 544 c = dfac.random(kl, ll, el, q); 545 //System.out.println("a = " + a); 546 //System.out.println("b = " + b); 547 //System.out.println("c = " + c); 548 549 if (a.isZERO() || b.isZERO() || c.isZERO()) { 550 // skip for this turn 551 continue; 552 } 553 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 554 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 555 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 556 557 a = a.multiply(c); 558 b = b.multiply(c); 559 //System.out.println("a = " + a); 560 //System.out.println("b = " + b); 561 562 d = ufd.gcd(a, b); 563 //System.out.println("d = " + d); 564 565 e = PolyUtil.<BigRational> baseSparsePseudoRemainder(d, c); 566 //System.out.println("e = " + e); 567 assertTrue("c | gcd(ac,bc) " + e, e.isZERO()); 568 569 e = PolyUtil.<BigRational> baseSparsePseudoRemainder(a, d); 570 //System.out.println("e = " + e); 571 assertTrue("gcd(a,b) | a " + e, e.isZERO()); 572 573 e = PolyUtil.<BigRational> baseSparsePseudoRemainder(b, d); 574 //System.out.println("e = " + e); 575 assertTrue("gcd(a,b) | b " + e, e.isZERO()); 576 } 577 } 578 579 580 /** 581 * Test lcm. 582 */ 583 public void testLCM() { 584 dfac = new GenPolynomialRing<BigRational>(mi, 3, to); 585 586 for (int i = 0; i < 1; i++) { 587 a = dfac.random(kl, ll, el, q); 588 b = dfac.random(kl, ll, el, q); 589 c = dfac.random(kl, 3, 2, q); 590 //System.out.println("a = " + a); 591 //System.out.println("b = " + b); 592 //System.out.println("c = " + c); 593 594 if (a.isZERO() || b.isZERO() || c.isZERO()) { 595 // skip for this turn 596 continue; 597 } 598 assertTrue("length( a" + i + " ) <> 0", a.length() > 0); 599 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 600 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 601 602 a = a.multiply(c); 603 b = b.multiply(c); 604 605 c = ufd.gcd(a, b); 606 //System.out.println("c = " + c); 607 608 d = ufd.lcm(a, b); 609 //System.out.println("d = " + d); 610 611 e = c.multiply(d); 612 //System.out.println("e = " + e); 613 c = a.multiply(b); 614 //System.out.println("c = " + c); 615 616 assertEquals("ab == gcd(a,b)lcm(ab)", c, e); 617 } 618 } 619 620 621 /** 622 * Test co-prime factors. 623 */ 624 public void testCoPrime() { 625 dfac = new GenPolynomialRing<BigRational>(mi, 3, to); 626 627 a = dfac.random(kl, 3, 2, q); 628 b = dfac.random(kl, 3, 2, q); 629 c = dfac.random(kl, 3, 2, q); 630 //System.out.println("a = " + a); 631 //System.out.println("b = " + b); 632 //System.out.println("c = " + c); 633 634 if (a.isZERO() || b.isZERO() || c.isZERO()) { 635 // skip for this turn 636 return; 637 } 638 assertTrue("length( a ) <> 0", a.length() > 0); 639 640 d = a.multiply(a).multiply(b).multiply(b).multiply(b).multiply(c); 641 e = a.multiply(b).multiply(c); 642 //System.out.println("d = " + d); 643 //System.out.println("c = " + c); 644 645 List<GenPolynomial<BigRational>> F = new ArrayList<GenPolynomial<BigRational>>(5); 646 F.add(d); 647 F.add(a); 648 F.add(b); 649 F.add(c); 650 F.add(e); 651 652 653 List<GenPolynomial<BigRational>> P = ufd.coPrime(F); 654 //System.out.println("F = " + F); 655 //System.out.println("P = " + P); 656 657 assertTrue("is co-prime ", ufd.isCoPrime(P)); 658 assertTrue("is co-prime of ", ufd.isCoPrime(P, F)); 659 660 661 //P = ufd.coPrimeSquarefree(F); 662 //System.out.println("F = " + F); 663 //System.out.println("P = " + P); 664 //assertTrue("is co-prime ", ufd.isCoPrime(P) ); 665 //assertTrue("is co-prime of ", ufd.isCoPrime(P,F) ); 666 667 668 P = ufd.coPrimeRec(F); 669 //System.out.println("F = " + F); 670 //System.out.println("P = " + P); 671 672 assertTrue("is co-prime ", ufd.isCoPrime(P)); 673 assertTrue("is co-prime of ", ufd.isCoPrime(P, F)); 674 } 675 676}