001/* 002 * $Id$ 003 */ 004 005package edu.jas.ufd; 006 007 008import edu.jas.arith.BigInteger; 009import edu.jas.arith.ModInteger; 010import edu.jas.poly.ExpVector; 011import edu.jas.poly.GenPolynomial; 012import edu.jas.poly.GenPolynomialRing; 013import edu.jas.poly.PolyUtil; 014import edu.jas.poly.TermOrder; 015 016import junit.framework.Test; 017import junit.framework.TestCase; 018import junit.framework.TestSuite; 019 020 021/** 022 * GCD Subresultant PRS algorithm tests with JUnit. 023 * @author Heinz Kredel 024 */ 025 026public class GCDSubresTest extends TestCase { 027 028 029 /** 030 * main. 031 */ 032 public static void main(String[] args) { 033 junit.textui.TestRunner.run(suite()); 034 } 035 036 037 /** 038 * Constructs a <CODE>GCDSubresTest</CODE> object. 039 * @param name String. 040 */ 041 public GCDSubresTest(String name) { 042 super(name); 043 } 044 045 046 /** 047 */ 048 public static Test suite() { 049 TestSuite suite = new TestSuite(GCDSubresTest.class); 050 return suite; 051 } 052 053 054 GreatestCommonDivisorAbstract<BigInteger> ufd; 055 056 057 TermOrder to = new TermOrder(TermOrder.INVLEX); 058 059 060 GenPolynomialRing<BigInteger> dfac; 061 062 063 GenPolynomialRing<BigInteger> cfac; 064 065 066 GenPolynomialRing<GenPolynomial<BigInteger>> rfac; 067 068 069 BigInteger ai, bi, ci, di, ei; 070 071 072 GenPolynomial<BigInteger> a, b, c, d, e; 073 074 075 GenPolynomial<GenPolynomial<BigInteger>> ar, br, cr, dr, er; 076 077 078 int rl = 5; 079 080 081 int kl = 4; 082 083 084 int ll = 5; 085 086 087 int el = 3; 088 089 090 float q = 0.3f; 091 092 093 @Override 094 protected void setUp() { 095 a = b = c = d = e = null; 096 ai = bi = ci = di = ei = null; 097 ar = br = cr = dr = er = null; 098 ufd = new GreatestCommonDivisorPrimitive<BigInteger>(); 099 String[] vars = ExpVector.STDVARS(rl); 100 String[] cvars = ExpVector.STDVARS(rl - 1); 101 String[] rvars = new String[] { vars[rl - 1] }; 102 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl, to, vars); 103 cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl - 1, to, cvars); 104 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to, rvars); 105 } 106 107 108 @Override 109 protected void tearDown() { 110 a = b = c = d = e = null; 111 ai = bi = ci = di = ei = null; 112 ar = br = cr = dr = er = null; 113 ufd = null; 114 dfac = null; 115 cfac = null; 116 rfac = null; 117 } 118 119 120 /** 121 * Test base gcd subresultant. 122 */ 123 public void testBaseGcdSubres() { 124 ufd = new GreatestCommonDivisorSubres<BigInteger>(); 125 126 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 1, to); 127 128 for (int i = 0; i < 1; i++) { 129 a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q); 130 b = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q); 131 c = dfac.random(kl * (i + 2), ll + 2, el + 2, q); 132 c = c.multiply(dfac.univariate(0)); 133 if (c.isZERO()) { 134 // skip for this turn 135 continue; 136 } 137 //a = ufd.basePrimitivePart(a); 138 //b = ufd.basePrimitivePart(b); 139 c = ufd.basePrimitivePart(c).abs(); 140 141 //System.out.println("a = " + a); 142 //System.out.println("b = " + b); 143 //System.out.println("c = " + c); 144 145 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 146 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 147 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 148 149 a = a.multiply(c); 150 b = b.multiply(c); 151 152 d = ufd.baseGcd(a, b); 153 e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(d, c); 154 //System.out.println("d = " + d); 155 //System.out.println("c = " + c); 156 assertTrue("c | gcd(ac,bc) " + e, e.isZERO()); 157 158 e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(a, d); 159 //System.out.println("e = " + e); 160 assertTrue("gcd(a,b) | a" + e, e.isZERO()); 161 162 e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(b, d); 163 //System.out.println("e = " + e); 164 assertTrue("gcd(a,b) | b" + e, e.isZERO()); 165 } 166 } 167 168 169 /** 170 * Test recursive gcd subresultant. 171 */ 172 public void testRecursiveGCDsubres() { 173 ufd = new GreatestCommonDivisorSubres<BigInteger>(); 174 175 di = new BigInteger(1); 176 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2, to); 177 cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2 - 1, to); 178 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to); 179 180 for (int i = 0; i < 5; i++) { 181 ar = rfac.random(kl, ll, el + i, q); 182 br = rfac.random(kl, ll, el, q); 183 cr = rfac.random(kl, ll, el, q); 184 cr = ufd.recursivePrimitivePart(cr).abs(); 185 //System.out.println("ar = " + ar); 186 //System.out.println("br = " + br); 187 //System.out.println("cr = " + cr); 188 189 if (ar.isZERO() || br.isZERO() || cr.isZERO()) { 190 // skip for this turn 191 continue; 192 } 193 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0); 194 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 195 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 196 197 ar = ar.multiply(cr); 198 br = br.multiply(cr); 199 //System.out.println("ar = " + ar); 200 //System.out.println("br = " + br); 201 //System.out.println("cr = " + cr); 202 203 dr = ufd.recursiveUnivariateGcd(ar, br); 204 //System.out.println("dr = " + dr); 205 206 er = PolyUtil.<BigInteger> recursiveSparsePseudoRemainder(dr, cr); 207 //System.out.println("er = " + er); 208 assertTrue("c | gcd(ac,bc) " + er, er.isZERO()); 209 210 er = PolyUtil.<BigInteger> recursiveSparsePseudoRemainder(ar, dr); 211 //System.out.println("er = " + er); 212 assertTrue("gcd(a,b) | a" + er, er.isZERO()); 213 214 er = PolyUtil.<BigInteger> recursiveSparsePseudoRemainder(br, dr); 215 //System.out.println("er = " + er); 216 assertTrue("gcd(a,b) | b" + er, er.isZERO()); 217 } 218 } 219 220 221 /** 222 * Test arbitrary recursive gcd subresultant. 223 */ 224 public void testArbitraryRecursiveGCDsubres() { 225 ufd = new GreatestCommonDivisorSubres<BigInteger>(); 226 227 di = new BigInteger(1); 228 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2, to); 229 cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2 - 1, to); 230 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to); 231 232 for (int i = 0; i < 5; i++) { 233 ar = rfac.random(kl, ll, el + i, q); 234 br = rfac.random(kl, ll, el, q); 235 cr = rfac.random(kl, ll, el, q); 236 cr = ufd.recursivePrimitivePart(cr).abs(); 237 //System.out.println("ar = " + ar); 238 //System.out.println("br = " + br); 239 //System.out.println("cr = " + cr); 240 241 if (ar.isZERO() || br.isZERO() || cr.isZERO()) { 242 // skip for this turn 243 continue; 244 } 245 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0); 246 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 247 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 248 249 ar = ar.multiply(cr); 250 br = br.multiply(cr); 251 //System.out.println("ar = " + ar); 252 //System.out.println("br = " + br); 253 //System.out.println("cr = " + cr); 254 255 dr = ufd.recursiveGcd(ar, br); 256 //System.out.println("dr = " + dr); 257 258 er = PolyUtil.<BigInteger> recursiveSparsePseudoRemainder(dr, cr); 259 //System.out.println("er = " + er); 260 assertTrue("c | gcd(ac,bc) " + er, er.isZERO()); 261 262 er = PolyUtil.<BigInteger> recursiveSparsePseudoRemainder(ar, dr); 263 //System.out.println("er = " + er); 264 assertTrue("gcd(a,b) | a" + er, er.isZERO()); 265 266 er = PolyUtil.<BigInteger> recursiveSparsePseudoRemainder(br, dr); 267 //System.out.println("er = " + er); 268 assertTrue("gcd(a,b) | b" + er, er.isZERO()); 269 } 270 } 271 272 273 /** 274 * Test gcd subresultant. 275 */ 276 public void testGCDsubres() { 277 //GreatestCommonDivisorAbstract<BigInteger> ufd_pp; 278 //ufd_pp = ufd; 279 280 ufd = new GreatestCommonDivisorSubres<BigInteger>(); 281 282 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 5, to); 283 284 for (int i = 0; i < 2; i++) { 285 a = dfac.random(kl, ll, el, q); 286 b = dfac.random(kl, ll, el, q); 287 c = dfac.random(kl, ll, el, q); 288 c = c.multiply(dfac.univariate(0)); 289 c = ufd.primitivePart(c).abs(); 290 //System.out.println("a = " + a); 291 //System.out.println("b = " + b); 292 //System.out.println("c = " + c); 293 294 if (a.isZERO() || b.isZERO() || c.isZERO()) { 295 // skip for this turn 296 continue; 297 } 298 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 299 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 300 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 301 302 a = a.multiply(c); 303 b = b.multiply(c); 304 //System.out.println("a = " + a); 305 //System.out.println("b = " + b); 306 //System.out.println("c = " + c); 307 308 d = ufd.gcd(a, b); 309 //System.out.println("c = " + c); 310 //System.out.println("d = " + d); 311 312 e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(d, c); 313 //System.out.println("e = " + e); 314 assertTrue("c | gcd(ac,bc) " + e, e.isZERO()); 315 316 e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(a, d); 317 //System.out.println("e = " + e); 318 assertTrue("gcd(a,b) | a " + e, e.isZERO()); 319 320 e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(b, d); 321 //System.out.println("e = " + e); 322 assertTrue("gcd(a,b) | b " + e, e.isZERO()); 323 } 324 } 325 326 327 /** 328 * Test base subresultant. 329 */ 330 public void testBaseSubresultant() { 331 GreatestCommonDivisorSubres<BigInteger> ufd = new GreatestCommonDivisorSubres<BigInteger>(); 332 333 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 1, to); 334 335 for (int i = 0; i < 1; i++) { 336 a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q); 337 b = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q); 338 c = dfac.random(kl, ll, 2, q); 339 //c = c.multiply( cfac.univariate(0) ); 340 //c = dfac.getONE(); 341 if (c.isZERO()) { 342 // skip for this turn 343 continue; 344 } 345 //System.out.println("a = " + a); 346 //System.out.println("b = " + b); 347 //System.out.println("c = " + c); 348 349 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 350 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 351 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 352 353 a = a.multiply(c); 354 b = b.multiply(c); 355 356 d = ufd.baseResultant(a, b); 357 e = ufd.baseGcd(a, b); 358 //System.out.println("d = " + d); 359 //System.out.println("c = " + c); 360 //System.out.println("e = " + e); 361 if (!e.isConstant()) { 362 assertTrue("res(a,b) == 0 " + d, d.isZERO()); 363 } else { 364 assertTrue("res(a,b) != 0 " + d, !d.isZERO()); 365 } 366 } 367 } 368 369 370 /** 371 * Test recursive subresultant. 372 */ 373 public void testRecursiveSubresultant() { 374 GreatestCommonDivisorSubres<BigInteger> ufd = new GreatestCommonDivisorSubres<BigInteger>(); 375 376 di = new BigInteger(1); 377 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2, to); 378 cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2 - 1, to); 379 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to); 380 381 for (int i = 0; i < 5; i++) { 382 ar = rfac.random(kl, ll, el + i, q); 383 br = rfac.random(kl, ll, el, q); 384 cr = rfac.random(kl, ll, 2, q); 385 //cr = rfac.getONE(); 386 //cr = ufd.recursivePrimitivePart(cr).abs(); 387 //cr = cr.multiply( rfac.univariate(0) ); 388 //System.out.println("ar = " + ar); 389 //System.out.println("br = " + br); 390 //System.out.println("cr = " + cr); 391 392 if (ar.isZERO() || br.isZERO() || cr.isZERO()) { 393 // skip for this turn 394 continue; 395 } 396 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0); 397 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 398 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 399 400 ar = ar.multiply(cr); 401 br = br.multiply(cr); 402 //System.out.println("ar = " + ar); 403 //System.out.println("br = " + br); 404 405 dr = ufd.recursiveUnivariateResultant(ar, br); 406 //System.out.println("cr = " + cr); 407 //System.out.println("dr = " + dr); 408 er = ufd.recursiveUnivariateGcd(ar, br); 409 //System.out.println("er = " + er); 410 411 if (er.isZERO()) { // cannot happen since a, b, c != 0 412 assertTrue("res(a,b) = 0 " + dr + " e = " + er, dr.isZERO()); 413 } 414 if (er.isConstant() && er.leadingBaseCoefficient().isConstant()) { 415 assertTrue("res(a,b) != 0 " + dr + ", e = " + er + ", a = " + ar + ", b = " + br, 416 !dr.isZERO()); 417 } else { 418 assertTrue("res(a,b) = 0 or not const " + dr + ", e = " + er + ", a = " + ar + ", b = " + br, 419 dr.isZERO() || !dr.isConstant() || !dr.leadingBaseCoefficient().isConstant()); 420 } 421 422 } 423 } 424 425 426 /** 427 * Test subresultant. 428 */ 429 public void testSubres() { 430 GreatestCommonDivisorSubres<BigInteger> ufd = new GreatestCommonDivisorSubres<BigInteger>(); 431 432 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 3, to); 433 434 for (int i = 0; i < 2; i++) { 435 a = dfac.random(kl, ll, el, q); 436 b = dfac.random(kl, ll, el, q); 437 c = dfac.random(kl, ll, 2, q); 438 //c = dfac.getONE(); 439 //c = c.multiply( dfac.univariate(0) ); 440 //c = ufd.primitivePart(c).abs(); 441 //System.out.println("a = " + a); 442 //System.out.println("b = " + b); 443 //System.out.println("c = " + c); 444 445 if (a.isZERO() || b.isZERO() || c.isZERO()) { 446 // skip for this turn 447 continue; 448 } 449 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 450 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 451 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 452 453 a = a.multiply(c); 454 b = b.multiply(c); 455 //System.out.println("a = " + a); 456 //System.out.println("b = " + b); 457 458 d = ufd.resultant(a, b); 459 e = ufd.gcd(a, b); 460 //System.out.println("c = " + c); 461 //System.out.println("d = " + d); 462 //System.out.println("e = " + e); 463 464 if (e.isZERO()) { // cannot happen since a, b, c != 0 465 assertTrue("res(a,b) = 0 " + d + " e = " + e, d.isZERO()); 466 } 467 if (e.isConstant()) { 468 assertTrue("res(a,b) != 0 " + d + ", e = " + e + ", a = " + a + ", b = " + b, !d.isZERO()); 469 } else { 470 assertTrue("res(a,b) = 0 or not const " + d + ", e = " + e + ", a = " + a + ", b = " + b, 471 d.isZERO() || !d.isConstant()); 472 } 473 } 474 } 475 476 477 /** 478 * Test and compare resultant. 479 */ 480 public void testResultant() { 481 GreatestCommonDivisorAbstract<BigInteger> ufdm = new GreatestCommonDivisorModular<ModInteger>(true); 482 GreatestCommonDivisorSubres<BigInteger> ufds = new GreatestCommonDivisorSubres<BigInteger>(); 483 484 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 3, to); 485 486 for (int i = 0; i < 1; i++) { 487 a = dfac.random(kl + (i + 1), ll, el, q); 488 b = dfac.random(kl + (i + 2), ll, el, q); 489 c = dfac.random(kl, ll, 2, q); 490 //c = dfac.getONE(); 491 //c = c.multiply( dfac.univariate(0) ); 492 //c = ufd.primitivePart(c).abs(); 493 //System.out.println("a = " + a); 494 //System.out.println("b = " + b); 495 496 if (a.isZERO() || b.isZERO() || c.isZERO()) { 497 // skip for this turn 498 continue; 499 } 500 if (c.isConstant()) { 501 c = dfac.univariate(0, 1); 502 } 503 //System.out.println("c = " + c); 504 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 505 506 d = ufdm.resultant(a, b); 507 //System.out.println("d = " + d); 508 e = ufds.resultant(a, b); 509 //System.out.println("e = " + e); 510 assertEquals("d == e: " + d.subtract(e), d.abs().signum(), e.abs().signum()); 511 //assertEquals("d == e: " + d.subtract(e), d, e); 512 513 GenPolynomial<BigInteger> ac = a.multiply(c); 514 GenPolynomial<BigInteger> bc = b.multiply(c); 515 //System.out.println("ac = " + ac); 516 //System.out.println("bc = " + bc); 517 518 d = ufdm.resultant(ac, bc); 519 //System.out.println("d = " + d); 520 //assertTrue("d == 0: " + d, d.isZERO()); 521 522 e = ufds.resultant(ac, bc); 523 //System.out.println("e = " + e); 524 //assertTrue("e == 0: " + e, e.isZERO()); 525 526 assertEquals("d == e: " + d.subtract(e), d.abs().signum(), e.abs().signum()); 527 } 528 } 529 530}