001/* 002 * $Id: GCDSimpleTest.java 4831 2014-06-21 21:26:23Z axelclk $ 003 */ 004 005package edu.jas.ufd; 006 007 008//import java.util.Map; 009 010import junit.framework.Test; 011import junit.framework.TestCase; 012import junit.framework.TestSuite; 013 014import org.apache.log4j.BasicConfigurator; 015 016import edu.jas.arith.BigInteger; 017import edu.jas.poly.GenPolynomial; 018import edu.jas.poly.GenPolynomialRing; 019import edu.jas.poly.PolyUtil; 020import edu.jas.poly.TermOrder; 021 022 023/** 024 * GCD Simple PRS algorithm tests with JUnit. 025 * @author Heinz Kredel. 026 */ 027 028public class GCDSimpleTest extends TestCase { 029 030 031 /** 032 * main. 033 */ 034 public static void main(String[] args) { 035 BasicConfigurator.configure(); 036 junit.textui.TestRunner.run(suite()); 037 } 038 039 040 /** 041 * Constructs a <CODE>GCDSimpleTest</CODE> object. 042 * @param name String. 043 */ 044 public GCDSimpleTest(String name) { 045 super(name); 046 } 047 048 049 /** 050 */ 051 public static Test suite() { 052 TestSuite suite = new TestSuite(GCDSimpleTest.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; 073 074 075 BigInteger bi; 076 077 078 BigInteger ci; 079 080 081 BigInteger di; 082 083 084 BigInteger ei; 085 086 087 GenPolynomial<BigInteger> a; 088 089 090 GenPolynomial<BigInteger> b; 091 092 093 GenPolynomial<BigInteger> c; 094 095 096 GenPolynomial<BigInteger> d; 097 098 099 GenPolynomial<BigInteger> e; 100 101 102 GenPolynomial<GenPolynomial<BigInteger>> ar; 103 104 105 GenPolynomial<GenPolynomial<BigInteger>> br; 106 107 108 GenPolynomial<GenPolynomial<BigInteger>> cr; 109 110 111 GenPolynomial<GenPolynomial<BigInteger>> dr; 112 113 114 GenPolynomial<GenPolynomial<BigInteger>> er; 115 116 117 int rl = 5; 118 119 120 int kl = 4; 121 122 123 int ll = 5; 124 125 126 int el = 3; 127 128 129 float q = 0.3f; 130 131 132 @Override 133 protected void setUp() { 134 a = b = c = d = e = null; 135 ai = bi = ci = di = ei = null; 136 ar = br = cr = dr = er = null; 137 ufd = new GreatestCommonDivisorSimple<BigInteger>(); 138 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl, to); 139 cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl - 1, to); 140 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to); 141 } 142 143 144 @Override 145 protected void tearDown() { 146 a = b = c = d = e = null; 147 ai = bi = ci = di = ei = null; 148 ar = br = cr = dr = er = null; 149 ufd = null; 150 dfac = null; 151 cfac = null; 152 rfac = null; 153 } 154 155 156 /** 157 * Test base gcd simple. 158 */ 159 public void testBaseGcdSimple() { 160 161 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 1, to); 162 163 for (int i = 0; i < 5; i++) { 164 a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q); 165 b = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q); 166 c = dfac.random(kl * (i + 2), ll + 2, el + 2, q); 167 c = c.multiply(dfac.univariate(0)); 168 if (c.isZERO()) { 169 // skip for this turn 170 continue; 171 } 172 //a = ufd.basePrimitivePart(a); 173 //b = ufd.basePrimitivePart(b); 174 c = ufd.basePrimitivePart(c).abs(); 175 176 //System.out.println("a = " + a); 177 //System.out.println("b = " + b); 178 //System.out.println("c = " + c); 179 180 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 181 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 182 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 183 184 a = a.multiply(c); 185 b = b.multiply(c); 186 187 d = ufd.baseGcd(a, b); 188 e = PolyUtil.<BigInteger> basePseudoRemainder(d, c); 189 //System.out.println("d = " + d); 190 //System.out.println("c = " + c); 191 assertTrue("c | gcd(ac,bc) " + e, e.isZERO()); 192 193 e = PolyUtil.<BigInteger> basePseudoRemainder(a, d); 194 //System.out.println("e = " + e); 195 assertTrue("gcd(a,b) | a" + e, e.isZERO()); 196 197 e = PolyUtil.<BigInteger> basePseudoRemainder(b, d); 198 //System.out.println("e = " + e); 199 assertTrue("gcd(a,b) | b" + e, e.isZERO()); 200 } 201 } 202 203 204 /** 205 * Test recursive gcd simple. 206 */ 207 public void testRecursiveGCDSimple() { 208 209 di = new BigInteger(1); 210 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2, to); 211 cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2 - 1, to); 212 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to); 213 214 //kl = 3; ll = 2; 215 216 for (int i = 0; i < 3; i++) { 217 ar = rfac.random(kl, ll, el + i, q); 218 br = rfac.random(kl, ll, el, q); 219 cr = rfac.random(kl, ll, el, q); 220 cr = ufd.recursivePrimitivePart(cr).abs(); 221 //System.out.println("ar = " + ar); 222 //System.out.println("br = " + br); 223 //System.out.println("cr = " + cr); 224 225 if (ar.isZERO() || br.isZERO() || cr.isZERO()) { 226 // skip for this turn 227 continue; 228 } 229 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0); 230 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 231 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 232 233 ar = ar.multiply(cr); 234 br = br.multiply(cr); 235 //System.out.println("ar = " + ar); 236 //System.out.println("br = " + br); 237 238 dr = ufd.recursiveUnivariateGcd(ar, br); 239 //System.out.println("cr = " + cr); 240 //System.out.println("dr = " + dr); 241 242 er = PolyUtil.<BigInteger> recursivePseudoRemainder(dr, cr); 243 //System.out.println("er = " + er); 244 assertTrue("c | gcd(ac,bc) " + er, er.isZERO()); 245 246 er = PolyUtil.<BigInteger> recursivePseudoRemainder(ar, dr); 247 //System.out.println("er = " + er); 248 assertTrue("gcd(a,b) | a" + er, er.isZERO()); 249 250 er = PolyUtil.<BigInteger> recursivePseudoRemainder(br, dr); 251 //System.out.println("er = " + er); 252 assertTrue("gcd(a,b) | b" + er, er.isZERO()); 253 } 254 } 255 256 257 /** 258 * Test arbitrary recursive gcd simple. 259 */ 260 public void testArbitraryRecursiveGCDSimple() { 261 262 di = new BigInteger(1); 263 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2, to); 264 cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2 - 1, to); 265 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to); 266 267 //kl = 3; ll = 2; 268 269 for (int i = 0; i < 3; i++) { 270 ar = rfac.random(kl, ll, el + i, q); 271 br = rfac.random(kl, ll, el, q); 272 cr = rfac.random(kl, ll, el, q); 273 cr = ufd.recursivePrimitivePart(cr).abs(); 274 //System.out.println("ar = " + ar); 275 //System.out.println("br = " + br); 276 //System.out.println("cr = " + cr); 277 278 if (ar.isZERO() || br.isZERO() || cr.isZERO()) { 279 // skip for this turn 280 continue; 281 } 282 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0); 283 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 284 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 285 286 ar = ar.multiply(cr); 287 br = br.multiply(cr); 288 //System.out.println("ar = " + ar); 289 //System.out.println("br = " + br); 290 291 dr = ufd.recursiveGcd(ar, br); 292 //System.out.println("cr = " + cr); 293 //System.out.println("dr = " + dr); 294 295 er = PolyUtil.<BigInteger> recursivePseudoRemainder(dr, cr); 296 //System.out.println("er = " + er); 297 assertTrue("c | gcd(ac,bc) " + er, er.isZERO()); 298 299 er = PolyUtil.<BigInteger> recursivePseudoRemainder(ar, dr); 300 //System.out.println("er = " + er); 301 assertTrue("gcd(a,b) | a" + er, er.isZERO()); 302 303 er = PolyUtil.<BigInteger> recursivePseudoRemainder(br, dr); 304 //System.out.println("er = " + er); 305 assertTrue("gcd(a,b) | b" + er, er.isZERO()); 306 } 307 } 308 309 310 /** 311 * Test gcd simple. 312 */ 313 public void testGCDSimple() { 314 315 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 4, to); 316 317 for (int i = 0; i < 2; i++) { 318 a = dfac.random(kl, ll, el, q); 319 b = dfac.random(kl, ll, el, q); 320 c = dfac.random(kl, ll, el, q); 321 c = c.multiply(dfac.univariate(0)); 322 c = ufd.primitivePart(c).abs(); 323 //System.out.println("a = " + a); 324 //System.out.println("b = " + b); 325 //System.out.println("c = " + c); 326 327 if (a.isZERO() || b.isZERO() || c.isZERO()) { 328 // skip for this turn 329 continue; 330 } 331 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 332 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 333 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 334 335 a = a.multiply(c); 336 b = b.multiply(c); 337 //System.out.println("a = " + a); 338 //System.out.println("b = " + b); 339 //System.out.println("c = " + c); 340 341 d = ufd.gcd(a, b); 342 //System.out.println("c = " + c); 343 //System.out.println("d = " + d); 344 345 e = PolyUtil.<BigInteger> basePseudoRemainder(d, c); 346 //System.out.println("e = " + e); 347 assertTrue("c | gcd(ac,bc) " + e, e.isZERO()); 348 349 e = PolyUtil.<BigInteger> basePseudoRemainder(a, d); 350 //System.out.println("e = " + e); 351 assertTrue("gcd(a,b) | a " + e, e.isZERO()); 352 353 e = PolyUtil.<BigInteger> basePseudoRemainder(b, d); 354 //System.out.println("e = " + e); 355 assertTrue("gcd(a,b) | b " + e, e.isZERO()); 356 } 357 } 358 359 360 /** 361 * Test base resultant integral coefficients. 362 */ 363 public void testBaseResultant() { 364 365 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 1, to); 366 367 GreatestCommonDivisorSimple<BigInteger> ufds = new GreatestCommonDivisorSimple<BigInteger>(); 368 GreatestCommonDivisorSubres<BigInteger> sres = new GreatestCommonDivisorSubres<BigInteger>(); 369 370 for (int i = 0; i < 1; i++) { 371 a = dfac.random(kl, ll, el + 3 + i, q); 372 b = dfac.random(kl, ll, el + 3 + i, q); 373 c = dfac.random(kl, ll, el + 3 + i, q); 374 //System.out.println("a = " + a); 375 //System.out.println("b = " + b); 376 //System.out.println("c = " + c); 377 378 if (a.isZERO() || b.isZERO() || c.isZERO()) { 379 // skip for this turn 380 continue; 381 } 382 if (c.isConstant()) { 383 c = dfac.univariate(0,1); 384 } 385 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 386 387 d = ufds.baseResultant(a, b); 388 //System.out.println("d = " + d); 389 e = sres.baseResultant(a, b); 390 //System.out.println("e = " + e); 391 assertEquals("d == e: " + d.subtract(e), d.abs().signum(), e.abs().signum() ); 392 //assertEquals("d == e: " + d.subtract(e), d, e); 393 394 GenPolynomial<BigInteger> ac = a.multiply(c); 395 GenPolynomial<BigInteger> bc = b.multiply(c); 396 //System.out.println("ac = " + ac); 397 //System.out.println("bc = " + bc); 398 399 d = ufds.baseResultant(ac, bc); 400 //System.out.println("d = " + d); 401 assertTrue("d == 0: " + d, d.isZERO()); 402 403 e = sres.baseResultant(ac, bc); 404 //System.out.println("e = " + e); 405 assertTrue("e == 0: " + e, e.isZERO()); 406 } 407 } 408 409 410 /** 411 * Test recursive resultant simple. 412 */ 413 public void testRecursiveResultantSimple() { 414 415 di = new BigInteger(1); 416 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2, to); 417 cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2 - 1, to); 418 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to); 419 420 GreatestCommonDivisorSimple<BigInteger> ufds = new GreatestCommonDivisorSimple<BigInteger>(); 421 GreatestCommonDivisorSubres<BigInteger> sres = new GreatestCommonDivisorSubres<BigInteger>(); 422 423 //kl = 3; ll = 2; 424 425 for (int i = 0; i < 1; i++) { 426 ar = rfac.random(kl, ll, el + i, q); 427 br = rfac.random(kl, ll, el, q); 428 cr = rfac.random(kl, ll, el, q); 429 cr = ufd.recursivePrimitivePart(cr).abs(); 430 //System.out.println("ar = " + ar); 431 //System.out.println("br = " + br); 432 433 if (ar.isZERO() || br.isZERO() || cr.isZERO()) { 434 // skip for this turn 435 continue; 436 } 437 if (cr.isConstant()) { 438 cr = rfac.univariate(0,1); 439 } 440 //System.out.println("cr = " + cr); 441 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0); 442 443 dr = ufds.recursiveUnivariateResultant(ar, br); 444 //System.out.println("dr = " + dr); 445 er = sres.recursiveUnivariateResultant(ar, br); 446 //System.out.println("er = " + er); 447 assertEquals("dr == er: " + dr.subtract(er), dr.abs().signum(), er.abs().signum()); 448 //assertEquals("dr == er: " + dr.subtract(er), dr, er); 449 450 GenPolynomial<GenPolynomial<BigInteger>> arc = ar.multiply(cr); 451 GenPolynomial<GenPolynomial<BigInteger>> brc = br.multiply(cr); 452 //System.out.println("ar = " + ar); 453 //System.out.println("br = " + br); 454 455 dr = ufds.recursiveUnivariateResultant(arc, brc); 456 //System.out.println("dr = " + dr); 457 //assertTrue("dr == 0: " + dr, dr.isZERO()); 458 459 er = sres.recursiveUnivariateResultant(arc, brc); 460 //System.out.println("er = " + er); 461 //assertTrue("er == 0: " + er, er.isZERO()); 462 463 assertEquals("dr == er: " + dr.subtract(er), dr.signum(), er.signum()); 464 } 465 } 466 467}