001 /*
002 * $Id: UnivPowerSeriesRing.java 3337 2010-09-27 21:05:17Z kredel $
003 */
004
005 package edu.jas.ps;
006
007
008 import java.io.Reader;
009 import java.util.ArrayList;
010 import java.util.HashMap;
011 import java.util.List;
012 import java.util.Random;
013
014 import edu.jas.poly.GenPolynomial;
015 import edu.jas.poly.GenPolynomialRing;
016 import edu.jas.poly.Monomial;
017 import edu.jas.structure.RingElem;
018 import 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
028 public 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 //JAVA6only: @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 if (!(B instanceof UnivPowerSeriesRing)) {
213 return false;
214 }
215 UnivPowerSeriesRing<C> a = null;
216 try {
217 a = (UnivPowerSeriesRing<C>) B;
218 } catch (ClassCastException ignored) {
219 }
220 if (var.equals(a.var)) {
221 return true;
222 }
223 return false;
224 }
225
226
227 /**
228 * Hash code for this .
229 * @see java.lang.Object#hashCode()
230 */
231 @Override
232 public int hashCode() {
233 int h = 0;
234 h = (var.hashCode() << 27);
235 h += truncate;
236 return h;
237 }
238
239
240 /**
241 * Get the zero element.
242 * @return 0 as UnivPowerSeries<C>.
243 */
244 public UnivPowerSeries<C> getZERO() {
245 return ZERO;
246 }
247
248
249 /**
250 * Get the one element.
251 * @return 1 as UnivPowerSeries<C>.
252 */
253 public UnivPowerSeries<C> getONE() {
254 return ONE;
255 }
256
257
258 /**
259 * Get a list of the generating elements.
260 * @return list of generators for the algebraic structure.
261 * @see edu.jas.structure.ElemFactory#generators()
262 */
263 public List<UnivPowerSeries<C>> generators() {
264 List<C> rgens = coFac.generators();
265 List<UnivPowerSeries<C>> gens = new ArrayList<UnivPowerSeries<C>>(rgens.size());
266 for (final C cg : rgens) {
267 UnivPowerSeries<C> g = new UnivPowerSeries<C>(this, new Coefficients<C>() {
268
269
270 @Override
271 public C generate(int i) {
272 if (i == 0) {
273 return cg;
274 }
275 return coFac.getZERO();
276 }
277 });
278 gens.add(g);
279 }
280 gens.add(ONE.shift(1));
281 return gens;
282 }
283
284
285 /**
286 * Is this structure finite or infinite.
287 * @return true if this structure is finite, else false.
288 * @see edu.jas.structure.ElemFactory#isFinite()
289 */
290 public boolean isFinite() {
291 return false;
292 }
293
294
295 /**
296 * Get the power series of the exponential function.
297 * @return exp(x) as UnivPowerSeries<C>.
298 */
299 public UnivPowerSeries<C> getEXP() {
300 return fixPoint(new UnivPowerSeriesMap<C>() {
301
302
303 public UnivPowerSeries<C> map(UnivPowerSeries<C> e) {
304 return e.integrate(coFac.getONE());
305 }
306 });
307 }
308
309
310 /**
311 * Get the power series of the sinus function.
312 * @return sin(x) as UnivPowerSeries<C>.
313 */
314 public UnivPowerSeries<C> getSIN() {
315 return fixPoint(new UnivPowerSeriesMap<C>() {
316
317
318 public UnivPowerSeries<C> map(UnivPowerSeries<C> s) {
319 return s.negate().integrate(coFac.getONE()).integrate(coFac.getZERO());
320 }
321 });
322 }
323
324
325 /**
326 * Get the power series of the cosine function.
327 * @return cos(x) as UnivPowerSeries<C>.
328 */
329 public UnivPowerSeries<C> getCOS() {
330 return fixPoint(new UnivPowerSeriesMap<C>() {
331
332
333 public UnivPowerSeries<C> map(UnivPowerSeries<C> c) {
334 return c.negate().integrate(coFac.getZERO()).integrate(coFac.getONE());
335 }
336 });
337 }
338
339
340 /**
341 * Get the power series of the tangens function.
342 * @return tan(x) as UnivPowerSeries<C>.
343 */
344 public UnivPowerSeries<C> getTAN() {
345 return fixPoint(new UnivPowerSeriesMap<C>() {
346
347
348 public UnivPowerSeries<C> map(UnivPowerSeries<C> t) {
349 return t.multiply(t).sum(getONE()).integrate(coFac.getZERO());
350 }
351 });
352 }
353
354
355 /**
356 * Solve an ordinary differential equation. y' = f(y) with y(0) = c.
357 * @param f a UnivPowerSeries<C>.
358 * @param c integration constant.
359 * @return f.integrate(c).
360 */
361 public UnivPowerSeries<C> solveODE(final UnivPowerSeries<C> f, final C c) {
362 return f.integrate(c);
363 }
364
365
366 /**
367 * Is commutative.
368 * @return true, if this ring is commutative, else false.
369 */
370 public boolean isCommutative() {
371 return coFac.isCommutative();
372 }
373
374
375 /**
376 * Query if this ring is associative.
377 * @return true if this ring is associative, else false.
378 */
379 public boolean isAssociative() {
380 return coFac.isAssociative();
381 }
382
383
384 /**
385 * Query if this ring is a field.
386 * @return false.
387 */
388 public boolean isField() {
389 return false;
390 }
391
392
393 /**
394 * Characteristic of this ring.
395 * @return characteristic of this ring.
396 */
397 public java.math.BigInteger characteristic() {
398 return coFac.characteristic();
399 }
400
401
402 /**
403 * Get a (constant) UnivPowerSeries<C> from a long value.
404 * @param a long.
405 * @return a UnivPowerSeries<C>.
406 */
407 public UnivPowerSeries<C> fromInteger(long a) {
408 return ONE.multiply(coFac.fromInteger(a));
409 }
410
411
412 /**
413 * Get a (constant) UnivPowerSeries<C> from a java.math.BigInteger.
414 * @param a BigInteger.
415 * @return a UnivPowerSeries<C>.
416 */
417 public UnivPowerSeries<C> fromInteger(java.math.BigInteger a) {
418 return ONE.multiply(coFac.fromInteger(a));
419 }
420
421
422 /**
423 * Get the corresponding GenPolynomialRing<C>.
424 * @return GenPolynomialRing<C>.
425 */
426 public GenPolynomialRing<C> polyRing() {
427 return new GenPolynomialRing<C>(coFac, 1, new String[] { var });
428 }
429
430
431 /**
432 * Get a UnivPowerSeries<C> from a GenPolynomial<C>.
433 * @param a GenPolynomial<C>.
434 * @return a UnivPowerSeries<C>.
435 */
436 public UnivPowerSeries<C> fromPolynomial(GenPolynomial<C> a) {
437 if (a == null || a.isZERO()) {
438 return ZERO;
439 }
440 if (a.isONE()) {
441 return ONE;
442 }
443 if (a.ring.nvar != 1) {
444 throw new IllegalArgumentException("only for univariate polynomials");
445 }
446 HashMap<Integer, C> cache = new HashMap<Integer, C>(a.length());
447 for (Monomial<C> m : a) {
448 long e = m.exponent().getVal(0);
449 cache.put((int) e, m.coefficient());
450 }
451 return new UnivPowerSeries<C>(this, new Coefficients<C>(cache) {
452
453
454 @Override
455 public C generate(int i) {
456 // cached coefficients returned by get
457 return coFac.getZERO();
458 }
459 });
460 }
461
462
463 /**
464 * Generate a random power series with k = 5, d = 0.7.
465 * @return a random power series.
466 */
467 public UnivPowerSeries<C> random() {
468 return random(5, 0.7f, random);
469 }
470
471
472 /**
473 * Generate a random power series with d = 0.7.
474 * @param k bitsize of random coefficients.
475 * @return a random power series.
476 */
477 public UnivPowerSeries<C> random(int k) {
478 return random(k, 0.7f, random);
479 }
480
481
482 /**
483 * Generate a random power series with d = 0.7.
484 * @param k bit-size of random coefficients.
485 * @param rnd is a source for random bits.
486 * @return a random power series.
487 */
488 public UnivPowerSeries<C> random(int k, Random rnd) {
489 return random(k, 0.7f, rnd);
490 }
491
492
493 /**
494 * Generate a random power series.
495 * @param k bit-size of random coefficients.
496 * @param d density of non-zero coefficients.
497 * @return a random power series.
498 */
499 public UnivPowerSeries<C> random(int k, float d) {
500 return random(k, d, random);
501 }
502
503
504 /**
505 * Generate a random power series.
506 * @param k bit-size of random coefficients.
507 * @param d density of non-zero coefficients.
508 * @param rnd is a source for random bits.
509 * @return a random power series.
510 */
511 public UnivPowerSeries<C> random(final int k, final float d, final Random rnd) {
512 return new UnivPowerSeries<C>(this, new Coefficients<C>() {
513
514
515 @Override
516 public C generate(int i) {
517 // cached coefficients returned by get
518 C c;
519 float f = rnd.nextFloat();
520 if (f < d) {
521 c = coFac.random(k, rnd);
522 } else {
523 c = coFac.getZERO();
524 }
525 return c;
526 }
527 });
528 }
529
530
531 /**
532 * Copy power series.
533 * @param c a power series.
534 * @return a copy of c.
535 */
536 public UnivPowerSeries<C> copy(UnivPowerSeries<C> c) {
537 return new UnivPowerSeries<C>(this, c.lazyCoeffs);
538 }
539
540
541 /**
542 * Parse a power series. <b>Note:</b> not implemented.
543 * @param s String.
544 * @return power series from s.
545 */
546 public UnivPowerSeries<C> parse(String s) {
547 throw new UnsupportedOperationException("parse for power series not implemented");
548 }
549
550
551 /**
552 * Parse a power series. <b>Note:</b> not implemented.
553 * @param r Reader.
554 * @return next power series from r.
555 */
556 public UnivPowerSeries<C> parse(Reader r) {
557 throw new UnsupportedOperationException("parse for power series not implemented");
558 }
559
560
561 /**
562 * Taylor power series.
563 * @param f function.
564 * @param a expansion point.
565 * @return Taylor series of f.
566 */
567 public UnivPowerSeries<C> seriesOfTaylor(final TaylorFunction<C> f, final C a) {
568 return new UnivPowerSeries<C>(this, new Coefficients<C>() {
569
570
571 TaylorFunction<C> der = f;
572
573
574 long k = 0;
575
576
577 long n = 1;
578
579
580 @Override
581 public C generate(int i) {
582 C c;
583 if (i == 0) {
584 c = der.evaluate(a);
585 der = der.deriviative();
586 return c;
587 }
588 if (i > 0) {
589 c = get(i - 1); // ensure deriv is updated
590 }
591 k++;
592 n *= k;
593 c = der.evaluate(a);
594 //System.out.println("n = " + n + ", i = " +i);
595 c = c.divide(coFac.fromInteger(n));
596 der = der.deriviative();
597 return c;
598 }
599 });
600 }
601
602 }