001/* 002 * $Id$ 003 */ 004 005package edu.jas.fd; 006 007 008import java.util.List; 009import java.util.ArrayList; 010 011import edu.jas.arith.BigRational; 012import edu.jas.gb.SolvableGroebnerBaseAbstract; 013import edu.jas.gb.SolvableGroebnerBaseSeq; 014import edu.jas.kern.ComputerThreads; 015import edu.jas.poly.GenPolynomial; 016import edu.jas.poly.GenSolvablePolynomial; 017import edu.jas.poly.GenSolvablePolynomialRing; 018import edu.jas.poly.PolyUtil; 019import edu.jas.poly.PolynomialList; 020import edu.jas.poly.RecSolvablePolynomial; 021import edu.jas.poly.RecSolvablePolynomialRing; 022import edu.jas.poly.RelationGenerator; 023import edu.jas.poly.TermOrder; 024import edu.jas.poly.TermOrderByName; 025import edu.jas.poly.WeylRelationsIterated; 026 027import junit.framework.Test; 028import junit.framework.TestCase; 029import junit.framework.TestSuite; 030 031 032/** 033 * GCD Primitive PRS algorithm tests with JUnit. <b>Note:</b> not in sync with 034 * implementation. 035 * @author Heinz Kredel 036 */ 037 038public class GCDPrimitiveTest extends TestCase { 039 040 041 /** 042 * main. 043 */ 044 public static void main(String[] args) { 045 junit.textui.TestRunner.run(suite()); 046 ComputerThreads.terminate(); 047 } 048 049 050 /** 051 * Constructs a <CODE>GCDPrimitiveTest</CODE> object. 052 * @param name String. 053 */ 054 public GCDPrimitiveTest(String name) { 055 super(name); 056 } 057 058 059 /** 060 */ 061 public static Test suite() { 062 TestSuite suite = new TestSuite(GCDPrimitiveTest.class); 063 return suite; 064 } 065 066 067 GreatestCommonDivisorAbstract<BigRational> fd, fds; 068 069 070 TermOrder to = TermOrderByName.INVLEX; 071 072 073 GenSolvablePolynomialRing<BigRational> dfac; 074 075 076 //GenSolvablePolynomialRing<GenPolynomial<BigRational>> rfac; 077 RecSolvablePolynomialRing<BigRational> rfac; 078 079 080 GenSolvablePolynomial<BigRational> a, b, a0, b0, c, d, e, a1, b1; 081 082 083 GenSolvablePolynomial<GenPolynomial<BigRational>> ar, br, ar0, br0, cr, dr, er, sr; 084 085 086 int rl = 4; 087 088 089 int kl = 2; 090 091 092 int ll = 2; 093 094 095 int el = 3; 096 097 098 float q = 0.25f; 099 100 101 @Override 102 protected void setUp() { 103 a = b = c = d = e = null; 104 ar = br = cr = dr = er = null; 105 String[] vars = new String[] { "a", "b", "c", "d" }; 106 BigRational cf = new BigRational(1); 107 fd = new GreatestCommonDivisorPrimitive<BigRational>(cf); 108 fds = new GreatestCommonDivisorSimple<BigRational>(cf); 109 dfac = new GenSolvablePolynomialRing<BigRational>(cf, to, vars); 110 RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>(); 111 dfac.addRelations(wl); 112 rfac = (RecSolvablePolynomialRing<BigRational>) dfac.recursive(1); 113 } 114 115 116 @Override 117 protected void tearDown() { 118 a = b = c = d = e = null; 119 ar = br = cr = dr = er = null; 120 fd = null; 121 dfac = null; 122 rfac = null; 123 } 124 125 126 /** 127 * Test base gcd primitive. 128 */ 129 public void testBaseGcdPrimitive() { 130 String[] uvars = new String[] { "x" }; 131 dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, uvars); 132 133 for (int i = 0; i < 3; i++) { 134 a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q); 135 b = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q); 136 c = dfac.random(kl * (i + 2), ll + 2, el + 2, q); 137 c = c.multiply(dfac.univariate(0)); 138 if (c.isZERO()) { 139 // skip for this turn 140 continue; 141 } 142 //a = fd.leftBasePrimitivePart(a); 143 //b = fd.leftBasePrimitivePart(b); 144 c = (GenSolvablePolynomial<BigRational>) fd.leftBasePrimitivePart(c).abs(); 145 146 //System.out.println("a = " + a); 147 //System.out.println("b = " + b); 148 //System.out.println("c = " + c); 149 //assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 150 151 a = a.multiply(c); 152 b = b.multiply(c); 153 154 d = fd.leftBaseGcd(a, b); 155 e = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> baseSparsePseudoRemainder(d, c); 156 //System.out.println("d = " + d); 157 //System.out.println("c = " + c); 158 assertTrue("c | gcd(ac,bc): " + e, e.isZERO()); 159 160 e = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> baseSparsePseudoRemainder(a, d); 161 //System.out.println("e = " + e); 162 assertTrue("gcd(a,b) | a: " + e, e.isZERO()); 163 164 e = (GenSolvablePolynomial<BigRational>) 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 univariate recursive left gcd primitive. 173 */ 174 @SuppressWarnings("cast") 175 public void testRecursiveLeftGCDPrimitive() { 176 //String[] vars = new String[] { "a", "b", "c", "d" }; 177 String[] vars = new String[] { "a", "b" }; 178 dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, vars); 179 RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>(); 180 dfac.addRelations(wl); 181 //System.out.println("dfac = " + dfac.toScript()); 182 rfac = (RecSolvablePolynomialRing<BigRational>) dfac.recursive(1); 183 //System.out.println("rfac = " + rfac.toScript()); 184 185 RecSolvablePolynomialRing<BigRational> rrfacTemp = rfac; 186 GenSolvablePolynomialRing<GenPolynomial<BigRational>> rrfac = rfac; 187 188 GenSolvablePolynomialRing<BigRational> rcfac = (GenSolvablePolynomialRing<BigRational>) rfac.coFac; 189 SolvableQuotientRing<BigRational> qfac = new SolvableQuotientRing<BigRational>(rcfac); 190 QuotSolvablePolynomialRing<BigRational> rqfac = new QuotSolvablePolynomialRing<BigRational>(qfac, 191 rrfac); 192 List<GenSolvablePolynomial<GenPolynomial<BigRational>>> rl = rrfacTemp.coeffTable.relationList(); 193 List<GenPolynomial<GenPolynomial<BigRational>>> rlc = PolynomialList 194 .<GenPolynomial<BigRational>> castToList(rl); 195 rqfac.polCoeff.coeffTable.addRelations(rlc); 196 //System.out.println("rrfac = " + rrfac.toScript()); 197 //System.out.println("rcfac = " + rcfac.toScript()); 198 //System.out.println("qfac = " + qfac.toScript()); 199 //System.out.println("rqfac = " + rqfac.toScript()); 200 201 //kl = 3; ll = 4; // 202 el = 2; 203 204 ar = rfac.random(kl, ll, el + 1, q); 205 br = rfac.random(kl, ll, el, q); 206 cr = rfac.random(kl, ll, el, q); 207 //cr = (RecSolvablePolynomial<BigRational>) cr.abs(); 208 cr = (RecSolvablePolynomial<BigRational>) PolyUtil.<BigRational> monic(cr); 209 //cr = (RecSolvablePolynomial<BigRational>) fd.recursivePrimitivePart(cr).abs(); 210 //cr = rfac.getONE(); 211 //cr = rfac.parse("a+b+c+d"); 212 213 //ar = rfac.parse("1/3 b^3 - 1/6"); 214 //ar = rfac.parse("1/3 b^2 - 1/6"); 215 //br = rfac.parse("( -1/2 ) b + 3 a"); 216 //nok: cr = rfac.parse("b * a - 5 b"); 217 //cr = rfac.parse("a - 5"); 218 219 //System.out.println("ar = " + ar); 220 //System.out.println("br = " + br); 221 //System.out.println("cr = " + cr); 222 223 if (br.isZERO() || cr.isZERO()) { 224 br = rfac.parse("( -1/2 ) b + 3 a"); 225 cr = rfac.parse("a * b - 5 b"); 226 } 227 228 //ar = cr.multiply(ar); 229 //br = cr.multiply(br); 230 ar = ar.multiply(cr); 231 br = br.multiply(cr); 232 //System.out.println("ar = " + ar); 233 //System.out.println("br = " + br); 234 //if (true) return; 235 236 long ts = System.currentTimeMillis(); 237 //sr = rfac.getONE(); 238 sr = fds.leftRecursiveUnivariateGcd(ar, br); 239 ts = System.currentTimeMillis() - ts; 240 //System.out.println("cr = " + cr); 241 242 long tp = System.currentTimeMillis(); 243 dr = fd.leftRecursiveUnivariateGcd(ar, br); 244 tp = System.currentTimeMillis() - tp; 245 //System.out.println("cr = " + cr); 246 //System.out.println("dr = " + dr); 247 //System.out.println("sr = " + sr); 248 //System.out.println("time: ts = " + ts + ", tp = " + tp); 249 assertTrue("time: ts = " + ts + ", tp = " + tp, ts + tp >= 0); 250 251 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(dr, cr); 252 //System.out.println("er = " + er); 253 assertTrue("c | gcd(ac,bc): " + er, er.isZERO()); 254 255 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(ar, dr); 256 //System.out.println("er = " + er); 257 assertTrue("gcd(ac,bc) | ac: " + er, er.isZERO()); 258 259 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(br, dr); 260 //System.out.println("er = " + er); 261 assertTrue("gcd(ac,bc) | bc: " + er, er.isZERO()); 262 263 GenSolvablePolynomial<SolvableQuotient<BigRational>> ap, bp, dp, gp, ep; // cp, apm, bpm, cpm, dpm, gpm; 264 ap = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, ar); 265 bp = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, br); 266 //cp = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, cr); 267 dp = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, dr); 268 //apm = ap.monic(); 269 //bpm = bp.monic(); 270 //cpm = cp.monic(); 271 //dpm = dp.monic(); 272 //System.out.println("ap = " + ap); 273 //System.out.println("apm = " + apm); 274 //System.out.println("bp = " + bp); 275 //System.out.println("bpm = " + bpm); 276 //System.out.println("cp = " + cp); 277 //System.out.println("cpm = " + cpm); 278 //System.out.println("dp = " + dp); 279 //System.out.println("dpm = " + dpm); 280 281 GreatestCommonDivisorAbstract<SolvableQuotient<BigRational>> fdq = new GreatestCommonDivisorPrimitive<SolvableQuotient<BigRational>>( 282 qfac); 283 gp = fdq.leftBaseGcd(ap, bp); 284 //gpm = gp.monic(); 285 //System.out.println("gp = " + gp); 286 //System.out.println("gpm = " + gpm); 287 288 ep = FDUtil.<SolvableQuotient<BigRational>> leftBaseSparsePseudoRemainder(gp, dp); 289 //System.out.println("ep = " + ep); 290 assertTrue("c | gcd(ac,bc): " + ep, ep.isZERO()); 291 292 ep = FDUtil.<SolvableQuotient<BigRational>> leftBaseSparsePseudoRemainder(ap, gp); 293 //System.out.println("ep = " + ep); 294 assertTrue("gcd(ac,bc)| ac): " + ep, ep.isZERO()); 295 296 ep = FDUtil.<SolvableQuotient<BigRational>> leftBaseSparsePseudoRemainder(bp, gp); 297 //System.out.println("ep = " + ep); 298 assertTrue("gcd(ac,bc)| bc): " + ep, ep.isZERO()); 299 } 300 301 302 /** 303 * Test univariate recursive right gcd primitive. 304 */ 305 @SuppressWarnings("cast") 306 public void testRecursiveRightGCDPrimitive() { 307 //String[] vars = new String[] { "a", "b", "c", "d" }; 308 String[] vars = new String[] { "a", "b" }; 309 dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, vars); 310 RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>(); 311 dfac.addRelations(wl); 312 //System.out.println("dfac = " + dfac.toScript()); 313 rfac = (RecSolvablePolynomialRing<BigRational>) dfac.recursive(1); 314 //System.out.println("rfac = " + rfac.toScript()); 315 316 RecSolvablePolynomialRing<BigRational> rrfacTemp = rfac; 317 GenSolvablePolynomialRing<GenPolynomial<BigRational>> rrfac = rfac; 318 319 GenSolvablePolynomialRing<BigRational> rcfac = (GenSolvablePolynomialRing<BigRational>) rfac.coFac; 320 SolvableQuotientRing<BigRational> qfac = new SolvableQuotientRing<BigRational>(rcfac); 321 QuotSolvablePolynomialRing<BigRational> rqfac = new QuotSolvablePolynomialRing<BigRational>(qfac, 322 rrfac); 323 List<GenSolvablePolynomial<GenPolynomial<BigRational>>> rl = rrfacTemp.coeffTable.relationList(); 324 List<GenPolynomial<GenPolynomial<BigRational>>> rlc = PolynomialList 325 .<GenPolynomial<BigRational>> castToList(rl); 326 rqfac.polCoeff.coeffTable.addRelations(rlc); 327 //System.out.println("rrfac = " + rrfac.toScript()); 328 //System.out.println("rcfac = " + rcfac.toScript()); 329 //System.out.println("qfac = " + qfac.toScript()); 330 //System.out.println("rqfac = " + rqfac.toScript()); 331 332 //kl = 3; ll = 4; // 333 el = 3; 334 335 ar = rfac.random(kl, ll, el + 1, q); 336 br = rfac.random(kl, ll, el, q); 337 cr = rfac.random(kl, ll, el, q); 338 //cr = (RecSolvablePolynomial<BigRational>) cr.abs(); 339 cr = (RecSolvablePolynomial<BigRational>) PolyUtil.<BigRational> monic(cr); 340 //cr = (RecSolvablePolynomial<BigRational>) fd.recursivePrimitivePart(cr).abs(); 341 //cr = rfac.getONE(); 342 //cr = rfac.parse("a+b+c+d"); 343 344 //ar = rfac.parse("1/3 b^3 - 1/6"); 345 //ar = rfac.parse("1/3 b^2 - 1/6"); 346 //br = rfac.parse("( -1/2 ) b + 3 a"); 347 //nok: cr = rfac.parse("b * a - 5 b"); 348 //cr = rfac.parse("a - 5"); 349 350 //ar = rfac.parse("359/95 a b^2 + 275/124 a"); 351 //br = rfac.parse("814/189 b + 135/44 a"); 352 //cr = rfac.parse("b - 612/25"); 353 354 //System.out.println("ar = " + ar); 355 //System.out.println("br = " + br); 356 //System.out.println("cr = " + cr); 357 358 if (br.isZERO() || cr.isZERO()) { 359 br = rfac.parse("( -1/2 ) b + 3 a"); 360 cr = rfac.parse("a * b - 5 b"); 361 } 362 363 ar = cr.multiply(ar); 364 br = cr.multiply(br); 365 //System.out.println("ar = " + ar); 366 //System.out.println("br = " + br); 367 368 // todo: 369 if (!rfac.getONE().isZERO()) return; 370 long ts = System.currentTimeMillis(); 371 //sr = rfac.getONE(); 372 sr = fds.rightRecursiveUnivariateGcd(ar, br); 373 ts = System.currentTimeMillis() - ts; 374 //System.out.println("cr = " + cr); 375 376 long tp = System.currentTimeMillis(); 377 dr = fd.rightRecursiveUnivariateGcd(ar, br); 378 tp = System.currentTimeMillis() - tp; 379 //System.out.println("cr = " + cr); 380 //System.out.println("dr = " + dr); 381 //System.out.println("sr = " + sr); 382 //System.out.println("time: ts = " + ts + ", tp = " + tp); 383 assertTrue("time: ts = " + ts + ", tp = " + tp, ts + tp >= 0); 384 385 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(dr, 386 cr); 387 //System.out.println("er = " + er); 388 assertTrue("c | gcd(ca,cb): " + er, er.isZERO()); 389 390 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(ar, 391 dr); 392 //System.out.println("er = " + er); 393 assertTrue("gcd(ca,cb) | ca: " + er, er.isZERO()); 394 395 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(br, 396 dr); 397 //System.out.println("er = " + er); 398 assertTrue("gcd(ca,cb) | cb: " + er, er.isZERO()); 399 } 400 401 402 /** 403 * Test arbitrary recursive gcd primitive. 404 */ 405 @SuppressWarnings("cast") 406 public void testArbitraryRecursiveGCDPrimitive() { 407 String[] cvars = new String[] { "a", "b" }; 408 String[] vars = new String[] { "c" }; 409 dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, cvars); 410 RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>(); 411 dfac.addRelations(wl); 412 //System.out.println("dfac = " + dfac.toScript()); 413 rfac = new RecSolvablePolynomialRing<BigRational>(dfac, to, vars); 414 //rfac = (RecSolvablePolynomialRing<BigRational>) dfac.recursive(1); 415 //System.out.println("rfac = " + rfac.toScript()); 416 417 //kl = 3; ll = 2; 418 el = 2; 419 420 ar0 = rfac.random(kl, ll, el + 1, q); 421 br0 = rfac.random(kl, ll, el, q); 422 cr = rfac.random(kl, ll, el, q); 423 424 //ar0 = rfac.parse("a + b c^2 "); 425 //br0 = rfac.parse("( a^2 - 1/3 ) c - 1/4"); 426 //cr = rfac.parse("(b - 1/2 a^2) c"); 427 428 //cr = (RecSolvablePolynomial<BigRational>) fd.recursivePrimitivePart(cr).abs(); 429 cr = (RecSolvablePolynomial<BigRational>) cr.monic(); 430 if (cr.isZERO()) { 431 cr = rfac.getONE(); 432 } 433 434 //System.out.println("ar = " + ar); 435 //System.out.println("br = " + br); 436 //System.out.println("cr = " + cr); 437 438 // left gcd 439 ar = ar0.multiply(cr); 440 br = br0.multiply(cr); 441 //System.out.println("ar = " + ar); 442 //System.out.println("br = " + br); 443 444 dr = fd.leftRecursiveGcd(ar, br); 445 //System.out.println("cr = " + cr); 446 //System.out.println("dr = " + dr); 447 448 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(dr, cr); 449 //System.out.println("er = " + er); 450 assertTrue("c | gcd(ac,bc): " + er, er.isZERO()); 451 452 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(ar, dr); 453 //System.out.println("er = " + er); 454 assertTrue("gcd(ac,bc) | ac: " + er, er.isZERO()); 455 456 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(br, dr); 457 //System.out.println("er = " + er); 458 assertTrue("gcd(ac,bc) | bc: " + er, er.isZERO()); 459 460 //todo: 461 if (er.isZERO()) return; 462 // right gcd 463 ar = cr.multiply(ar0); 464 br = cr.multiply(br0); 465 //System.out.println("ar = " + ar); 466 //System.out.println("br = " + br); 467 468 dr = fd.rightRecursiveGcd(ar, br); 469 //System.out.println("cr = " + cr); 470 //System.out.println("dr = " + dr); 471 472 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(dr, 473 cr); 474 //System.out.println("er = " + er); 475 assertTrue("c | gcd(ca,cb) " + er, er.isZERO()); 476 477 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(ar, 478 dr); 479 //System.out.println("er = " + er); 480 assertTrue("gcd(ca,cb) | ca " + er, er.isZERO()); 481 482 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(br, 483 dr); 484 //System.out.println("er = " + er); 485 assertTrue("gcd(ca,cb) | cb " + er, er.isZERO()); 486 } 487 488 489 /** 490 * Test full gcd primitive. 491 */ 492 public void testGCDPrimitive() { 493 String[] vars = new String[] { "a", "b", "c", "d" }; 494 //String[] vars = new String[] { "a", "b" }; 495 dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, vars); 496 RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>(); 497 dfac.addRelations(wl); 498 //System.out.println("dfac = " + dfac.toScript()); 499 500 //kl = 3; 501 ll = 4; 502 el = 4; 503 504 //a = dfac.random(kl, ll, el, q); 505 //b = dfac.random(kl, ll, el, q); 506 //c = dfac.random(kl, ll, el, q); 507 //c = c.multiply(dfac.univariate(0)); 508 509 a = dfac.parse("1/3 b^3 - 1/6 + d"); 510 b = dfac.parse("( -1/2 ) b + 3 a^2 + d"); 511 ////b = dfac.parse("( -1/2 ) b + 3 a^2 + c"); 512 ////c = dfac.parse("(a - 5 b) + c + d"); 513 ////ok: c = dfac.parse("(a - b) c"); 514 ////c = dfac.parse("c (a - b)"); 515 //c = dfac.parse("(a - b) + c + d "); 516 c = dfac.parse("(a - b) + c"); 517 //c = dfac.parse("(a - b) + b^3"); 518 //c = dfac.parse("(a - b) + d"); 519 520 //a = dfac.parse("2 b^3 * d^2 + 2/3 a + 3/2"); 521 //b = dfac.parse("2/3 d + 1/2 a^3 + 3/4"); 522 //c = dfac.parse("c^2 * d - 1/2 a^3 * d + 5/4 d"); 523 524 //c = (GenSolvablePolynomial<BigRational>) fd.primitivePart(c).abs(); 525 c = c.monic(); 526 if (c.isZERO()) { 527 c = dfac.getONE(); 528 } 529 //System.out.println("a = " + a); 530 //System.out.println("b = " + b); 531 //System.out.println("c = " + c); 532 533 // left 534 a0 = a; 535 b0 = b; 536 a = a0.multiply(c); 537 b = b0.multiply(c); 538 //System.out.println("a = " + a); 539 //System.out.println("b = " + b); 540 //System.out.println("c = " + c); 541 542 543 List<GenSolvablePolynomial<BigRational>> L = new ArrayList<GenSolvablePolynomial<BigRational>>(); 544 L.add(a); 545 L.add(b); 546 SolvableGroebnerBaseAbstract<BigRational> sbb = new SolvableGroebnerBaseSeq<BigRational>(); 547 548 // left 549 List<GenSolvablePolynomial<BigRational>> Llgb = sbb.leftGB(L); 550 //System.out.println("leftGB = " + Llgb); 551 //List<GenSolvablePolynomial<BigRational>> Ltgb = sbb.twosidedGB(L); 552 //System.out.println("twosidedGB = " + Ltgb); 553 554 // todo: 555 d = fd.leftGcd(a, b); 556 //System.out.println("gb = " + Llgb); 557 //System.out.println("c = " + c); 558 //System.out.println("d = " + d); 559 e = sbb.sred.leftNormalform(Llgb, d); 560 assertTrue("d in leftGB: " + Llgb + ", " + d, e.isZERO()||e.equals(d)); 561 562 //todo: e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(d, c); 563 //System.out.println("e = " + e); 564 //assertTrue("c | gcd(ac,bc): " + e, e.isZERO()); 565 566 e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(a, c); 567 //System.out.println("e = " + e); 568 assertTrue("c | ac: " + e, e.isZERO()); 569 e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(a, d); 570 //System.out.println("e = " + e); 571 assertTrue("gcd(a,b) | a: " + e, e.isZERO()); 572 573 e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(b, c); 574 //System.out.println("e = " + e); 575 assertTrue("c | bc: " + e, e.isZERO()); 576 e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(b, d); 577 //System.out.println("e = " + e); 578 assertTrue("gcd(a,b): | b " + e, e.isZERO()); 579 580 // todo: 581 if (e.isZERO()) return; 582 // right 583 a = c.multiply(a0); 584 b = c.multiply(b0); 585 //System.out.println("a = " + a); 586 //System.out.println("b = " + b); 587 //System.out.println("c = " + c); 588 589 //List<GenSolvablePolynomial<BigRational>> Lrgb = sbb.rightGB(L); // too long 590 //List<GenSolvablePolynomial<BigRational>> Ltgb = sbb.twosidedGB(L); 591 //System.out.println("twosidedGB = " + Ltgb); 592 593 d = fd.rightGcd(a, b); 594 //System.out.println("rightGB = " + Lrgb); 595 System.out.println("c = " + c); 596 System.out.println("d = " + d); 597 //assertTrue("d in rightGB", sbb.sred.rightNormalform(Lrgb, d).isZERO()); 598 599 e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(d, c); 600 //System.out.println("e = " + e); 601 assertTrue("c | gcd(ac,bc): " + e, e.isZERO()); 602 603 e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(a, c); 604 //System.out.println("e = " + e); 605 assertTrue("c | ac: " + e, e.isZERO()); 606 e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(b, c); 607 //System.out.println("e = " + e); 608 assertTrue("c | bc: " + e, e.isZERO()); 609 610 e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(a, d); 611 //System.out.println("e = " + e); 612 //e = FDUtil.<BigRational> divideRightPolynomial(a,d); 613 //System.out.println("e = " + e); 614 assertTrue("gcd(a,b) | a: " + e, e.isZERO()); 615 616 e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(b, d); 617 //System.out.println("e = " + e); 618 //e = FDUtil.<BigRational> divideRightPolynomial(b,d); 619 //System.out.println("e = " + e); 620 assertTrue("gcd(a,b) | b: " + e, e.isZERO()); 621 } 622 623 624 /** 625 * Test rational coefficients gcd polynomial cofactor tests. 626 */ 627 public void ztestRatCofactors() { 628 //System.out.println("dfac = " + dfac.toScript()); 629 do { 630 a = dfac.random(kl, ll, el, q); 631 } while (a.isZERO() || a.isConstant()); 632 do { 633 b = dfac.random(kl, ll, el, q / 2f); 634 } while (b.isZERO() || b.isConstant()); 635 do { 636 c = dfac.random(kl, ll, el, q / 2f); 637 } while (c.isZERO() || c.isConstant()); 638 c = c.monic(); 639 //System.out.println("a = " + a); 640 //System.out.println("b = " + b); 641 //System.out.println("c = " + c); 642 643 // non commutative left 644 //System.out.println("left: "); 645 d = c.multiply(a); 646 e = c.multiply(b); 647 //System.out.println("d = " + d); 648 //System.out.println("e = " + e); 649 650 GenSolvablePolynomial<BigRational>[] gco = fd.leftGcdCofactors(dfac, d, e); 651 //System.out.println("left gco[0] = " + gco[0]); 652 //System.out.println("gco[1] = " + gco[1]); 653 //System.out.println("gco[2] = " + gco[2]); 654 655 GenSolvablePolynomial<BigRational> ca, cb; 656 ca = gco[0].multiply(gco[1]); 657 cb = gco[0].multiply(gco[2]); 658 //System.out.println("ca = " + ca); 659 //System.out.println("d = " + d); 660 //System.out.println("cb = " + cb); 661 //System.out.println("e = " + e); 662 assertEquals("ca = c*a: ", ca, d); 663 assertEquals("cb = c*b: ", cb, e); 664 665 // non commutative right 666 //System.out.println("right: "); 667 d = a.multiply(c); 668 e = b.multiply(c); 669 //System.out.println("d = " + d); 670 //System.out.println("e = " + e); 671 672 gco = fd.rightGcdCofactors(dfac, d, e); 673 //System.out.println("right gco[0] = " + gco[0]); 674 //System.out.println("gco[1] = " + gco[1]); 675 //System.out.println("gco[2] = " + gco[2]); 676 677 GenSolvablePolynomial<BigRational> ac, bc; 678 ac = gco[1].multiply(gco[0]); 679 bc = gco[2].multiply(gco[0]); 680 //System.out.println("ac = " + ac); 681 //System.out.println("d = " + d); 682 //System.out.println("bc = " + bc); 683 //System.out.println("e = " + e); 684 assertEquals("ac = a*c: ", ac, d); 685 assertEquals("bc = b*c: ", bc, e); 686 } 687 688 689 /** 690 * Test co-prime factors. 691 */ 692 public void testCoPrime() { 693 String[] vs = new String[] { "a", "b" }; 694 dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, vs); 695 RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>(); 696 dfac.addRelations(wl); 697 //System.out.println("dfac = " + dfac.toScript()); 698 699 a = dfac.random(kl, 3, 2, q); 700 b = dfac.random(kl, 3, 2, q); 701 c = dfac.random(kl, 3, 2, q); 702 //System.out.println("a = " + a); 703 //System.out.println("b = " + b); 704 //System.out.println("c = " + c); 705 706 if (a.isZERO() || b.isZERO() || c.isZERO()) { 707 // skip for this turn 708 return; 709 } 710 assertTrue("length( a ) <> 0", a.length() > 0); 711 712 d = a.multiply(a).multiply(b).multiply(b).multiply(b).multiply(c); 713 e = a.multiply(b).multiply(c); 714 //System.out.println("d = " + d); 715 //System.out.println("e = " + e); 716 717 List<GenSolvablePolynomial<BigRational>> F = new ArrayList<GenSolvablePolynomial<BigRational>>(5); 718 F.add(d); 719 F.add(a); 720 F.add(b); 721 F.add(c); 722 F.add(e); 723 724 List<GenSolvablePolynomial<BigRational>> P = fd.leftCoPrime(F); 725 //System.out.println("F = " + F); 726 //System.out.println("P = " + P); 727 728 assertTrue("is co-prime ", fd.isLeftCoPrime(P)); 729 assertTrue("is co-prime of ", fd.isLeftCoPrime(P, F)); 730 731 P = fd.leftCoPrimeRec(F); 732 //System.out.println("F = " + F); 733 //System.out.println("P = " + P); 734 assertTrue("is co-prime ", fd.isLeftCoPrime(P)); 735 assertTrue("is co-prime of ", fd.isLeftCoPrime(P, F)); 736 } 737 738}