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