001/* 002 * $Id: UnivPowerSeriesRing.java 4655 2013-10-05 10:12:32Z kredel $ 003 */ 004 005package edu.jas.ps; 006 007 008import java.io.Reader; 009import java.util.ArrayList; 010import java.util.HashMap; 011import java.util.List; 012import java.util.Random; 013 014import edu.jas.poly.GenPolynomial; 015import edu.jas.poly.GenPolynomialRing; 016import edu.jas.poly.Monomial; 017import edu.jas.structure.RingElem; 018import edu.jas.structure.RingFactory; 019 020 021/** 022 * Univariate power series ring implementation. Uses lazy evaluated generating 023 * function for coefficients. 024 * @param <C> ring element type 025 * @author Heinz Kredel 026 */ 027 028public class UnivPowerSeriesRing<C extends RingElem<C>> implements RingFactory<UnivPowerSeries<C>> { 029 030 031 /** 032 * A default random sequence generator. 033 */ 034 protected final static Random random = new Random(); 035 036 037 /** 038 * Default truncate. 039 */ 040 public final static int DEFAULT_TRUNCATE = 11; 041 042 043 /** 044 * Truncate. 045 */ 046 int truncate; 047 048 049 /** 050 * Default variable name. 051 */ 052 public final static String DEFAULT_NAME = "x"; 053 054 055 /** 056 * Variable name. 057 */ 058 String var; 059 060 061 /** 062 * Coefficient ring factory. 063 */ 064 public final RingFactory<C> coFac; 065 066 067 /** 068 * The constant power series 1 for this ring. 069 */ 070 public final UnivPowerSeries<C> ONE; 071 072 073 /** 074 * The constant power series 0 for this ring. 075 */ 076 public final UnivPowerSeries<C> ZERO; 077 078 079 /** 080 * No argument constructor. 081 */ 082 @SuppressWarnings("unused") 083 private UnivPowerSeriesRing() { 084 throw new IllegalArgumentException("do not use no-argument constructor"); 085 } 086 087 088 /** 089 * Constructor. 090 * @param coFac coefficient ring factory. 091 */ 092 public UnivPowerSeriesRing(RingFactory<C> coFac) { 093 this(coFac, DEFAULT_TRUNCATE, DEFAULT_NAME); 094 } 095 096 097 /** 098 * Constructor. 099 * @param coFac coefficient ring factory. 100 * @param truncate index of truncation. 101 */ 102 public UnivPowerSeriesRing(RingFactory<C> coFac, int truncate) { 103 this(coFac, truncate, DEFAULT_NAME); 104 } 105 106 107 /** 108 * Constructor. 109 * @param coFac coefficient ring factory. 110 * @param name of the variable. 111 */ 112 public UnivPowerSeriesRing(RingFactory<C> coFac, String name) { 113 this(coFac, DEFAULT_TRUNCATE, name); 114 } 115 116 117 /** 118 * Constructor. 119 * @param pfac polynomial ring factory. 120 */ 121 public UnivPowerSeriesRing(GenPolynomialRing<C> pfac) { 122 this(pfac.coFac, DEFAULT_TRUNCATE, pfac.getVars()[0]); 123 } 124 125 126 /** 127 * Constructor. 128 * @param cofac coefficient ring factory. 129 * @param truncate index of truncation. 130 * @param name of the variable. 131 */ 132 public UnivPowerSeriesRing(RingFactory<C> cofac, int truncate, String name) { 133 this.coFac = cofac; 134 this.truncate = truncate; 135 this.var = name; 136 this.ONE = new UnivPowerSeries<C>(this, new Coefficients<C>() { 137 138 139 @Override 140 public C generate(int i) { 141 if (i == 0) { 142 return coFac.getONE(); 143 } 144 return coFac.getZERO(); 145 } 146 }); 147 this.ZERO = new UnivPowerSeries<C>(this, new Coefficients<C>() { 148 149 150 @Override 151 public C generate(int i) { 152 return coFac.getZERO(); 153 } 154 }); 155 } 156 157 158 /** 159 * Fixed point construction. 160 * @param map a mapping of power series. 161 * @return fix point wrt map. 162 */ 163 // Cannot be a static method because a power series ring is required. 164 public UnivPowerSeries<C> fixPoint(UnivPowerSeriesMap<C> map) { 165 UnivPowerSeries<C> ps1 = new UnivPowerSeries<C>(this); 166 UnivPowerSeries<C> ps2 = map.map(ps1); 167 ps1.lazyCoeffs = ps2.lazyCoeffs; 168 return ps2; 169 } 170 171 172 /** 173 * To String. 174 * @return string representation of this. 175 */ 176 @Override 177 public String toString() { 178 StringBuffer sb = new StringBuffer(); 179 String scf = coFac.getClass().getSimpleName(); 180 sb.append(scf + "((" + var + "))"); 181 return sb.toString(); 182 } 183 184 185 /** 186 * Get a scripting compatible string representation. 187 * @return script compatible representation for this ElemFactory. 188 * @see edu.jas.structure.ElemFactory#toScript() 189 */ 190 @Override 191 public String toScript() { 192 // Python case 193 StringBuffer s = new StringBuffer("PS("); 194 String f = null; 195 try { 196 f = ((RingElem<C>) coFac).toScriptFactory(); // sic 197 } catch (Exception e) { 198 f = coFac.toScript(); 199 } 200 s.append(f + ",\"" + var + "\"," + truncate + ")"); 201 return s.toString(); 202 } 203 204 205 /** 206 * Comparison with any other object. 207 * @see java.lang.Object#equals(java.lang.Object) 208 */ 209 @Override 210 @SuppressWarnings("unchecked") 211 public boolean equals(Object B) { 212 UnivPowerSeriesRing<C> a = null; 213 try { 214 a = (UnivPowerSeriesRing<C>) B; 215 } catch (ClassCastException ignored) { 216 } 217 if (a == null) { 218 return false; 219 } 220 if (!coFac.equals(a.coFac)) { 221 return false; 222 } 223 if (!var.equals(a.var)) { 224 return false; 225 } 226 return true; 227 } 228 229 230 /** 231 * Hash code for this . 232 * @see java.lang.Object#hashCode() 233 */ 234 @Override 235 public int hashCode() { 236 int h = coFac.hashCode(); 237 h += (var.hashCode() << 27); 238 h += truncate; 239 return h; 240 } 241 242 243 /** 244 * Get the zero element. 245 * @return 0 as UnivPowerSeries<C>. 246 */ 247 public UnivPowerSeries<C> getZERO() { 248 return ZERO; 249 } 250 251 252 /** 253 * Get the one element. 254 * @return 1 as UnivPowerSeries<C>. 255 */ 256 public UnivPowerSeries<C> getONE() { 257 return ONE; 258 } 259 260 261 /** 262 * Get a list of the generating elements. 263 * @return list of generators for the algebraic structure. 264 * @see edu.jas.structure.ElemFactory#generators() 265 */ 266 public List<UnivPowerSeries<C>> generators() { 267 List<C> rgens = coFac.generators(); 268 List<UnivPowerSeries<C>> gens = new ArrayList<UnivPowerSeries<C>>(rgens.size()); 269 for (final C cg : rgens) { 270 UnivPowerSeries<C> g = new UnivPowerSeries<C>(this, new Coefficients<C>() { 271 272 273 @Override 274 public C generate(int i) { 275 if (i == 0) { 276 return cg; 277 } 278 return coFac.getZERO(); 279 } 280 }); 281 gens.add(g); 282 } 283 gens.add(ONE.shift(1)); 284 return gens; 285 } 286 287 288 /** 289 * Is this structure finite or infinite. 290 * @return true if this structure is finite, else false. 291 * @see edu.jas.structure.ElemFactory#isFinite() 292 */ 293 public boolean isFinite() { 294 return false; 295 } 296 297 298 /** 299 * Get the power series of the exponential function. 300 * @return exp(x) as UnivPowerSeries<C>. 301 */ 302 public UnivPowerSeries<C> getEXP() { 303 return fixPoint(new UnivPowerSeriesMap<C>() { 304 305 306 public UnivPowerSeries<C> map(UnivPowerSeries<C> e) { 307 return e.integrate(coFac.getONE()); 308 } 309 }); 310 } 311 312 313 /** 314 * Get the power series of the sinus function. 315 * @return sin(x) as UnivPowerSeries<C>. 316 */ 317 public UnivPowerSeries<C> getSIN() { 318 return fixPoint(new UnivPowerSeriesMap<C>() { 319 320 321 public UnivPowerSeries<C> map(UnivPowerSeries<C> s) { 322 return s.negate().integrate(coFac.getONE()).integrate(coFac.getZERO()); 323 } 324 }); 325 } 326 327 328 /** 329 * Get the power series of the cosine function. 330 * @return cos(x) as UnivPowerSeries<C>. 331 */ 332 public UnivPowerSeries<C> getCOS() { 333 return fixPoint(new UnivPowerSeriesMap<C>() { 334 335 336 public UnivPowerSeries<C> map(UnivPowerSeries<C> c) { 337 return c.negate().integrate(coFac.getZERO()).integrate(coFac.getONE()); 338 } 339 }); 340 } 341 342 343 /** 344 * Get the power series of the tangens function. 345 * @return tan(x) as UnivPowerSeries<C>. 346 */ 347 public UnivPowerSeries<C> getTAN() { 348 return fixPoint(new UnivPowerSeriesMap<C>() { 349 350 351 public UnivPowerSeries<C> map(UnivPowerSeries<C> t) { 352 return t.multiply(t).sum(getONE()).integrate(coFac.getZERO()); 353 } 354 }); 355 } 356 357 358 /** 359 * Solve an ordinary differential equation. y' = f(y) with y(0) = c. 360 * @param f a UnivPowerSeries<C>. 361 * @param c integration constant. 362 * @return f.integrate(c). 363 */ 364 public UnivPowerSeries<C> solveODE(final UnivPowerSeries<C> f, final C c) { 365 return f.integrate(c); 366 } 367 368 369 /** 370 * Is commutative. 371 * @return true, if this ring is commutative, else false. 372 */ 373 public boolean isCommutative() { 374 return coFac.isCommutative(); 375 } 376 377 378 /** 379 * Query if this ring is associative. 380 * @return true if this ring is associative, else false. 381 */ 382 public boolean isAssociative() { 383 return coFac.isAssociative(); 384 } 385 386 387 /** 388 * Query if this ring is a field. 389 * @return false. 390 */ 391 public boolean isField() { 392 return false; 393 } 394 395 396 /** 397 * Characteristic of this ring. 398 * @return characteristic of this ring. 399 */ 400 public java.math.BigInteger characteristic() { 401 return coFac.characteristic(); 402 } 403 404 405 /** 406 * Get a (constant) UnivPowerSeries<C> from a long value. 407 * @param a long. 408 * @return a UnivPowerSeries<C>. 409 */ 410 public UnivPowerSeries<C> fromInteger(long a) { 411 return ONE.multiply(coFac.fromInteger(a)); 412 } 413 414 415 /** 416 * Get a (constant) UnivPowerSeries<C> from a java.math.BigInteger. 417 * @param a BigInteger. 418 * @return a UnivPowerSeries<C>. 419 */ 420 public UnivPowerSeries<C> fromInteger(java.math.BigInteger a) { 421 return ONE.multiply(coFac.fromInteger(a)); 422 } 423 424 425 /** 426 * Get the corresponding GenPolynomialRing<C>. 427 * @return GenPolynomialRing<C>. 428 */ 429 public GenPolynomialRing<C> polyRing() { 430 return new GenPolynomialRing<C>(coFac, 1, new String[] { var }); 431 } 432 433 434 /** 435 * Get a UnivPowerSeries<C> from a GenPolynomial<C>. 436 * @param a GenPolynomial<C>. 437 * @return a UnivPowerSeries<C>. 438 */ 439 public UnivPowerSeries<C> fromPolynomial(GenPolynomial<C> a) { 440 if (a == null || a.isZERO()) { 441 return ZERO; 442 } 443 if (a.isONE()) { 444 return ONE; 445 } 446 if (a.ring.nvar != 1) { 447 throw new IllegalArgumentException("only for univariate polynomials"); 448 } 449 HashMap<Integer, C> cache = new HashMap<Integer, C>(a.length()); 450 for (Monomial<C> m : a) { 451 long e = m.exponent().getVal(0); 452 cache.put((int) e, m.coefficient()); 453 } 454 return new UnivPowerSeries<C>(this, new Coefficients<C>(cache) { 455 456 457 @Override 458 public C generate(int i) { 459 // cached coefficients returned by get 460 return coFac.getZERO(); 461 } 462 }); 463 } 464 465 466 /** 467 * Generate a random power series with k = 5, d = 0.7. 468 * @return a random power series. 469 */ 470 public UnivPowerSeries<C> random() { 471 return random(5, 0.7f, random); 472 } 473 474 475 /** 476 * Generate a random power series with d = 0.7. 477 * @param k bitsize of random coefficients. 478 * @return a random power series. 479 */ 480 public UnivPowerSeries<C> random(int k) { 481 return random(k, 0.7f, random); 482 } 483 484 485 /** 486 * Generate a random power series with d = 0.7. 487 * @param k bit-size of random coefficients. 488 * @param rnd is a source for random bits. 489 * @return a random power series. 490 */ 491 public UnivPowerSeries<C> random(int k, Random rnd) { 492 return random(k, 0.7f, rnd); 493 } 494 495 496 /** 497 * Generate a random power series. 498 * @param k bit-size of random coefficients. 499 * @param d density of non-zero coefficients. 500 * @return a random power series. 501 */ 502 public UnivPowerSeries<C> random(int k, float d) { 503 return random(k, d, random); 504 } 505 506 507 /** 508 * Generate a random power series. 509 * @param k bit-size of random coefficients. 510 * @param d density of non-zero coefficients. 511 * @param rnd is a source for random bits. 512 * @return a random power series. 513 */ 514 public UnivPowerSeries<C> random(final int k, final float d, final Random rnd) { 515 return new UnivPowerSeries<C>(this, new Coefficients<C>() { 516 517 518 @Override 519 public C generate(int i) { 520 // cached coefficients returned by get 521 C c; 522 float f = rnd.nextFloat(); 523 if (f < d) { 524 c = coFac.random(k, rnd); 525 } else { 526 c = coFac.getZERO(); 527 } 528 return c; 529 } 530 }); 531 } 532 533 534 /** 535 * Copy power series. 536 * @param c a power series. 537 * @return a copy of c. 538 */ 539 public UnivPowerSeries<C> copy(UnivPowerSeries<C> c) { 540 return new UnivPowerSeries<C>(this, c.lazyCoeffs); 541 } 542 543 544 /** 545 * Parse a power series. <b>Note:</b> not implemented. 546 * @param s String. 547 * @return power series from s. 548 */ 549 public UnivPowerSeries<C> parse(String s) { 550 throw new UnsupportedOperationException("parse for power series not implemented"); 551 } 552 553 554 /** 555 * Parse a power series. <b>Note:</b> not implemented. 556 * @param r Reader. 557 * @return next power series from r. 558 */ 559 public UnivPowerSeries<C> parse(Reader r) { 560 throw new UnsupportedOperationException("parse for power series not implemented"); 561 } 562 563 564 /** 565 * Taylor power series. 566 * @param f function. 567 * @param a expansion point. 568 * @return Taylor series of f. 569 */ 570 public UnivPowerSeries<C> seriesOfTaylor(final TaylorFunction<C> f, final C a) { 571 return new UnivPowerSeries<C>(this, new Coefficients<C>() { 572 573 574 TaylorFunction<C> der = f; 575 576 577 long k = 0; 578 579 580 long n = 1; 581 582 583 @Override 584 public C generate(int i) { 585 C c; 586 if (i == 0) { 587 c = der.evaluate(a); 588 der = der.deriviative(); 589 return c; 590 } 591 if (i > 0) { 592 c = get(i - 1); // ensure deriv is updated 593 } 594 k++; 595 n *= k; 596 c = der.evaluate(a); 597 //System.out.println("n = " + n + ", i = " +i); 598 c = c.divide(coFac.fromInteger(n)); 599 der = der.deriviative(); 600 return c; 601 } 602 }); 603 } 604 605}