001/* 002 * $Id$ 003 */ 004 005package edu.jas.fd; 006 007 008import java.util.ArrayList; 009import java.util.List; 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 Simple PRS algorithm tests with JUnit. <b>Note:</b> not in sync with 034 * implementation. 035 * @author Heinz Kredel 036 */ 037 038public class GCDSimpleTest 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>GCDSimpleTest</CODE> object. 052 * @param name String. 053 */ 054 public GCDSimpleTest(String name) { 055 super(name); 056 } 057 058 059 /** 060 */ 061 public static Test suite() { 062 TestSuite suite = new TestSuite(GCDSimpleTest.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, f; 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 dfac = new GenSolvablePolynomialRing<BigRational>(cf, to, vars); 109 RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>(); 110 dfac.addRelations(wl); 111 rfac = (RecSolvablePolynomialRing<BigRational>) dfac.recursive(1); 112 //System.out.println("dfac = " + dfac); 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 simple. 128 */ 129 public void testBaseGcdSimple() { 130 String[] uvars = new String[] { "x" }; 131 dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), 1, to, uvars); 132 //System.out.println("dfac = " + dfac.toScript()); 133 for (int i = 0; i < 3; i++) { 134 //System.out.println(); 135 a = dfac.random(kl + (i + 2), ll + 2 * i, el + 2, q); 136 b = dfac.random(kl + (i + 1), ll + i, el + 2, q); 137 c = dfac.random(kl + (i + 1), ll + 1, el + 1, q); 138 c = c.multiply(dfac.univariate(0)); 139 if (a.isZERO() || b.isZERO() || c.isZERO()) { 140 // skip for this turn 141 continue; 142 } 143 //a = fd.basePrimitivePart(a); 144 //b = fd.basePrimitivePart(b); 145 //c = (GenSolvablePolynomial<BigRational>) fd.leftBasePrimitivePart(c).abs(); 146 //System.out.println("a = " + a); 147 //System.out.println("b = " + b); 148 //System.out.println("c = " + c); 149 150 a = a.multiply(c); 151 b = b.multiply(c); 152 //System.out.println("a = " + a); 153 //System.out.println("b = " + b); 154 155 d = fd.leftBaseGcd(a, b); 156 e = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> baseSparsePseudoRemainder(d, c); 157 //System.out.println("d = " + d); 158 //System.out.println("c = " + c); 159 assertTrue("c | gcd(ac,bc) " + e, e.isZERO()); 160 161 e = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> baseSparsePseudoRemainder(a, d); 162 //System.out.println("e = " + e); 163 assertTrue("gcd(a,b) | a " + e, e.isZERO()); 164 165 e = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> baseSparsePseudoRemainder(b, d); 166 //System.out.println("e = " + e); 167 assertTrue("gcd(a,b) | b " + e, e.isZERO()); 168 } 169 } 170 171 172 /** 173 * Test base extended gcd simple. 174 */ 175 public void xtestBaseExtendedGcdSimple() { 176 String[] uvars = new String[] { "x" }; 177 dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), 1, to, uvars); 178 //System.out.println("dfac = " + dfac.toScript()); 179 for (int i = 0; i < 3; i++) { 180 //System.out.println(); 181 a = dfac.random(kl + (i + 2), ll + 2 * i, el + 2, q); 182 b = dfac.random(kl + (i + 1), ll + i, el + 2, q); 183 c = dfac.random(kl + (i + 1), ll + 1, el + 1, q); 184 c = c.multiply(dfac.univariate(0)); 185 if (a.isZERO() || b.isZERO() || c.isZERO()) { 186 // skip for this turn 187 continue; 188 } 189 //a = fd.basePrimitivePart(a); 190 //b = fd.basePrimitivePart(b); 191 //c = (GenSolvablePolynomial<BigRational>) fd.basePrimitivePart(c).abs(); 192 //System.out.println("a = " + a); 193 //System.out.println("b = " + b); 194 //System.out.println("c = " + c); 195 196 a = a.multiply(c); 197 b = b.multiply(c); 198 //System.out.println("a = " + a); 199 //System.out.println("b = " + b); 200 201 // extended gcd 202 GenSolvablePolynomial<BigRational>[] egcd = fd.baseExtendedGcd(a, b); 203 //System.out.println("egcd = " + Arrays.toString(egcd)); 204 205 d = egcd[0]; 206 e = (GenSolvablePolynomial<BigRational>) a.multiply(egcd[1]).sum(b.multiply(egcd[2])); 207 //System.out.println("e = " + e); 208 f = (GenSolvablePolynomial<BigRational>) egcd[1].multiply(a).sum(egcd[2].multiply(b)); 209 //System.out.println("f = " + f); 210 assertEquals("e == f: ", e, f); 211 //assertEquals("gcd(a,b) = s a + t b: " + f, d, f.monic()); 212 assertTrue("gcd(a,b) = s a + t b: " + f, f.remainder(d).isZERO()); 213 214 // todo 215 //e = (GenSolvablePolynomial<BigRational>) FDUtil.<BigRational> leftBaseSparsePseudoRemainder(d,c); 216 //System.out.println("d = " + d); 217 //System.out.println("c = " + c); 218 //assertTrue("c | gcd(ac,bc) " + e, e.isZERO()); 219 220 // diophant solution 221 GenSolvablePolynomial<BigRational>[] dio = fd.baseGcdDiophant(a, b, d); 222 //System.out.println("dio = " + Arrays.toString(dio)); 223 224 e = (GenSolvablePolynomial<BigRational>) dio[0].multiply(a).sum(dio[1].multiply(b)); 225 //System.out.println("e = " + e); 226 f = (GenSolvablePolynomial<BigRational>) a.multiply(dio[0]).sum(b.multiply(dio[1])); 227 //System.out.println("f = " + f); 228 assertEquals("e == f: ", e, f); 229 //assertEquals("a*d + b*e == f: ", d, f.monic()); 230 //assertEquals("d*gcd(a,b) = s a + t b: : ", d, f.monic()); 231 assertTrue("d*gcd(a,b) = s a + t b: ", f.remainder(d).isZERO()); 232 233 e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(f, c); 234 //System.out.println("d = " + d); 235 //System.out.println("c = " + c); 236 assertTrue("c | a*s + b*t " + e, e.isZERO()); 237 } 238 } 239 240 241 /** 242 * Test univariate recursive left gcd simple. 243 */ 244 @SuppressWarnings("cast") 245 public void testRecursiveLeftGCDSimple() { 246 String[] vars = new String[] { "a", "b" }; 247 dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, vars); 248 RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>(); 249 dfac.addRelations(wl); 250 //System.out.println("dfac = " + dfac.toScript()); 251 rfac = (RecSolvablePolynomialRing<BigRational>) dfac.recursive(1); 252 //System.out.println("rfac = " + rfac.toScript()); 253 254 RecSolvablePolynomialRing<BigRational> rrfacTemp = rfac; 255 GenSolvablePolynomialRing<GenPolynomial<BigRational>> rrfac = rfac; 256 257 GenSolvablePolynomialRing<BigRational> rcfac = (GenSolvablePolynomialRing<BigRational>) rfac.coFac; 258 SolvableQuotientRing<BigRational> qfac = new SolvableQuotientRing<BigRational>(rcfac); 259 QuotSolvablePolynomialRing<BigRational> rqfac = new QuotSolvablePolynomialRing<BigRational>(qfac, 260 rrfac); 261 List<GenSolvablePolynomial<GenPolynomial<BigRational>>> rl = rrfacTemp.coeffTable.relationList(); 262 List<GenPolynomial<GenPolynomial<BigRational>>> rlc = PolynomialList 263 .<GenPolynomial<BigRational>> castToList(rl); 264 rqfac.polCoeff.coeffTable.addRelations(rlc); 265 //System.out.println("rrfac = " + rrfac.toScript()); 266 //System.out.println("rcfac = " + rcfac.toScript()); 267 //System.out.println("qfac = " + qfac.toScript()); 268 //System.out.println("rqfac = " + rqfac.toScript()); 269 270 //kl = 3; 271 ll = 3; 272 el = 3; 273 274 ar = rfac.random(kl, ll, el + 1, q); 275 br = rfac.random(kl, ll, el, q); 276 cr = rfac.random(kl, ll, el, q); 277 ////cr = (RecSolvablePolynomial<BigRational>) cr.abs(); 278 cr = (RecSolvablePolynomial<BigRational>) PolyUtil.<BigRational> monic(cr); 279 //cr = (RecSolvablePolynomial<BigRational>) fd.recursivePrimitivePart(cr).abs(); 280 //cr = rfac.getONE(); 281 //cr = rfac.parse("a+b+c+d"); 282 283 //ar = rfac.parse("( ( -31/19 ) ) b^3 - ( 781/260 a - 641/372 )"); 284 //br = rfac.parse("( ( -1/5 ) a - 1/4 ) b^2 - 11/12 b - ( 47/17 a + 29/30 )"); 285 //cr = rfac.parse(" ( a + 9/8 ) b + ( 285/208 a + 191/280 )"); 286 287 //ar = rfac.parse("b^3 - ( a )"); 288 //br = rfac.parse("( a ) b^2 - 1/2 b"); 289 //cr = rfac.parse("b + ( a )"); 290 291 //ar = rfac.parse("( 2/23 a - 1/2 ) b^3 + 617/672 b^2 - ( 5 a + 307/154 )"); 292 //br = rfac.parse("( ( -673/330 ) ) b - ( 2/5 a - 566969/1651860 )"); 293 //cr = rfac.parse("( a - 2287945/213324 )"); 294 295 //ar = rfac.parse("( b^2 + 1/2 )"); 296 //br = rfac.parse("( a^2 b - ( a - 1/3 ) )"); 297 //cr = rfac.parse("( b + a - 1/5 )"); 298 299 //System.out.println("ar = " + ar); 300 //System.out.println("br = " + br); 301 //System.out.println("cr = " + cr); 302 303 if (cr.isZERO()) { 304 cr = rfac.getONE(); 305 } 306 //ar = cr.multiply(ar); 307 //br = cr.multiply(br); 308 ar = ar.multiply(cr); 309 br = br.multiply(cr); 310 //System.out.println("ar = " + ar); 311 //System.out.println("br = " + br); 312 313 dr = fd.leftRecursiveUnivariateGcd(ar, br); 314 //System.out.println("cr = " + cr); 315 //System.out.println("dr = " + dr); 316 317 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(dr, cr); 318 //System.out.println("er = " + er); 319 assertTrue("c | gcd(ac,bc) " + er, er.isZERO()); 320 321 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(ar, dr); 322 //System.out.println("er = " + er); 323 assertTrue("gcd(a,b) | a " + er, er.isZERO()); 324 325 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(br, dr); 326 //System.out.println("er = " + er); 327 assertTrue("gcd(a,b) | b " + er, er.isZERO()); 328 329 //if (true) return; 330 GenSolvablePolynomial<SolvableQuotient<BigRational>> ap, bp, cp, dp, gp, ep, apm, bpm, cpm, dpm, gpm; 331 ap = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, ar); 332 bp = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, br); 333 cp = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, cr); 334 dp = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, dr); 335 apm = ap.monic(); 336 bpm = bp.monic(); 337 cpm = cp.monic(); 338 dpm = dp.monic(); 339 //System.out.println("ap = " + ap); 340 //System.out.println("apm = " + apm); 341 //System.out.println("bp = " + bp); 342 //System.out.println("bpm = " + bpm); 343 //System.out.println("cp = " + cp); 344 //System.out.println("cpm = " + cpm); 345 //System.out.println("dp = " + dp); 346 //System.out.println("dpm = " + dpm); 347 assertTrue("", apm.leadingBaseCoefficient().isONE()); 348 assertTrue("", bpm.leadingBaseCoefficient().isONE()); 349 assertTrue("", cpm.leadingBaseCoefficient().isONE()); 350 assertTrue("", dpm.leadingBaseCoefficient().isONE()); 351 352 GreatestCommonDivisorAbstract<SolvableQuotient<BigRational>> fdq = new GreatestCommonDivisorSimple<SolvableQuotient<BigRational>>( 353 qfac); 354 gp = fdq.leftBaseGcd(ap, bp); 355 gpm = gp.monic(); 356 //System.out.println("gp = " + gp); 357 //System.out.println("gpm = " + gpm); 358 assertTrue("", gpm.leadingBaseCoefficient().isONE()); 359 360 ep = FDUtil.<SolvableQuotient<BigRational>> leftBaseSparsePseudoRemainder(gp, dp); 361 //System.out.println("ep = " + ep); 362 assertTrue("c | gcd(ac,bc): " + ep, ep.isZERO()); 363 364 ep = FDUtil.<SolvableQuotient<BigRational>> leftBaseSparsePseudoRemainder(ap, gp); 365 //System.out.println("ep = " + ep); 366 assertTrue("gcd(ac,bc)| ac): " + ep, ep.isZERO()); 367 368 ep = FDUtil.<SolvableQuotient<BigRational>> leftBaseSparsePseudoRemainder(bp, gp); 369 //System.out.println("ep = " + ep); 370 assertTrue("gcd(ac,bc)| bc): " + ep, ep.isZERO()); 371 } 372 373 374 /** 375 * Test univariate recursive right gcd simple. 376 */ 377 @SuppressWarnings("cast") 378 public void ztestRecursiveRightGCDSimple() { 379 String[] vars = new String[] { "a", "b" }; 380 dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, vars); 381 RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>(); 382 dfac.addRelations(wl); 383 //System.out.println("dfac = " + dfac.toScript()); 384 rfac = (RecSolvablePolynomialRing<BigRational>) dfac.recursive(1); 385 //System.out.println("rfac = " + rfac.toScript()); 386 387 RecSolvablePolynomialRing<BigRational> rrfacTemp = rfac; 388 GenSolvablePolynomialRing<GenPolynomial<BigRational>> rrfac = rfac; 389 390 GenSolvablePolynomialRing<BigRational> rcfac = (GenSolvablePolynomialRing<BigRational>) rfac.coFac; 391 SolvableQuotientRing<BigRational> qfac = new SolvableQuotientRing<BigRational>(rcfac); 392 QuotSolvablePolynomialRing<BigRational> rqfac = new QuotSolvablePolynomialRing<BigRational>(qfac, 393 rrfac); 394 List<GenSolvablePolynomial<GenPolynomial<BigRational>>> rl = rrfacTemp.coeffTable.relationList(); 395 List<GenPolynomial<GenPolynomial<BigRational>>> rlc = PolynomialList 396 .<GenPolynomial<BigRational>> castToList(rl); 397 rqfac.polCoeff.coeffTable.addRelations(rlc); 398 //System.out.println("rrfac = " + rrfac.toScript()); 399 //System.out.println("rcfac = " + rcfac.toScript()); 400 //System.out.println("qfac = " + qfac.toScript()); 401 //System.out.println("rqfac = " + rqfac.toScript()); 402 403 //kl = 3; 404 int ll = 3; 405 int el = 3; 406 407 ar = rfac.random(kl, ll, el + 1, q); 408 br = rfac.random(kl, ll, el, q); 409 cr = rfac.random(kl, ll, el, q); 410 ////cr = (RecSolvablePolynomial<BigRational>) cr.abs(); 411 cr = (RecSolvablePolynomial<BigRational>) PolyUtil.<BigRational> monic(cr); 412 //cr = (RecSolvablePolynomial<BigRational>) fd.recursivePrimitivePart(cr).abs(); 413 //cr = rfac.getONE(); 414 415 //System.out.println("ar = " + ar); 416 //System.out.println("br = " + br); 417 //System.out.println("cr = " + cr); 418 419 if (cr.isZERO()) { 420 cr = rfac.getONE(); 421 } 422 ar = cr.multiply(ar); 423 br = cr.multiply(br); 424 //ar = ar.multiply(cr); 425 //br = br.multiply(cr); 426 //System.out.println("ar = " + ar); 427 //System.out.println("br = " + br); 428 429 dr = fd.rightRecursiveUnivariateGcd(ar, br); 430 //System.out.println("cr = " + cr); 431 //System.out.println("dr = " + dr); 432 433 //er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightPseudoQuotient(dr, cr); 434 //System.out.println("dr/cr = " + er); 435 436 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(dr, 437 cr); 438 //System.out.println("er = " + er); 439 assertTrue("c | gcd(ac,bc) " + er, er.isZERO()); 440 441 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(ar, 442 dr); 443 //System.out.println("er = " + er); 444 assertTrue("gcd(a,b) | a " + er, er.isZERO()); 445 446 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(br, 447 dr); 448 //System.out.println("er = " + er); 449 assertTrue("gcd(a,b) | b " + er, er.isZERO()); 450 } 451 452 453 /** 454 * Test arbitrary recursive gcd simple. 455 */ 456 @SuppressWarnings("cast") 457 public void testArbitrary3RecursiveGCDSimple() { 458 String[] cvars = new String[] { "a", "b" }; 459 String[] vars = new String[] { "c" }; 460 dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, cvars); 461 RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>(); 462 dfac.addRelations(wl); 463 //System.out.println("dfac = " + dfac.toScript()); 464 rfac = new RecSolvablePolynomialRing<BigRational>(dfac, to, vars); 465 //System.out.println("rfac = " + rfac.toScript()); 466 467 //kl = 3; ll = 2; 468 int el = 2; 469 470 ar0 = rfac.random(kl, ll, el + 1, q); 471 br0 = rfac.random(kl, ll, el, q); 472 cr = rfac.random(kl, ll, el, q); 473 474 //ar = rfac.parse("a + b c^2 "); 475 //br = rfac.parse("( a^2 - 1/3 ) c - 1/4"); 476 //cr = rfac.parse("(b - 1/2 a^2) c"); 477 //ar = rfac.parse("( 2/11 a * b^2 + 11/24 b - 11/6 a^2 )"); 478 //br = rfac.parse("( 14/13 b^2 - 1/69 )"); 479 //cr = rfac.parse("c + 33/133 a"); 480 //ar0 = rfac.parse("( a * b^2 + 1/2 b - 1/6 a^2 )"); 481 //br0 = rfac.parse("( b^2 - 1/5 )"); 482 //cr = rfac.parse("c + 3/13 a"); 483 484 //cr = (RecSolvablePolynomial<BigRational>) fd.recursivePrimitivePart(cr).abs(); 485 cr = (RecSolvablePolynomial<BigRational>) cr.monic(); 486 if (cr.isZERO()) { 487 cr = rfac.getONE(); 488 } 489 //System.out.println("ar = " + ar); 490 //System.out.println("br = " + br); 491 //System.out.println("cr = " + cr); 492 493 // left gcd 494 ar = ar0.multiply(cr); 495 br = br0.multiply(cr); 496 //System.out.println("ar = " + ar); 497 //System.out.println("br = " + br); 498 499 dr = fd.leftRecursiveGcd(ar, br); 500 //System.out.println("cr = " + cr); 501 //System.out.println("dr = " + dr); 502 503 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(dr, cr); 504 //System.out.println("er = " + er); 505 assertTrue("c | gcd(ac,bc): " + er, er.isZERO()); 506 507 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(ar, dr); 508 //System.out.println("er = " + er); 509 assertTrue("gcd(ac,bc) | ac: " + er, er.isZERO()); 510 511 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(br, dr); 512 //System.out.println("er = " + er); 513 assertTrue("gcd(ac,bc) | bc: " + er, er.isZERO()); 514 515 // true at this point 516 if (er.isZERO()) return; 517 // right gcd 518 ar = cr.multiply(ar0); 519 br = cr.multiply(br0); 520 //System.out.println("ar = " + ar); 521 //System.out.println("br = " + br); 522 523 dr = fd.rightRecursiveGcd(ar, br); 524 //System.out.println("cr = " + cr); 525 //System.out.println("dr = " + dr); 526 527 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(dr, 528 cr); 529 //System.out.println("er = " + er); 530 assertTrue("c | gcd(ca,cb) " + er, er.isZERO()); 531 532 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(ar, 533 dr); 534 //System.out.println("er = " + er); 535 assertTrue("gcd(ca,cb) | ca " + er, er.isZERO()); 536 537 er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveRightSparsePseudoRemainder(br, 538 dr); 539 //System.out.println("er = " + er); 540 assertTrue("gcd(ca,cb) | cb " + er, er.isZERO()); 541 } 542 543 544 /** 545 * Test full gcd simple, 4 variables. 546 */ 547 public void testGCD4Simple() { 548 String[] vars = new String[] { "a", "b", "c", "d" }; 549 //String[] vars = new String[] { "a", "b" }; 550 dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, vars); 551 RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>(); 552 //RelationGenerator<BigRational> wl = new WeylRelations<BigRational>(); 553 dfac.addRelations(wl); 554 //System.out.println("dfac = " + dfac.toScript()); 555 556 //kl = 3; 557 ll = 4; 558 el = 4; 559 560 //a = dfac.random(kl, ll, el, q); 561 //b = dfac.random(kl, ll, el, q); 562 //c = dfac.random(kl, ll, el, q); 563 //c = c.multiply(dfac.univariate(0)); 564 565 a0 = dfac.parse("b^3 - 1/6 + d"); 566 b0 = dfac.parse("b + 3 a^2 + d"); 567 //b = dfac.parse("( -1/2 ) b + 3 a^2 + d"); 568 //c = dfac.parse("(a - 5 b) + c + d"); 569 //ok: c = dfac.parse("(a - b) c"); 570 //c = dfac.parse("(a - b) + c + d "); 571 //c = dfac.parse("(a - b) + c"); 572 //c = dfac.parse("(a - b) + b^2"); 573 c = dfac.parse("c - a - b"); 574 //c = dfac.parse("d - c - b - a"); 575 //c = dfac.parse("(a - b) + d"); 576 //c = dfac.parse("b + d"); 577 //c = dfac.parse("a + d"); 578 579 //a = dfac.parse("2 b^3 * d^2 + 2/3 a + 3/2"); 580 //b = dfac.parse("2/3 d + 1/2 a^3 + 3/4"); 581 //c = dfac.parse("c^2 * d - 1/2 a^3 * d + 5/4 d"); 582 583 //c = (GenSolvablePolynomial<BigRational>) fd.primitivePart(c).abs(); 584 c = c.monic(); 585 if (c.isZERO()) { 586 c = dfac.getONE(); 587 } 588 //System.out.println("a = " + a); 589 //System.out.println("b = " + b); 590 //System.out.println("c = " + c); 591 592 a = a0.multiply(c); 593 b = b0.multiply(c); 594 //System.out.println("a = " + a); 595 //System.out.println("b = " + b); 596 //System.out.println("c = " + c); 597 598 599 List<GenSolvablePolynomial<BigRational>> L = new ArrayList<GenSolvablePolynomial<BigRational>>(); 600 L.add(a); 601 L.add(b); 602 SolvableGroebnerBaseAbstract<BigRational> sbb = new SolvableGroebnerBaseSeq<BigRational>(); 603 604 // left 605 List<GenSolvablePolynomial<BigRational>> Llgb = sbb.leftGB(L); 606 //System.out.println("leftGB = " + Llgb); 607 //List<GenSolvablePolynomial<BigRational>> Ltgb = sbb.twosidedGB(L); 608 //System.out.println("twosidedGB = " + Ltgb); 609 610 d = fd.leftGcd(a, b); 611 System.out.println("gb = " + Llgb); 612 System.out.println("c = " + c); 613 System.out.println("d = " + d); 614 assertTrue("c in leftGB", sbb.sred.leftNormalform(Llgb, c).isZERO()); 615 //todo: assertTrue("d in leftGB", sbb.sred.leftNormalform(Llgb, d).isZERO()); 616 617 e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(a, c); 618 //System.out.println("e = " + e); 619 assertTrue("c | ac: " + e, e.isZERO()); 620 e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(b, c); 621 //System.out.println("e = " + e); 622 assertTrue("c | bc: " + e, e.isZERO()); 623 624 e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(a, d); 625 //System.out.println("e = " + e); 626 //e = FDUtil.<BigRational> divideRightPolynomial(a,d); 627 //System.out.println("e = " + e); 628 assertTrue("gcd(a,b) | a: " + e, e.isZERO()); 629 630 e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(b, d); 631 //System.out.println("e = " + e); 632 //e = FDUtil.<BigRational> divideRightPolynomial(b,d); 633 //System.out.println("e = " + e); 634 assertTrue("gcd(a,b) | b: " + e, e.isZERO()); 635 636 //todo: e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(d, c); 637 //System.out.println("e = " + e); 638 //assertTrue("c | gcd(ac,bc): " + e, e.isZERO()); 639 640 // todo: 641 if (e.isZERO()) return; 642 // right 643 a = c.multiply(a0); 644 b = c.multiply(b0); 645 //System.out.println("a = " + a); 646 //System.out.println("b = " + b); 647 //System.out.println("c = " + c); 648 649 //List<GenSolvablePolynomial<BigRational>> Lrgb = sbb.rightGB(L); // too long 650 //System.out.println("rightGB = " + Lrgb); 651 //List<GenSolvablePolynomial<BigRational>> Ltgb = sbb.twosidedGB(L); 652 //System.out.println("twosidedGB = " + Ltgb); 653 654 d = fd.rightGcd(a, b); 655 //System.out.println("gb = " + Llgb); 656 //System.out.println("c = " + c); 657 //System.out.println("d = " + d); 658 //assertTrue("d in rightGB", sbb.sred.rightNormalform(Lrgb, d).isZERO()); 659 660 e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(d, c); 661 //System.out.println("e = " + e); 662 assertTrue("c | gcd(ac,bc): " + e, e.isZERO()); 663 664 e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(a, c); 665 //System.out.println("e = " + e); 666 assertTrue("c | ac: " + e, e.isZERO()); 667 e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(b, c); 668 //System.out.println("e = " + e); 669 assertTrue("c | bc: " + e, e.isZERO()); 670 671 e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(a, d); 672 //System.out.println("e = " + e); 673 //e = FDUtil.<BigRational> divideRightPolynomial(a,d); 674 //System.out.println("e = " + e); 675 assertTrue("gcd(a,b) | a: " + e, e.isZERO()); 676 677 e = FDUtil.<BigRational> rightBaseSparsePseudoRemainder(b, d); 678 //System.out.println("e = " + e); 679 //e = FDUtil.<BigRational> divideRightPolynomial(b,d); 680 //System.out.println("e = " + e); 681 assertTrue("gcd(a,b) | b: " + e, e.isZERO()); 682 } 683 684 685 /** 686 * Test rational coefficients gcd polynomial cofactor tests. 687 */ 688 public void ztestRatCofactors() { 689 //System.out.println("dfac = " + dfac.toScript()); 690 do { 691 a = dfac.random(kl, ll, el, q); 692 } while (a.isZERO() || a.isConstant()); 693 do { 694 b = dfac.random(kl, ll, el, q / 2f); 695 } while (b.isZERO() || b.isConstant()); 696 do { 697 c = dfac.random(kl, ll, el, q / 2f); 698 } while (c.isZERO() || c.isConstant()); 699 c = c.monic(); 700 //System.out.println("a = " + a); 701 //System.out.println("b = " + b); 702 //System.out.println("c = " + c); 703 704 // non commutative left 705 //System.out.println("left: "); 706 d = c.multiply(a); 707 e = c.multiply(b); 708 //System.out.println("d = " + d); 709 //System.out.println("e = " + e); 710 711 GenSolvablePolynomial<BigRational>[] gco = fd.leftGcdCofactors(dfac, d, e); 712 //System.out.println("left gco[0] = " + gco[0]); 713 //System.out.println("gco[1] = " + gco[1]); 714 //System.out.println("gco[2] = " + gco[2]); 715 716 GenSolvablePolynomial<BigRational> ca, cb; 717 ca = gco[0].multiply(gco[1]); 718 cb = gco[0].multiply(gco[2]); 719 System.out.println("ca = " + ca); 720 System.out.println("d = " + d); 721 System.out.println("cb = " + cb); 722 System.out.println("e = " + e); 723 assertEquals("ca = c*a: ", ca, d); 724 assertEquals("cb = c*b: ", cb, e); 725 726 if (ca.equals(d)) return; 727 // non commutative right 728 //System.out.println("right: "); 729 d = a.multiply(c); 730 e = b.multiply(c); 731 //System.out.println("d = " + d); 732 //System.out.println("e = " + e); 733 734 gco = fd.rightGcdCofactors(dfac, d, e); 735 //System.out.println("right gco[0] = " + gco[0]); 736 //System.out.println("gco[1] = " + gco[1]); 737 //System.out.println("gco[2] = " + gco[2]); 738 739 GenSolvablePolynomial<BigRational> ac, bc; 740 ac = gco[1].multiply(gco[0]); 741 bc = gco[2].multiply(gco[0]); 742 //System.out.println("ac = " + ac); 743 //System.out.println("d = " + d); 744 //System.out.println("bc = " + bc); 745 //System.out.println("e = " + e); 746 assertEquals("ac = a*c: ", ac, d); 747 assertEquals("bc = b*c: ", bc, e); 748 } 749 750}