001/* 002 * $Id$ 003 */ 004 005package edu.jas.fd; 006 007 008import java.util.ArrayList; 009import java.util.List; 010 011 012import edu.jas.arith.BigRational; 013import edu.jas.gb.SolvableGroebnerBaseAbstract; 014import edu.jas.gb.SolvableGroebnerBaseSeq; 015import edu.jas.kern.ComputerThreads; 016import edu.jas.poly.GenPolynomial; 017import edu.jas.poly.GenSolvablePolynomial; 018import edu.jas.poly.GenSolvablePolynomialRing; 019import edu.jas.poly.PolyUtil; 020import edu.jas.poly.PolynomialList; 021import edu.jas.poly.RecSolvablePolynomial; 022import edu.jas.poly.RecSolvablePolynomialRing; 023import edu.jas.poly.RelationGenerator; 024import edu.jas.poly.TermOrder; 025import edu.jas.poly.TermOrderByName; 026import edu.jas.poly.WeylRelationsIterated; 027 028import junit.framework.Test; 029import junit.framework.TestCase; 030import junit.framework.TestSuite; 031 032 033/** 034 * GCD via syzygy tests with JUnit. 035 * @author Heinz Kredel 036 */ 037 038public class GCDSyzygyTest 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>GCDSyzygyTest</CODE> object. 052 * @param name String. 053 */ 054 public GCDSyzygyTest(String name) { 055 super(name); 056 } 057 058 059 /** 060 */ 061 public static Test suite() { 062 TestSuite suite = new TestSuite(GCDSyzygyTest.class); 063 return suite; 064 } 065 066 067 GreatestCommonDivisorAbstract<BigRational> fd; 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; 081 082 083 GenSolvablePolynomial<GenPolynomial<BigRational>> ar, br, cr, dr, er, ar0, br0; 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 GreatestCommonDivisorSimple<BigRational>(cf); 108 //fd = new GreatestCommonDivisorSyzygy<BigRational>(cf); //todo 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 //System.out.println("dfac = " + dfac); 114 } 115 116 117 @Override 118 protected void tearDown() { 119 a = b = c = d = e = null; 120 ar = br = cr = dr = er = null; 121 fd = null; 122 dfac = null; 123 rfac = null; 124 } 125 126 127 /** 128 * Test base gcd simple. 129 */ 130 public void testBaseGcdSimple() { 131 String[] uvars = new String[] { "x" }; 132 dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), 1, to, uvars); 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 + 1), ll + i, el + 2, q); 136 c = dfac.random(kl * (i + 1), ll + 1, el + 1, q); 137 c = c.multiply(dfac.univariate(0)); 138 if (c.isZERO()) { 139 // skip for this turn 140 continue; 141 } 142 //a = fd.basePrimitivePart(a); 143 //b = fd.basePrimitivePart(b); 144 //c = (GenSolvablePolynomial<BigRational>) fd.basePrimitivePart(c).abs(); 145 //System.out.println("a = " + a); 146 //System.out.println("b = " + b); 147 //System.out.println("c = " + c); 148 149 a = a.multiply(c); 150 b = b.multiply(c); 151 152 d = fd.leftBaseGcd(a, b); 153 e = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> 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 = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> baseSparsePseudoRemainder(a, d); 159 //System.out.println("e = " + e); 160 assertTrue("gcd(a,b) | a " + e, e.isZERO()); 161 162 e = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> 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 univariate recursive left gcd simple. 171 */ 172 @SuppressWarnings("cast") 173 public void testRecursiveLeftGCDSyzygy() { 174 String[] vars = new String[] { "a", "b" }; 175 dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, vars); 176 RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>(); 177 dfac.addRelations(wl); 178 //System.out.println("dfac = " + dfac.toScript()); 179 rfac = (RecSolvablePolynomialRing<BigRational>) dfac.recursive(1); 180 //System.out.println("rfac = " + rfac.toScript()); 181 182 RecSolvablePolynomialRing<BigRational> rrfacTemp = rfac; 183 GenSolvablePolynomialRing<GenPolynomial<BigRational>> rrfac = rfac; 184 185 GenSolvablePolynomialRing<BigRational> rcfac = (GenSolvablePolynomialRing<BigRational>) rfac.coFac; 186 SolvableQuotientRing<BigRational> qfac = new SolvableQuotientRing<BigRational>(rcfac); 187 QuotSolvablePolynomialRing<BigRational> rqfac = new QuotSolvablePolynomialRing<BigRational>(qfac, 188 rrfac); 189 List<GenSolvablePolynomial<GenPolynomial<BigRational>>> rl = rrfacTemp.coeffTable.relationList(); 190 List<GenPolynomial<GenPolynomial<BigRational>>> rlc = PolynomialList 191 .<GenPolynomial<BigRational>> castToList(rl); 192 rqfac.polCoeff.coeffTable.addRelations(rlc); 193 //System.out.println("rrfac = " + rrfac.toScript()); 194 //System.out.println("rcfac = " + rcfac.toScript()); 195 //System.out.println("qfac = " + qfac.toScript()); 196 //System.out.println("rqfac = " + rqfac.toScript()); 197 198 //kl = 3; 199 ll = 3; 200 el = 3; 201 202 ar = rfac.random(kl, ll, el + 1, q); 203 br = rfac.random(kl, ll, el, q); 204 cr = rfac.random(kl, ll, el, q); 205 ////cr = (RecSolvablePolynomial<BigRational>) cr.abs(); 206 cr = (RecSolvablePolynomial<BigRational>) PolyUtil.<BigRational> monic(cr); 207 //cr = (RecSolvablePolynomial<BigRational>) fd.recursivePrimitivePart(cr).abs(); 208 //cr = rfac.getONE(); 209 //cr = rfac.parse("a+b+c+d"); 210 211 //ar = rfac.parse("( ( -31/19 ) ) b^3 - ( 781/260 a - 641/372 )"); 212 //br = rfac.parse("( ( -1/5 ) a - 1/4 ) b^2 - 11/12 b - ( 47/17 a + 29/30 )"); 213 //cr = rfac.parse(" ( a + 9/8 ) b + ( 285/208 a + 191/280 )"); 214 215 //ar = rfac.parse("b^3 - ( a )"); 216 //br = rfac.parse("( a ) b^2 - 1/2 b"); 217 //cr = rfac.parse("b + ( a )"); 218 219 //ar = rfac.parse("( 2/23 a - 1/2 ) b^3 + 617/672 b^2 - ( 5 a + 307/154 )"); 220 //br = rfac.parse("( ( -673/330 ) ) b - ( 2/5 a - 566969/1651860 )"); 221 //cr = rfac.parse("( a - 2287945/213324 )"); 222 223 //ar = rfac.parse("( b^2 + 1/2 )"); 224 //br = rfac.parse("( a^2 b - ( a - 1/3 ) )"); 225 //cr = rfac.parse("( b + a - 1/5 )"); 226 227 //System.out.println("ar = " + ar); 228 //System.out.println("br = " + br); 229 //System.out.println("cr = " + cr); 230 231 if (cr.isZERO()) { 232 cr = rfac.getONE(); 233 } 234 //ar = cr.multiply(ar); 235 //br = cr.multiply(br); 236 ar = ar.multiply(cr); 237 br = br.multiply(cr); 238 //System.out.println("ar = " + ar); 239 //System.out.println("br = " + br); 240 241 dr = fd.leftRecursiveUnivariateGcd(ar, br); 242 //System.out.println("cr = " + cr); 243 //System.out.println("dr = " + dr); 244 245 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(dr, cr); 246 //System.out.println("er = " + er); 247 assertTrue("c | gcd(ac,bc) " + er, er.isZERO()); 248 249 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(ar, dr); 250 //System.out.println("er = " + er); 251 assertTrue("gcd(a,b) | a " + er, er.isZERO()); 252 253 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(br, dr); 254 //System.out.println("er = " + er); 255 assertTrue("gcd(a,b) | b " + er, er.isZERO()); 256 257 //if (true) return; 258 GenSolvablePolynomial<SolvableQuotient<BigRational>> ap, bp, cp, dp, gp, ep, apm, bpm, cpm, dpm, gpm; 259 ap = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, ar); 260 bp = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, br); 261 cp = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, cr); 262 dp = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, dr); 263 apm = ap.monic(); 264 bpm = bp.monic(); 265 cpm = cp.monic(); 266 dpm = dp.monic(); 267 //System.out.println("ap = " + ap); 268 //System.out.println("apm = " + apm); 269 //System.out.println("bp = " + bp); 270 //System.out.println("bpm = " + bpm); 271 //System.out.println("cp = " + cp); 272 //System.out.println("cpm = " + cpm); 273 //System.out.println("dp = " + dp); 274 //System.out.println("dpm = " + dpm); 275 assertTrue("", apm.leadingBaseCoefficient().isONE()); 276 assertTrue("", bpm.leadingBaseCoefficient().isONE()); 277 assertTrue("", cpm.leadingBaseCoefficient().isONE()); 278 assertTrue("", dpm.leadingBaseCoefficient().isONE()); 279 280 GreatestCommonDivisorAbstract<SolvableQuotient<BigRational>> fdq = new GreatestCommonDivisorSimple<SolvableQuotient<BigRational>>( 281 qfac); 282 gp = fdq.leftBaseGcd(ap, bp); 283 gpm = gp.monic(); 284 //System.out.println("gp = " + gp); 285 //System.out.println("gpm = " + gpm); 286 assertTrue("", gpm.leadingBaseCoefficient().isONE()); 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 simple. 304 */ 305 @SuppressWarnings("cast") 306 public void testRecursiveRightGCDSyzygy() { 307 String[] vars = new String[] { "a", "b" }; 308 dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, vars); 309 RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>(); 310 dfac.addRelations(wl); 311 //System.out.println("dfac = " + dfac.toScript()); 312 rfac = (RecSolvablePolynomialRing<BigRational>) dfac.recursive(1); 313 //System.out.println("rfac = " + rfac.toScript()); 314 315 RecSolvablePolynomialRing<BigRational> rrfacTemp = rfac; 316 GenSolvablePolynomialRing<GenPolynomial<BigRational>> rrfac = rfac; 317 318 GenSolvablePolynomialRing<BigRational> rcfac = (GenSolvablePolynomialRing<BigRational>) rfac.coFac; 319 SolvableQuotientRing<BigRational> qfac = new SolvableQuotientRing<BigRational>(rcfac); 320 QuotSolvablePolynomialRing<BigRational> rqfac = new QuotSolvablePolynomialRing<BigRational>(qfac, 321 rrfac); 322 List<GenSolvablePolynomial<GenPolynomial<BigRational>>> rl = rrfacTemp.coeffTable.relationList(); 323 List<GenPolynomial<GenPolynomial<BigRational>>> rlc = PolynomialList 324 .<GenPolynomial<BigRational>> castToList(rl); 325 rqfac.polCoeff.coeffTable.addRelations(rlc); 326 //System.out.println("rrfac = " + rrfac.toScript()); 327 //System.out.println("rcfac = " + rcfac.toScript()); 328 //System.out.println("qfac = " + qfac.toScript()); 329 //System.out.println("rqfac = " + rqfac.toScript()); 330 331 //kl = 3; 332 int ll = 3; 333 int 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 343 //System.out.println("ar = " + ar); 344 //System.out.println("br = " + br); 345 //System.out.println("cr = " + cr); 346 347 if (cr.isZERO()) { 348 cr = rfac.getONE(); 349 } 350 ar = cr.multiply(ar); 351 br = cr.multiply(br); 352 //ar = ar.multiply(cr); 353 //br = br.multiply(cr); 354 //System.out.println("ar = " + ar); 355 //System.out.println("br = " + br); 356 357 dr = fd.rightRecursiveUnivariateGcd(ar, br); 358 //System.out.println("cr = " + cr); 359 //System.out.println("dr = " + dr); 360 361 //er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightPseudoQuotient(dr, cr); 362 //System.out.println("dr/cr = " + er); 363 364 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(dr, 365 cr); 366 //System.out.println("er = " + er); 367 assertTrue("c | gcd(ac,bc) " + er, er.isZERO()); 368 369 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(ar, 370 dr); 371 //System.out.println("er = " + er); 372 assertTrue("gcd(a,b) | a " + er, er.isZERO()); 373 374 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(br, 375 dr); 376 //System.out.println("er = " + er); 377 assertTrue("gcd(a,b) | b " + er, er.isZERO()); 378 } 379 380 381 /** 382 * Test arbitrary recursive gcd simple. 383 */ 384 @SuppressWarnings("cast") 385 public void testArbitraryRecursiveGCDSyzygy() { 386 String[] cvars = new String[] { "a", "b" }; 387 String[] vars = new String[] { "c" }; 388 dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, cvars); 389 RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>(); 390 dfac.addRelations(wl); 391 //System.out.println("dfac = " + dfac.toScript()); 392 rfac = new RecSolvablePolynomialRing<BigRational>(dfac, to, vars); 393 //System.out.println("rfac = " + rfac.toScript()); 394 395 //kl = 3; ll = 2; 396 int el = 2; 397 398 ar0 = rfac.random(kl, ll, el + 1, q); 399 br0 = rfac.random(kl, ll, el, q); 400 cr = rfac.random(kl, ll, el, q); 401 402 //ar = rfac.parse("a + b c^2 "); 403 //br = rfac.parse("( a^2 - 1/3 ) c - 1/4"); 404 //cr = rfac.parse("(b - 1/2 a^2) c"); 405 //ar = rfac.parse("( 2/11 a * b^2 + 11/24 b - 11/6 a^2 )"); 406 //br = rfac.parse("( 14/13 b^2 - 1/69 )"); 407 //cr = rfac.parse("c + 33/133 a"); 408 //ar0 = rfac.parse("( a * b^2 + 1/2 b - 1/6 a^2 )"); 409 //br0 = rfac.parse("( b^2 - 1/5 )"); 410 //cr = rfac.parse("c + 3/13 a"); 411 412 //cr = (RecSolvablePolynomial<BigRational>) fd.recursivePrimitivePart(cr).abs(); 413 cr = (RecSolvablePolynomial<BigRational>) cr.monic(); 414 if (cr.isZERO()) { 415 cr = rfac.getONE(); 416 } 417 //System.out.println("ar = " + ar); 418 //System.out.println("br = " + br); 419 //System.out.println("cr = " + cr); 420 421 // left gcd 422 ar = ar0.multiply(cr); 423 br = br0.multiply(cr); 424 //System.out.println("ar = " + ar); 425 //System.out.println("br = " + br); 426 427 dr = fd.leftRecursiveGcd(ar, br); 428 //System.out.println("cr = " + cr); 429 //System.out.println("dr = " + dr); 430 431 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(dr, cr); 432 //System.out.println("er = " + er); 433 assertTrue("c | gcd(ac,bc) " + er, er.isZERO()); 434 435 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(ar, dr); 436 //System.out.println("er = " + er); 437 assertTrue("gcd(ac,bc) | ac " + er, er.isZERO()); 438 439 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(br, dr); 440 //System.out.println("er = " + er); 441 assertTrue("gcd(ac,bc) | bc " + er, er.isZERO()); 442 443 444 // right gcd 445 ar = cr.multiply(ar0); 446 br = cr.multiply(br0); 447 //System.out.println("ar = " + ar); 448 //System.out.println("br = " + br); 449 450 dr = fd.rightRecursiveGcd(ar, br); 451 //System.out.println("cr = " + cr); 452 //System.out.println("dr = " + dr); 453 454 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(dr, 455 cr); 456 //System.out.println("er = " + er); 457 assertTrue("c | gcd(ca,cb) " + er, er.isZERO()); 458 459 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(ar, 460 dr); 461 //System.out.println("er = " + er); 462 assertTrue("gcd(ca,cb) | ca " + er, er.isZERO()); 463 464 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(br, 465 dr); 466 //System.out.println("er = " + er); 467 assertTrue("gcd(ca,cb) | cb " + er, er.isZERO()); 468 } 469 470 471 /** 472 * Test full gcd simple, 4 variables. 473 */ 474 public void testGCDSyzygy() { 475 String[] vars = new String[] { "a", "b", "c", "d" }; 476 //String[] vars = new String[] { "a", "b" }; 477 dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, vars); 478 RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>(); 479 //RelationGenerator<BigRational> wl = new WeylRelations<BigRational>(); 480 dfac.addRelations(wl); 481 //System.out.println("dfac = " + dfac.toScript()); 482 483 //kl = 3; 484 ll = 4; 485 el = 4; 486 487 //a = dfac.random(kl, ll, el, q); 488 //b = dfac.random(kl, ll, el, q); 489 //c = dfac.random(kl, ll, el, q); 490 //c = c.multiply(dfac.univariate(0)); 491 492 a0 = dfac.parse("b^3 - 1/6 + d"); 493 b0 = dfac.parse("b + 3 a^2 + d"); 494 //b = dfac.parse("( -1/2 ) b + 3 a^2 + d"); 495 //c = dfac.parse("(a - 5 b) + c + d"); 496 //ok: c = dfac.parse("(a - b) c"); 497 //c = dfac.parse("(a - b) + c + d "); 498 //c = dfac.parse("(a - b) + c"); 499 //c = dfac.parse("(a - b) + b^2"); 500 c = dfac.parse("c - a - b"); 501 //c = dfac.parse("d - c - b - a"); 502 //c = dfac.parse("(a - b) + d"); 503 //c = dfac.parse("b + d"); 504 //c = dfac.parse("a + d"); 505 506 //a = dfac.parse("2 b^3 * d^2 + 2/3 a + 3/2"); 507 //b = dfac.parse("2/3 d + 1/2 a^3 + 3/4"); 508 //c = dfac.parse("c^2 * d - 1/2 a^3 * d + 5/4 d"); 509 510 //c = (GenSolvablePolynomial<BigRational>) fd.primitivePart(c).abs(); 511 c = c.monic(); 512 if (c.isZERO()) { 513 c = dfac.getONE(); 514 } 515 //System.out.println("a = " + a); 516 //System.out.println("b = " + b); 517 //System.out.println("c = " + c); 518 519 a = a0.multiply(c); 520 b = b0.multiply(c); 521 //System.out.println("a = " + a); 522 //System.out.println("b = " + b); 523 //System.out.println("c = " + c); 524 525 526 List<GenSolvablePolynomial<BigRational>> L = new ArrayList<GenSolvablePolynomial<BigRational>>(); 527 L.add(a); 528 L.add(b); 529 SolvableGroebnerBaseAbstract<BigRational> sbb = new SolvableGroebnerBaseSeq<BigRational>(); 530 531 // left 532 List<GenSolvablePolynomial<BigRational>> Llgb = sbb.leftGB(L); 533 //System.out.println("leftGB = " + Llgb); 534 //List<GenSolvablePolynomial<BigRational>> Ltgb = sbb.twosidedGB(L); 535 //System.out.println("twosidedGB = " + Ltgb); 536 537 d = fd.leftGcd(a, b); 538 //System.out.println("gb = " + Llgb); 539 //System.out.println("c = " + c); 540 //System.out.println("d = " + d); 541 assertTrue("d in leftGB", sbb.sred.leftNormalform(Llgb, d).isZERO()); 542 543 e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(d, c); 544 //System.out.println("e = " + e); 545 assertTrue("c | gcd(ac,bc): " + e, e.isZERO()); 546 547 e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(a, c); 548 //System.out.println("e = " + e); 549 assertTrue("c | ac: " + e, e.isZERO()); 550 e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(b, c); 551 //System.out.println("e = " + e); 552 assertTrue("c | bc: " + e, e.isZERO()); 553 554 e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(a, d); 555 //System.out.println("e = " + e); 556 //e = FDUtil.<BigRational> divideRightPolynomial(a,d); 557 //System.out.println("e = " + e); 558 assertTrue("gcd(a,b) | a: " + e, e.isZERO()); 559 560 e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(b, d); 561 //System.out.println("e = " + e); 562 //e = FDUtil.<BigRational> divideRightPolynomial(b,d); 563 //System.out.println("e = " + e); 564 assertTrue("gcd(a,b) | b: " + e, e.isZERO()); 565 566 567 // right 568 a = c.multiply(a0); 569 b = c.multiply(b0); 570 //System.out.println("a = " + a); 571 //System.out.println("b = " + b); 572 //System.out.println("c = " + c); 573 574 //List<GenSolvablePolynomial<BigRational>> Lrgb = sbb.rightGB(L); // too long 575 //System.out.println("rightGB = " + Lrgb); 576 //List<GenSolvablePolynomial<BigRational>> Ltgb = sbb.twosidedGB(L); 577 //System.out.println("twosidedGB = " + Ltgb); 578 579 d = fd.rightGcd(a, b); 580 //System.out.println("gb = " + Llgb); 581 //System.out.println("c = " + c); 582 //System.out.println("d = " + d); 583 584 e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(d, c); 585 //System.out.println("e = " + e); 586 assertTrue("c | gcd(ac,bc): " + e, e.isZERO()); 587 588 e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(a, c); 589 //System.out.println("e = " + e); 590 assertTrue("c | ac: " + e, e.isZERO()); 591 e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(b, c); 592 //System.out.println("e = " + e); 593 assertTrue("c | bc: " + e, e.isZERO()); 594 595 e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(a, d); 596 //System.out.println("e = " + e); 597 //e = FDUtil.<BigRational> divideRightPolynomial(a,d); 598 //System.out.println("e = " + e); 599 assertTrue("gcd(a,b) | a: " + e, e.isZERO()); 600 601 e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(b, d); 602 //System.out.println("e = " + e); 603 //e = FDUtil.<BigRational> divideRightPolynomial(b,d); 604 //System.out.println("e = " + e); 605 assertTrue("gcd(a,b) | b: " + e, e.isZERO()); 606 } 607 608 609 /** 610 * Test rational coefficients gcd polynomial cofactor tests. 611 */ 612 public void testRatCofactors() { 613 //System.out.println("dfac = " + dfac.toScript()); 614 do { 615 a = dfac.random(kl, ll, el, q); 616 } while (a.isZERO()||a.isConstant()); 617 do { 618 b = dfac.random(kl, ll, el, q/2f); 619 } while (b.isZERO()||b.isConstant()); 620 do { 621 c = dfac.random(kl, ll, el, q/2f); 622 } while (c.isZERO()||c.isConstant()); 623 c = c.monic(); 624 //System.out.println("a = " + a); 625 //System.out.println("b = " + b); 626 //System.out.println("c = " + c); 627 628 // non commutative left 629 //System.out.println("right: "); 630 d = c.multiply(a); 631 e = c.multiply(b); 632 //System.out.println("d = " + d); 633 //System.out.println("e = " + e); 634 635 GenSolvablePolynomial<BigRational>[] gco = fd.leftGcdCofactors(dfac, d, e); 636 //System.out.println("left gco[0] = " + gco[0]); 637 //System.out.println("gco[1] = " + gco[1]); 638 //System.out.println("gco[2] = " + gco[2]); 639 640 GenSolvablePolynomial<BigRational> ca, cb; 641 ca = gco[0].multiply(gco[1]); 642 cb = gco[0].multiply(gco[2]); 643 //System.out.println("ca = " + ca); 644 //System.out.println("d = " + d); 645 //System.out.println("cb = " + cb); 646 //System.out.println("e = " + e); 647 assertEquals("ca = c*a: ", ca, d); 648 assertEquals("cb = c*b: ", cb, e); 649 650 // non commutative right 651 //System.out.println("left: "); 652 d = a.multiply(c); 653 e = b.multiply(c); 654 //System.out.println("d = " + d); 655 //System.out.println("e = " + e); 656 657 gco = fd.rightGcdCofactors(dfac, d, e); 658 //System.out.println("right gco[0] = " + gco[0]); 659 //System.out.println("gco[1] = " + gco[1]); 660 //System.out.println("gco[2] = " + gco[2]); 661 662 GenSolvablePolynomial<BigRational> ac, bc; 663 ac = gco[1].multiply(gco[0]); 664 bc = gco[2].multiply(gco[0]); 665 //System.out.println("ac = " + ac); 666 //System.out.println("d = " + d); 667 //System.out.println("bc = " + bc); 668 //System.out.println("e = " + e); 669 assertEquals("ac = a*c: ", ac, d); 670 assertEquals("bc = b*c: ", bc, e); 671 } 672 673}