001/* 002 * $Id: Examples.java 5248 2015-05-11 20:00:14Z kredel $ 003 */ 004 005package edu.jas.poly; 006 007 008import java.util.ArrayList; 009import java.util.List; 010 011import org.apache.log4j.BasicConfigurator; 012 013import edu.jas.arith.BigInteger; 014import edu.jas.arith.BigRational; 015import edu.jas.arith.ModInteger; 016import edu.jas.arith.ModIntegerRing; 017import edu.jas.kern.Scripting; 018 019 020/** 021 * Examples for polynomials usage. 022 * @author Heinz Kredel. 023 */ 024 025public class Examples { 026 027 028 /** 029 * main. 030 */ 031 public static void main(String[] args) { 032 BasicConfigurator.configure(); 033 //example0(); 034 /* 035 example1(); 036 example2(); 037 example3(); 038 example4(); 039 example5(); 040 */ 041 //example6(); 042 example7(); 043 example7(); 044 //example8(); 045 //example9(); 046 //example10(); 047 //example11(); 048 //example12(); 049 //example13(); 050 } 051 052 053 /** 054 * example0. for PPPJ 2006. 055 */ 056 public static void example0() { 057 BigInteger z = new BigInteger(); 058 059 TermOrder to = new TermOrder(); 060 String[] vars = new String[] { "x1", "x2", "x3" }; 061 GenPolynomialRing<BigInteger> ring; 062 ring = new GenPolynomialRing<BigInteger>(z, 3, to, vars); 063 System.out.println("ring = " + ring); 064 065 GenPolynomial<BigInteger> pol; 066 pol = ring.parse("3 x1^2 x3^4 + 7 x2^5 - 61"); 067 System.out.println("pol = " + pol); 068 System.out.println("pol = " + pol.toString(ring.getVars())); 069 070 GenPolynomial<BigInteger> one; 071 one = ring.parse("1"); 072 System.out.println("one = " + one); 073 System.out.println("one = " + one.toString(ring.getVars())); 074 075 GenPolynomial<BigInteger> p; 076 p = pol.subtract(pol); 077 System.out.println("p = " + p); 078 System.out.println("p = " + p.toString(ring.getVars())); 079 080 p = pol.multiply(pol); 081 System.out.println("p = " + p); 082 System.out.println("p = " + p.toString(ring.getVars())); 083 } 084 085 086 /** 087 * example1. random polynomial with rational coefficients. Q[x_1,...x_7] 088 */ 089 public static void example1() { 090 System.out.println("\n\n example 1"); 091 092 BigRational cfac = new BigRational(); 093 System.out.println("cfac = " + cfac); 094 GenPolynomialRing<BigRational> fac; 095 fac = new GenPolynomialRing<BigRational>(cfac, 7); 096 //System.out.println("fac = " + fac); 097 System.out.println("fac = " + fac); 098 099 GenPolynomial<BigRational> a = fac.random(10); 100 System.out.println("a = " + a); 101 } 102 103 104 /** 105 * example2. random polynomial with coefficients of rational polynomials. 106 * Q[x_1,...x_7][y_1,...,y_3] 107 */ 108 public static void example2() { 109 System.out.println("\n\n example 2"); 110 111 BigRational cfac = new BigRational(); 112 System.out.println("cfac = " + cfac); 113 GenPolynomialRing<BigRational> fac; 114 fac = new GenPolynomialRing<BigRational>(cfac, 7); 115 System.out.println("fac = " + fac); 116 117 GenPolynomialRing<GenPolynomial<BigRational>> gfac; 118 gfac = new GenPolynomialRing<GenPolynomial<BigRational>>(fac, 3); 119 System.out.println("gfac = " + gfac); 120 121 GenPolynomial<GenPolynomial<BigRational>> a = gfac.random(10); 122 System.out.println("a = " + a); 123 } 124 125 126 /** 127 * example3. random rational algebraic number. Q(alpha) 128 */ 129 public static void example3() { 130 System.out.println("\n\n example 3"); 131 132 BigRational cfac = new BigRational(); 133 System.out.println("cfac = " + cfac); 134 135 GenPolynomialRing<BigRational> mfac; 136 mfac = new GenPolynomialRing<BigRational>(cfac, 1); 137 System.out.println("mfac = " + mfac); 138 139 GenPolynomial<BigRational> modul = mfac.random(8).monic(); 140 // assume !mo.isUnit() 141 System.out.println("modul = " + modul); 142 143 AlgebraicNumberRing<BigRational> fac; 144 fac = new AlgebraicNumberRing<BigRational>(modul); 145 System.out.println("fac = " + fac); 146 147 AlgebraicNumber<BigRational> a = fac.random(15); 148 System.out.println("a = " + a); 149 } 150 151 152 protected static long getPrime() { 153 long prime = 2; //2^60-93; // 2^30-35; //19; knuth (2,390) 154 for (int i = 1; i < 60; i++) { 155 prime *= 2; 156 } 157 prime -= 93; 158 //System.out.println("prime = " + prime); 159 return prime; 160 } 161 162 163 /** 164 * example4. random modular algebraic number. Z_p(alpha) 165 */ 166 public static void example4() { 167 System.out.println("\n\n example 4"); 168 169 long prime = getPrime(); 170 ModIntegerRing cfac = new ModIntegerRing(prime); 171 System.out.println("cfac = " + cfac); 172 173 GenPolynomialRing<ModInteger> mfac; 174 mfac = new GenPolynomialRing<ModInteger>(cfac, 1); 175 System.out.println("mfac = " + mfac); 176 177 GenPolynomial<ModInteger> modul = mfac.random(8).monic(); 178 // assume !modul.isUnit() 179 System.out.println("modul = " + modul); 180 181 AlgebraicNumberRing<ModInteger> fac; 182 fac = new AlgebraicNumberRing<ModInteger>(modul); 183 System.out.println("fac = " + fac); 184 185 AlgebraicNumber<ModInteger> a = fac.random(12); 186 System.out.println("a = " + a); 187 } 188 189 190 /** 191 * example5. random solvable polynomial with rational coefficients. 192 * Q{x_1,...x_6, {x_2 * x_1 = x_1 x_2 +1, ...} } 193 */ 194 public static void example5() { 195 System.out.println("\n\n example 5"); 196 197 BigRational cfac = new BigRational(); 198 System.out.println("cfac = " + cfac); 199 GenSolvablePolynomialRing<BigRational> sfac; 200 sfac = new GenSolvablePolynomialRing<BigRational>(cfac, 6); 201 //System.out.println("sfac = " + sfac); 202 203 RelationGenerator<BigRational> wl = new WeylRelations<BigRational>(); 204 //wl.generate(sfac); 205 sfac.addRelations(wl); 206 System.out.println("sfac = " + sfac); 207 208 GenSolvablePolynomial<BigRational> a = sfac.random(5); 209 System.out.println("a = " + a); 210 System.out.println("a = " + a.toString(sfac.vars)); 211 212 GenSolvablePolynomial<BigRational> b = a.multiply(a); 213 System.out.println("b = " + b); 214 System.out.println("b = " + b.toString(sfac.vars)); 215 216 System.out.println("sfac = " + sfac); 217 } 218 219 220 /** 221 * example6. Fateman benchmark: p = (x+y+z)^20; q = p * (p+1) Z[z,y,x] 222 */ 223 public static void example6() { 224 System.out.println("\n\n example 6"); 225 226 BigInteger cfac = new BigInteger(); 227 System.out.println("cfac = " + cfac); 228 229 TermOrder to = new TermOrder(TermOrder.INVLEX); 230 System.out.println("to = " + to); 231 232 GenPolynomialRing<BigInteger> fac; 233 fac = new GenPolynomialRing<BigInteger>(cfac, 3, to); 234 System.out.println("fac = " + fac); 235 fac.setVars(new String[] { "z", "y", "x" }); 236 System.out.println("fac = " + fac); 237 238 GenPolynomial<BigInteger> x = fac.univariate(0); 239 GenPolynomial<BigInteger> y = fac.univariate(1); 240 GenPolynomial<BigInteger> z = fac.univariate(2); 241 242 System.out.println("x = " + x); 243 System.out.println("x = " + x.toString(fac.vars)); 244 System.out.println("y = " + y); 245 System.out.println("y = " + y.toString(fac.vars)); 246 System.out.println("z = " + z); 247 System.out.println("z = " + z.toString(fac.vars)); 248 249 GenPolynomial<BigInteger> p = x.sum(y).sum(z).sum(fac.getONE()); 250 //BigInteger f = cfac.fromInteger(10000000001L); 251 // p = p.multiply( f ); 252 System.out.println("p = " + p); 253 System.out.println("p = " + p.toString(fac.vars)); 254 255 GenPolynomial<BigInteger> q = p; 256 for (int i = 1; i < 20; i++) { 257 q = q.multiply(p); 258 } 259 //System.out.println("q = " + q.toString( fac.vars ) ); 260 System.out.println("q = " + q.length()); 261 262 GenPolynomial<BigInteger> q1 = q.sum(fac.getONE()); 263 264 GenPolynomial<BigInteger> q2; 265 long t = System.currentTimeMillis(); 266 q2 = q.multiply(q1); 267 t = System.currentTimeMillis() - t; 268 269 System.out.println("q2 = " + q2.length()); 270 System.out.println("time = " + t + " ms"); 271 } 272 273 274 /** 275 * example7. Fateman benchmark: p = (x+y+z)^20; q = p * (p+1) Q[z,y,x] 276 */ 277 public static void example7() { 278 System.out.println("\n\n example 7"); 279 280 BigRational cfac = new BigRational(); 281 System.out.println("cfac = " + cfac); 282 283 TermOrder to = new TermOrder(TermOrder.INVLEX); 284 System.out.println("to = " + to); 285 286 GenPolynomialRing<BigRational> fac; 287 fac = new GenPolynomialRing<BigRational>(cfac, 3, to); 288 System.out.println("fac = " + fac); 289 fac.setVars(new String[] { "z", "y", "x" }); 290 System.out.println("fac = " + fac); 291 292 long mi = 1L; 293 //long mi = Integer.MAX_VALUE; 294 GenPolynomial<BigRational> x = fac.univariate(0, mi); 295 GenPolynomial<BigRational> y = fac.univariate(1, mi); 296 GenPolynomial<BigRational> z = fac.univariate(2, mi); 297 298 // System.out.println("x = " + x); 299 System.out.println("x = " + x.toString(fac.vars)); 300 // System.out.println("y = " + y); 301 System.out.println("y = " + y.toString(fac.vars)); 302 // System.out.println("z = " + z); 303 System.out.println("z = " + z.toString(fac.vars)); 304 305 GenPolynomial<BigRational> p = x.sum(y).sum(z).sum(fac.getONE()); 306 //BigRational f = cfac.fromInteger(10000000001L); 307 // f = f.multiply( f ); 308 //p = p.multiply( f ); 309 // System.out.println("p = " + p); 310 System.out.println("p = " + p.toString(fac.vars)); 311 312 int mpow = 20; 313 System.out.println("mpow = " + mpow); 314 GenPolynomial<BigRational> q = p; 315 for (int i = 1; i < mpow; i++) { 316 q = q.multiply(p); 317 } 318 //System.out.println("q = " + q.toString( fac.vars ) ); 319 System.out.println("len(q) = " + q.length()); 320 System.out.println("deg(q) = " + q.degree()); 321 322 GenPolynomial<BigRational> q1 = q.sum(fac.getONE()); 323 324 GenPolynomial<BigRational> q2; 325 long t = System.currentTimeMillis(); 326 q2 = q.multiply(q1); 327 t = System.currentTimeMillis() - t; 328 329 System.out.println("len(q2) = " + q2.length()); 330 System.out.println("deg(q2) = " + q2.degree()); 331 System.out.println("LeadEV(q2) = " + q2.leadingExpVector()); 332 System.out.println("time = " + t + " ms"); 333 } 334 335 336 /** 337 * example8. Chebyshev polynomials 338 * 339 * T(0) = 1 T(1) = x T(n) = 2x * T(n-1) - T(n-2) 340 */ 341 public static void example8() { 342 int m = 10; 343 BigInteger fac = new BigInteger(); 344 String[] var = new String[] { "x" }; 345 346 GenPolynomialRing<BigInteger> ring = new GenPolynomialRing<BigInteger>(fac, 1, var); 347 348 List<GenPolynomial<BigInteger>> T = new ArrayList<GenPolynomial<BigInteger>>(m); 349 350 GenPolynomial<BigInteger> t, one, x, x2, x2b; 351 352 one = ring.getONE(); 353 x = ring.univariate(0); 354 //x2 = ring.parse("2 x"); 355 //x2a = x.multiply( fac.fromInteger(2) ); 356 x2b = x.multiply(new BigInteger(2)); 357 x2 = x2b; 358 359 T.add(one); 360 T.add(x); 361 for (int n = 2; n < m; n++) { 362 t = x2.multiply(T.get(n - 1)).subtract(T.get(n - 2)); 363 T.add(t); 364 } 365 for (int n = 0 /*m-2*/; n < m; n++) { 366 System.out.println("T[" + n + "] = " + T.get(n)); //.toString(var) ); 367 } 368 } 369 370 371 /** 372 * example9. Legendre polynomials 373 * 374 * P(0) = 1 P(1) = x P(n) = 1/n [ (2n-1) * x * P(n-1) - (n-1) * P(n-2) ] 375 */ 376 // P(n+1) = 1/(n+1) [ (2n+1) * x * P(n) - n * P(n-1) ] 377 public static void example9() { 378 int n = 10; 379 380 BigRational fac = new BigRational(); 381 String[] var = new String[] { "x" }; 382 383 GenPolynomialRing<BigRational> ring = new GenPolynomialRing<BigRational>(fac, 1, var); 384 385 List<GenPolynomial<BigRational>> P = new ArrayList<GenPolynomial<BigRational>>(n); 386 387 GenPolynomial<BigRational> t, one, x, xc; 388 BigRational n21, nn; 389 390 one = ring.getONE(); 391 x = ring.univariate(0); 392 393 P.add(one); 394 P.add(x); 395 for (int i = 2; i < n; i++) { 396 n21 = new BigRational(2 * i - 1); 397 xc = x.multiply(n21); 398 t = xc.multiply(P.get(i - 1)); 399 nn = new BigRational(i - 1); 400 xc = P.get(i - 2).multiply(nn); 401 t = t.subtract(xc); 402 nn = new BigRational(1, i); 403 t = t.multiply(nn); 404 P.add(t); 405 } 406 for (int i = 0; i < n; i++) { 407 System.out.println("P[" + i + "] = " + P.get(i).toString(var)); 408 System.out.println(); 409 } 410 } 411 412 413 /** 414 * example10. Hermite polynomials 415 * 416 * H(0) = 1 H(1) = 2 x H(n) = 2 * x * H(n-1) - 2 * (n-1) * H(n-2) 417 */ 418 // H(n+1) = 2 * x * H(n) - 2 * n * H(n-1) 419 public static void example10() { 420 int n = 100; 421 422 BigInteger fac = new BigInteger(); 423 String[] var = new String[] { "x" }; 424 425 GenPolynomialRing<BigInteger> ring = new GenPolynomialRing<BigInteger>(fac, 1, var); 426 427 List<GenPolynomial<BigInteger>> H = new ArrayList<GenPolynomial<BigInteger>>(n); 428 429 GenPolynomial<BigInteger> t, one, x2, xc, x; 430 BigInteger n2, nn; 431 432 one = ring.getONE(); 433 x = ring.univariate(0); 434 n2 = new BigInteger(2); 435 x2 = x.multiply(n2); 436 H.add(one); 437 H.add(x2); 438 for (int i = 2; i < n; i++) { 439 t = x2.multiply(H.get(i - 1)); 440 nn = new BigInteger(2 * (i - 1)); 441 xc = H.get(i - 2).multiply(nn); 442 t = t.subtract(xc); 443 H.add(t); 444 } 445 for (int i = n - 1; i < n; i++) { 446 System.out.println("H[" + i + "] = " + H.get(i).toString(var)); 447 System.out.println(); 448 } 449 } 450 451 452 /** 453 * example11. degree matrix; 454 * 455 */ 456 @SuppressWarnings("cast") 457 public static void example11() { 458 int n = 50; 459 BigRational fac = new BigRational(); 460 GenPolynomialRing<BigRational> ring = new GenPolynomialRing<BigRational>(fac, n); 461 System.out.println("ring = " + ring + "\n"); 462 463 GenPolynomial<BigRational> p = ring.random(5, 3, 6, 0.5f); 464 System.out.println("p = " + p + "\n"); 465 466 List<GenPolynomial<BigInteger>> dem = TermOrderOptimization.<BigRational> degreeMatrix(p); 467 468 System.out.println("dem = " + dem + "\n"); 469 470 List<GenPolynomial<BigRational>> polys = new ArrayList<GenPolynomial<BigRational>>(); 471 polys.add(p); 472 for (int i = 0; i < 5; i++) { 473 polys.add(ring.random(5, 3, 6, 0.1f)); 474 } 475 System.out.println("polys = " + polys + "\n"); 476 477 dem = TermOrderOptimization.<BigRational> degreeMatrix(polys); 478 System.out.println("dem = " + dem + "\n"); 479 480 List<Integer> perm; 481 perm = TermOrderOptimization.optimalPermutation(dem); 482 System.out.println("perm = " + perm + "\n"); 483 484 List<GenPolynomial<BigInteger>> pdem; 485 pdem = TermOrderOptimization.<GenPolynomial<BigInteger>> listPermutation(perm, dem); 486 System.out.println("pdem = " + pdem + "\n"); 487 488 GenPolynomialRing<BigRational> pring; 489 pring = TermOrderOptimization.<BigRational> permutation(perm, ring); 490 System.out.println("ring = " + ring); 491 System.out.println("pring = " + pring + "\n"); 492 493 List<GenPolynomial<BigRational>> ppolys; 494 ppolys = TermOrderOptimization.<BigRational> permutation(perm, pring, polys); 495 System.out.println("ppolys = " + ppolys + "\n"); 496 497 dem = TermOrderOptimization.<BigRational> degreeMatrix(ppolys); 498 //System.out.println("pdem = " + dem + "\n"); 499 500 perm = TermOrderOptimization.optimalPermutation(dem); 501 //System.out.println("pperm = " + perm + "\n"); 502 int i = 0; 503 for (Integer j : perm) { 504 if (i != (int) j) { 505 System.out.println("error = " + i + " != " + j + "\n"); 506 } 507 i++; 508 } 509 510 OptimizedPolynomialList<BigRational> op; 511 op = TermOrderOptimization.<BigRational> optimizeTermOrder(ring, polys); 512 System.out.println("op:\n" + op); 513 if (!op.equals(new PolynomialList<BigRational>(pring, ppolys))) { 514 System.out.println("error = " + "\n" + op); 515 } 516 } 517 518 519 /** 520 * example12. type games. 521 */ 522 public static void example12() { 523 System.out.println("\n\n example 12"); 524 525 BigRational t1 = new BigRational(); 526 System.out.println("t1 = " + t1); 527 528 BigInteger t2 = new BigInteger(); 529 System.out.println("t2 = " + t2); 530 531 System.out.println("t1.isAssignableFrom(t2) = " + t1.getClass().isAssignableFrom(t2.getClass())); 532 System.out.println("t2.isAssignableFrom(t1) = " + t2.getClass().isAssignableFrom(t1.getClass())); 533 534 GenPolynomialRing<BigInteger> t3 = new GenPolynomialRing<BigInteger>(t2, 3); 535 System.out.println("t3 = " + t3); 536 537 GenSolvablePolynomialRing<BigInteger> t4 = new GenSolvablePolynomialRing<BigInteger>(t2, 3); 538 System.out.println("t4 = " + t4); 539 540 System.out.println("t3.isAssignableFrom(t4) = " + t3.getClass().isAssignableFrom(t4.getClass())); 541 System.out.println("t4.isAssignableFrom(t3) = " + t4.getClass().isAssignableFrom(t3.getClass())); 542 543 544 GenPolynomialRing<BigRational> t5 = new GenPolynomialRing<BigRational>(t1, 3); 545 System.out.println("t5 = " + t5); 546 547 System.out.println("t3.isAssignableFrom(t5) = " + t3.getClass().isAssignableFrom(t5.getClass())); 548 System.out.println("t5.isAssignableFrom(t3) = " + t5.getClass().isAssignableFrom(t3.getClass())); 549 } 550 551 552 /** 553 * example13. poly parser for strange syntax. 554 */ 555 public static void example13() { 556 System.out.println("\n\n example 13"); 557 TermOrder to = new TermOrder(TermOrder.INVLEX); 558 BigRational cfraction = new BigRational(1); 559 String[] vars = new String[] { "x" }; 560 561 //Scripting.setPrecision(5); 562 563 GenPolynomialRing<BigRational> pfac 564 = new GenPolynomialRing<BigRational>(cfraction, 1, to, vars); 565 GenPolynomial<BigRational> FF0 = pfac.parse("19(6)/10"); 566 System.out.println("FF0 = " + FF0); 567 FF0 = pfac.parse("19(6)1/10"); 568 System.out.println("FF0 = " + FF0); 569 FF0 = pfac.parse("19 6/10"); 570 System.out.println("FF0 = " + FF0); 571 FF0 = pfac.parse("19*6/10"); 572 System.out.println("FF0 = " + FF0); 573 FF0 = pfac.parse("19+6/10"); 574 System.out.println("FF0 = " + FF0); 575 FF0 = pfac.parse("(x).2"); 576 System.out.println("FF0 = " + FF0); 577 FF0 = pfac.parse("4.0/9.0"); 578 System.out.println("FF0 = " + FF0); 579 FF0 = pfac.parse("4/9.0"); 580 System.out.println("FF0 = " + FF0); 581 FF0 = pfac.parse("4.0/9"); 582 System.out.println("FF0 = " + FF0); 583 FF0 = pfac.parse("-4.0/9"); 584 System.out.println("FF0 = " + FF0); 585 } 586}