/*
* $Id$
*/
package edu.jas.ps;
import edu.jas.poly.AlgebraicNumber;
import edu.jas.poly.ExpVector;
import edu.jas.poly.GenPolynomial;
import edu.jas.structure.BinaryFunctor;
import edu.jas.structure.RingElem;
import edu.jas.structure.Selector;
import edu.jas.structure.UnaryFunctor;
/**
* Univariate power series implementation. Uses inner classes and lazy evaluated
* generating function for coefficients. All ring element methods use lazy
* evaluation except where noted otherwise. Eager evaluated methods are
* toString(), compareTo(), equals(),
* evaluate(), or they use the order() method, like
* signum(), abs(), divide(),
* remainder() and gcd().
* @param ring element type
* @author Heinz Kredel
*/
public class UnivPowerSeries> implements RingElem> {
/**
* Power series ring factory.
*/
public final UnivPowerSeriesRing ring;
/**
* Data structure / generating function for coeffcients. Cannot be final
* because of fixPoint, must be accessible in factory.
*/
/*package*/Coefficients lazyCoeffs;
/**
* Truncation of computations.
*/
private int truncate = 11;
/**
* Order of power series.
*/
private int order = -1; // == unknown
/**
* Private constructor.
*/
@SuppressWarnings("unused")
private UnivPowerSeries() {
throw new IllegalArgumentException("do not use no-argument constructor");
}
/**
* Package constructor. Use in fixPoint only, must be accessible in factory.
* @param ring power series ring.
*/
/*package*/UnivPowerSeries(UnivPowerSeriesRing ring) {
this.ring = ring;
this.lazyCoeffs = null;
}
/**
* Constructor.
* @param ring power series ring.
* @param lazyCoeffs generating function for coefficients.
*/
public UnivPowerSeries(UnivPowerSeriesRing ring, Coefficients lazyCoeffs) {
if (lazyCoeffs == null || ring == null) {
throw new IllegalArgumentException("null not allowed: ring = " + ring + ", lazyCoeffs = "
+ lazyCoeffs);
}
this.ring = ring;
this.lazyCoeffs = lazyCoeffs;
this.truncate = ring.truncate;
}
/**
* Get the corresponding element factory.
* @return factory for this Element.
* @see edu.jas.structure.Element#factory()
*/
public UnivPowerSeriesRing factory() {
return ring;
}
/**
* Clone this power series.
* @see java.lang.Object#clone()
*/
@Override
public UnivPowerSeries copy() {
return new UnivPowerSeries(ring, lazyCoeffs);
}
/**
* String representation of power series.
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return toString(truncate);
}
/**
* To String with given truncate.
* @return string representation of this to given truncate.
*/
public String toString(int truncate) {
StringBuffer sb = new StringBuffer();
UnivPowerSeries s = this;
String var = ring.var;
//System.out.println("cache = " + s.coeffCache);
for (int i = 0; i < truncate; i++) {
C c = s.coefficient(i);
int si = c.signum();
if (si != 0) {
if (si > 0) {
if (sb.length() > 0) {
sb.append(" + ");
}
} else {
c = c.negate();
sb.append(" - ");
}
if (!c.isONE() || i == 0) {
if (c instanceof GenPolynomial || c instanceof AlgebraicNumber) {
sb.append("{ ");
}
sb.append(c.toString());
if (c instanceof GenPolynomial || c instanceof AlgebraicNumber) {
sb.append(" }");
}
if (i > 0) {
sb.append(" * ");
}
}
if (i == 0) {
//skip; sb.append(" ");
} else if (i == 1) {
sb.append(var);
} else {
sb.append(var + "^" + i);
}
//sb.append(c.toString() + ", ");
}
//System.out.println("cache = " + s.coeffCache);
}
if (sb.length() == 0) {
sb.append("0");
}
sb.append(" + BigO(" + var + "^" + truncate + ")");
//sb.append("...");
return sb.toString();
}
/**
* Get a scripting compatible string representation.
* @return script compatible representation for this Element.
* @see edu.jas.structure.Element#toScript()
*/
@Override
public String toScript() {
// Python case
StringBuffer sb = new StringBuffer("");
UnivPowerSeries s = this;
String var = ring.var;
//System.out.println("cache = " + s.coeffCache);
for (int i = 0; i < truncate; i++) {
C c = s.coefficient(i);
int si = c.signum();
if (si != 0) {
if (si > 0) {
if (sb.length() > 0) {
sb.append(" + ");
}
} else {
c = c.negate();
sb.append(" - ");
}
if (!c.isONE() || i == 0) {
if (c instanceof GenPolynomial || c instanceof AlgebraicNumber) {
sb.append("{ ");
}
sb.append(c.toScript());
if (c instanceof GenPolynomial || c instanceof AlgebraicNumber) {
sb.append(" }");
}
if (i > 0) {
sb.append(" * ");
}
}
if (i == 0) {
//skip; sb.append(" ");
} else if (i == 1) {
sb.append(var);
} else {
sb.append(var + "**" + i);
}
//sb.append(c.toString() + ", ");
}
//System.out.println("cache = " + s.coeffCache);
}
if (sb.length() == 0) {
sb.append("0");
}
// sb.append("," + truncate + "");
return sb.toString();
}
/**
* Get a scripting compatible string representation of the factory.
* @return script compatible representation for this ElemFactory.
* @see edu.jas.structure.Element#toScriptFactory()
*/
@Override
public String toScriptFactory() {
// Python case
return factory().toScript();
}
/**
* Get coefficient.
* @param index number of requested coefficient.
* @return coefficient at index.
*/
public C coefficient(int index) {
if (index < 0) {
throw new IndexOutOfBoundsException("negative index not allowed");
}
//System.out.println("cache = " + coeffCache);
return lazyCoeffs.get(index);
}
/**
* Get a GenPolynomial<C> from this.
* @return a GenPolynomial<C> from this up to truncate parts.
*/
public GenPolynomial asPolynomial() {
GenPolynomial p = ring.polyRing().getZERO();
for (int i = 0; i <= truncate; i++) {
C c = coefficient(i);
ExpVector e = ExpVector.create(1, 0, i);
p = p.sum(c, e);
}
return p;
}
/**
* Leading base coefficient.
* @return first coefficient.
*/
public C leadingCoefficient() {
return coefficient(0);
}
/**
* Reductum.
* @return this - leading monomial.
*/
public UnivPowerSeries reductum() {
return new UnivPowerSeries(ring, new Coefficients() {
@Override
public C generate(int i) {
return coefficient(i + 1);
}
});
}
/**
* Prepend a new leading coefficient.
* @param h new coefficient.
* @return new power series.
*/
public UnivPowerSeries prepend(final C h) {
return new UnivPowerSeries(ring, new Coefficients() {
@Override
public C generate(int i) {
if (i == 0) {
return h;
}
return coefficient(i - 1);
}
});
}
/**
* Shift coefficients.
* @param k shift index.
* @return new power series with coefficient(i) = old.coefficient(i-k).
*/
public UnivPowerSeries shift(final int k) {
return new UnivPowerSeries(ring, new Coefficients() {
@Override
public C generate(int i) {
if (i - k < 0) {
return ring.coFac.getZERO();
}
return coefficient(i - k);
}
});
}
/**
* Select coefficients.
* @param sel selector functor.
* @return new power series with selected coefficients.
*/
public UnivPowerSeries select(final Selector sel) {
return new UnivPowerSeries(ring, new Coefficients() {
@Override
public C generate(int i) {
C c = coefficient(i);
if (sel.select(c)) {
return c;
}
return ring.coFac.getZERO();
}
});
}
/**
* Shift select coefficients. Not selected coefficients are removed from the
* result series.
* @param sel selector functor.
* @return new power series with shifted selected coefficients.
*/
public UnivPowerSeries shiftSelect(final Selector sel) {
return new UnivPowerSeries(ring, new Coefficients() {
int pos = 0;
@Override
public C generate(int i) {
C c;
if (i > 0) {
c = get(i - 1); // ensure coeffs are all generated
}
do {
c = coefficient(pos++);
} while (!sel.select(c));
return c;
}
});
}
/**
* Map a unary function to this power series.
* @param f evaluation functor.
* @return new power series with coefficients f(this(i)).
*/
public UnivPowerSeries map(final UnaryFunctor f) {
return new UnivPowerSeries(ring, new Coefficients() {
@Override
public C generate(int i) {
return f.eval(coefficient(i));
}
});
}
/**
* Map a binary function to this and another power series.
* @param f evaluation functor with coefficients f(this(i),other(i)).
* @param ps other power series.
* @return new power series.
*/
public > UnivPowerSeries zip(final BinaryFunctor f,
final UnivPowerSeries ps) {
return new UnivPowerSeries(ring, new Coefficients() {
@Override
public C generate(int i) {
return f.eval(coefficient(i), ps.coefficient(i));
}
});
}
/**
* Sum of two power series.
* @param ps other power series.
* @return this + ps.
*/
public UnivPowerSeries sum(UnivPowerSeries ps) {
return zip(new Sum(), ps);
}
/**
* Subtraction of two power series.
* @param ps other power series.
* @return this - ps.
*/
public UnivPowerSeries subtract(UnivPowerSeries ps) {
return zip(new Subtract(), ps);
}
/**
* Multiply by coefficient.
* @param c coefficient.
* @return this * c.
*/
public UnivPowerSeries multiply(C c) {
return map(new Multiply(c));
}
/**
* Negate.
* @return - this.
*/
public UnivPowerSeries negate() {
return map(new Negate());
}
/**
* Absolute value.
* @return abs(this).
*/
public UnivPowerSeries abs() {
if (signum() < 0) {
return negate();
}
return this;
}
/**
* Evaluate at given point.
* @return ps(c).
*/
public C evaluate(C e) {
C v = coefficient(0);
C p = e;
for (int i = 1; i < truncate; i++) {
C c = coefficient(i).multiply(p);
v = v.sum(c);
p = p.multiply(e);
}
return v;
}
/**
* Order.
* @return index of first non zero coefficient.
*/
public int order() {
if (order < 0) { // compute it
for (int i = 0; i <= truncate; i++) {
if (!coefficient(i).isZERO()) {
order = i;
return order;
}
}
order = truncate + 1;
}
return order;
}
/**
* Truncate.
* @return truncate index of power series.
*/
public int truncate() {
return truncate;
}
/**
* Set truncate.
* @param t new truncate index.
* @return old truncate index of power series.
*/
public int setTruncate(int t) {
if (t < 0) {
throw new IllegalArgumentException("negative truncate not allowed");
}
int ot = truncate;
truncate = t;
return ot;
}
/**
* Signum.
* @return sign of first non zero coefficient.
*/
public int signum() {
return coefficient(order()).signum();
}
/**
* Compare to. Note: compare only up to truncate.
* @return sign of first non zero coefficient of this-ps.
*/
@Override
public int compareTo(UnivPowerSeries ps) {
int m = order();
int n = ps.order();
int pos = (m <= n) ? m : n;
int s = 0;
do {
s = coefficient(pos).compareTo(ps.coefficient(pos));
pos++;
} while (s == 0 && pos <= truncate);
return s;
}
/**
* Is power series zero. Note: compare only up to truncate.
* @return If this is 0 then true is returned, else false.
* @see edu.jas.structure.RingElem#isZERO()
*/
public boolean isZERO() {
return (compareTo(ring.ZERO) == 0);
}
/**
* Is power series one. Note: compare only up to truncate.
* @return If this is 1 then true is returned, else false.
* @see edu.jas.structure.RingElem#isONE()
*/
public boolean isONE() {
return (compareTo(ring.ONE) == 0);
}
/**
* Comparison with any other object. Note: compare only up to
* truncate.
* @see java.lang.Object#equals(java.lang.Object)
*/
@Override
@SuppressWarnings("unchecked")
public boolean equals(Object B) {
UnivPowerSeries a = null;
try {
a = (UnivPowerSeries) B;
} catch (ClassCastException ignored) {
}
if (a == null) {
return false;
}
return compareTo(a) == 0;
}
/**
* Hash code for this polynomial. Note: only up to truncate.
* @see java.lang.Object#hashCode()
*/
@Override
public int hashCode() {
int h = 0;
//h = ( ring.hashCode() << 23 );
//h += val.hashCode();
for (int i = 0; i <= truncate; i++) {
h += coefficient(i).hashCode();
h = (h << 23);
}
return h;
}
/**
* Is unit.
* @return true, if this power series is invertible, else false.
*/
public boolean isUnit() {
return leadingCoefficient().isUnit();
}
/**
* Multiply by another power series.
* @return this * ps.
*/
public UnivPowerSeries multiply(final UnivPowerSeries ps) {
return new UnivPowerSeries(ring, new Coefficients() {
@Override
public C generate(int i) {
C c = null; //fac.getZERO();
for (int k = 0; k <= i; k++) {
C m = coefficient(k).multiply(ps.coefficient(i - k));
if (c == null) {
c = m;
} else {
c = c.sum(m);
}
}
return c;
}
});
}
/**
* Inverse power series.
* @return ps with this * ps = 1.
*/
public UnivPowerSeries inverse() {
return new UnivPowerSeries(ring, new Coefficients() {
@Override
public C generate(int i) {
C d = leadingCoefficient().inverse(); // may fail
if (i == 0) {
return d;
}
C c = null; //fac.getZERO();
for (int k = 0; k < i; k++) {
C m = get(k).multiply(coefficient(i - k));
if (c == null) {
c = m;
} else {
c = c.sum(m);
}
}
c = c.multiply(d.negate());
return c;
}
});
}
/**
* Divide by another power series.
* @return this / ps.
*/
public UnivPowerSeries divide(UnivPowerSeries ps) {
if (ps.isUnit()) {
return multiply(ps.inverse());
}
int m = order();
int n = ps.order();
if (m < n) {
return ring.getZERO();
}
if (!ps.coefficient(n).isUnit()) {
throw new ArithmeticException("division by non unit coefficient " + ps.coefficient(n) + ", n = "
+ n);
}
// now m >= n
UnivPowerSeries st, sps, q, sq;
if (m == 0) {
st = this;
} else {
st = this.shift(-m);
}
if (n == 0) {
sps = ps;
} else {
sps = ps.shift(-n);
}
q = st.multiply(sps.inverse());
if (m == n) {
sq = q;
} else {
sq = q.shift(m - n);
}
return sq;
}
/**
* Power series remainder.
* @param ps nonzero power series with invertible leading coefficient.
* @return remainder with this = quotient * ps + remainder.
*/
public UnivPowerSeries remainder(UnivPowerSeries ps) {
int m = order();
int n = ps.order();
if (m >= n) {
return ring.getZERO();
}
return this;
}
/**
* Quotient and remainder by division of this by S.
* @param S a UnivPowerSeries
* @return [this/S, this - (this/S)*S].
*/
public UnivPowerSeries[] quotientRemainder(UnivPowerSeries S) {
return new UnivPowerSeries[] { divide(S), remainder(S) };
}
/**
* Differentiate.
* @return differentiate(this).
*/
public UnivPowerSeries differentiate() {
return new UnivPowerSeries(ring, new Coefficients() {
@Override
public C generate(int i) {
C v = coefficient(i + 1);
v = v.multiply(ring.coFac.fromInteger(i + 1));
return v;
}
});
}
/**
* Integrate with given constant.
* @param c integration constant.
* @return integrate(this).
*/
public UnivPowerSeries integrate(final C c) {
return new UnivPowerSeries(ring, new Coefficients() {
@Override
public C generate(int i) {
if (i == 0) {
return c;
}
C v = coefficient(i - 1);
v = v.divide(ring.coFac.fromInteger(i));
return v;
}
});
}
/**
* Power series greatest common divisor.
* @param ps power series.
* @return gcd(this,ps).
*/
public UnivPowerSeries gcd(UnivPowerSeries ps) {
if (ps.isZERO()) {
return this;
}
if (this.isZERO()) {
return ps;
}
int m = order();
int n = ps.order();
int ll = (m < n) ? m : n;
return ring.getONE().shift(ll);
}
/**
* Power series extended greatest common divisor. Note: not
* implemented.
* @param S power series.
* @return [ gcd(this,S), a, b ] with a*this + b*S = gcd(this,S).
*/
//SuppressWarnings("unchecked")
public UnivPowerSeries[] egcd(UnivPowerSeries S) {
throw new UnsupportedOperationException("egcd for power series not implemented");
}
}
/* arithmetic method functors */
/**
* Internal summation functor.
*/
class Sum> implements BinaryFunctor {
public C eval(C c1, C c2) {
return c1.sum(c2);
}
}
/**
* Internal subtraction functor.
*/
class Subtract> implements BinaryFunctor {
public C eval(C c1, C c2) {
return c1.subtract(c2);
}
}
/**
* Internal scalar multiplication functor.
*/
class Multiply> implements UnaryFunctor {
C x;
public Multiply(C x) {
this.x = x;
}
public C eval(C c) {
return c.multiply(x);
}
}
/**
* Internal negation functor.
*/
class Negate> implements UnaryFunctor {
public C eval(C c) {
return c.negate();
}
}
/* only for sequential access:
class Abs> implements UnaryFunctor {
int sign = 0;
public C eval(C c) {
int s = c.signum();
if ( s == 0 ) {
return c;
}
if ( sign > 0 ) {
return c;
} else if ( sign < 0 ) {
return c.negate();
}
// first non zero coefficient:
sign = s;
if ( s > 0 ) {
return c;
}
return c.negate();
}
}
*/
Ads help maintain this website.