public class PolynomialZ extends TreeMap<BigInteger,BigInteger>
p(x) = a0 + a1 x + a2 x2 + ... + an xn
where a0, a1, ..., an ∈ ℤ, and an ǂ 0. Then n is called the degree of the polynomial. Internally, a polynomial is represented by a sorted map, where the key represents the unique exponent and the value the respective coefficient, i.e., is given by the map[<n,an>, ..., <0,a0>]
The default comparator for the exponents, i.e., the keys of this TreeMap, isBigExponentComparator
, with a descending order.
The simplest way to create a polynomial
is given by the following code snippet:
PolynomialZ p = new PolynomialZ(); p.put( new BigInteger("1023"), new BigInteger("1") ); p.put( new BigInteger("2"), new BigInteger("-3") ); p.put( new BigInteger("1"), new BigInteger("5") ); p.put( new BigInteger("0"), new BigInteger("-1") );Here the order of put instructions is arbitrary. This object then represents the polynomial
p(x) = x1023 - 3x2 + 5x - 1
This class requires JDK 5 or higher.Polynomial
,
Serialized FormAbstractMap.SimpleEntry<K,V>, AbstractMap.SimpleImmutableEntry<K,V>
Constructor and Description |
---|
PolynomialZ()
Creates an empty polynomial with a new
BigExponentComparator . |
PolynomialZ(BigExponentComparator ec)
Creates an empty polynomial with the given
BigExponentComparator . |
PolynomialZ(BigInteger exponent,
BigInteger coefficient)
Creates a polynomial with a the single term ae xe
and a new
BigExponentComparator . |
PolynomialZ(BigInteger exponent,
BigInteger coefficient,
BigExponentComparator ec)
Creates a polynomial with a the single term ae xe
and the given
BigExponentComparator . |
Modifier and Type | Method and Description |
---|---|
PolynomialZ[] |
divide(PolynomialZ v)
Divides this polynomial by the given polynomial v
and returns an array {q,r} holding the quotient q as the first
entry and the remainder r as the second entry.
|
PolynomialZ[] |
divideMod(PolynomialZ v,
BigInteger m)
Divides this polynomial by the given polynomial v modulo m
and returns an array {q,r} holding the quotient q as the first entry
and the remainder r as the second entry.
|
BigInteger |
evaluate(BigInteger x)
Evaluates this polynomial at the point x.
|
BigInteger |
evaluateMod(BigInteger x,
BigInteger n)
Evaluates this polynomial at the point x modulo n.
|
BigInteger |
getDegree()
Returns the degree of this polynomial.
|
PolynomialZ |
minus(PolynomialZ q)
Returns the difference this - q of this polynomial and the specified
polynomial q.
|
PolynomialZ |
minus(PolynomialZ q,
BigInteger m)
Returns the difference this - q of this polynomial and the specified
polynomial q, with coefficients modula m.
|
PolynomialZ |
mod(PolynomialZ y)
Returns the remainder of the division of this polynomial by the given
polynomial y.
|
PolynomialZ |
mod(PolynomialZ y,
BigInteger m)
Returns the remainder of the division of this polynomial by the given
polynomial y modulo m.
|
PolynomialZ |
modPow(BigInteger e,
int r,
BigInteger n)
Returns se mod (xr - 1, n)
where s is this polynomial.
|
PolynomialZ |
modPow(int e,
BigInteger n)
Returns the polynomial qe mod (p, n)
where q is this polynomial.
|
PolynomialZ |
modPow(PolynomialZ p,
BigInteger e,
BigInteger n)
Returns the polynomial qe mod (p, n)
where q is this polynomial.
|
PolynomialZ |
multiply(PolynomialZ q)
Multiplies this polynomial with the given polynomial q.
|
PolynomialZ |
multiplyMod(PolynomialZ q,
BigInteger n)
Multiplies this polynomial with the given polynomial q modulo n.
|
PolynomialZ |
multiplyMod2(PolynomialZ q,
BigInteger n)
Multiplies this polynomial with the given polynomial q modulo n.
|
PolynomialZ |
plus(PolynomialZ q)
Returns the sum this + q of this polynomial and the specified
polynomial q.
|
PolynomialZ |
plus(PolynomialZ q,
BigInteger m)
Returns the sum this + q of this polynomial and the specified
polynomial q, with coefficients modulo m.
|
BigInteger |
put(BigInteger exponent,
BigInteger coefficient)
Adds the term ae xe to this
polynomial.
|
String |
toBinaryString()
Returns a binary string representation of this polynomial, where the
j-the bit (counted from the right) is zero iff the coefficient
of xj is zero.
|
String |
toHTMLString()
Returns a HTML string representation of this polynomial.
|
String |
toString()
Returns a string representation of this polynomial.
|
ceilingEntry, ceilingKey, clear, clone, comparator, containsKey, containsValue, descendingKeySet, descendingMap, entrySet, firstEntry, firstKey, floorEntry, floorKey, forEach, get, headMap, headMap, higherEntry, higherKey, keySet, lastEntry, lastKey, lowerEntry, lowerKey, navigableKeySet, pollFirstEntry, pollLastEntry, putAll, remove, replace, replace, replaceAll, size, subMap, subMap, tailMap, tailMap, values
equals, hashCode, isEmpty
finalize, getClass, notify, notifyAll, wait, wait, wait
compute, computeIfAbsent, computeIfPresent, equals, getOrDefault, hashCode, isEmpty, merge, putIfAbsent, remove
public PolynomialZ()
BigExponentComparator
.public PolynomialZ(BigExponentComparator ec)
BigExponentComparator
.ec
- an exponent comparatorpublic PolynomialZ(BigInteger exponent, BigInteger coefficient)
BigExponentComparator
.exponent
- the exponent ecoefficient
- the coefficient aepublic PolynomialZ(BigInteger exponent, BigInteger coefficient, BigExponentComparator ec)
BigExponentComparator
.exponent
- the exponent ecoefficient
- the coefficient aeec
- the comparator to compare exponentspublic BigInteger put(BigInteger exponent, BigInteger coefficient)
put
in interface Map<BigInteger,BigInteger>
put
in class TreeMap<BigInteger,BigInteger>
exponent
- the exponent e in the term ae xecoefficient
- the coefficient ae in the term
ae xepublic PolynomialZ plus(PolynomialZ q)
q
- the polynomial to be added to this polynomialpublic PolynomialZ plus(PolynomialZ q, BigInteger m)
q
- the polynomial to be added to this polynomialm
- the summandpublic PolynomialZ minus(PolynomialZ q)
q
- the polynomial to be subtracted from this polynomialpublic PolynomialZ minus(PolynomialZ q, BigInteger m)
q
- the polynomial to be subtracted from this polynomialm
- the moduluspublic PolynomialZ multiply(PolynomialZ q)
q
- the polynomial to be multiplied with this polynomialpublic PolynomialZ multiplyMod(PolynomialZ q, BigInteger n)
q
- the polynomial to be multiplied with this polynomialn
- the moduluspublic PolynomialZ multiplyMod2(PolynomialZ q, BigInteger n)
multiplyMod(PolynomialZ, BigInteger)
if all, or nearly all,
powers have non-vanishing coefficients.q
- the polynomial to be multiplied with this polynomialn
- the modulusmultiplyMod(PolynomialZ, BigInteger)
public PolynomialZ[] divide(PolynomialZ v)
v
- the polynomial to divide this polynomialpublic PolynomialZ mod(PolynomialZ y)
y
- the polynomial to divide this polynomialpublic PolynomialZ mod(PolynomialZ y, BigInteger m)
y
- the polynomial to divide this polynomialm
- the moduluspublic PolynomialZ[] divideMod(PolynomialZ v, BigInteger m)
v
- the polynomial to divide this polynomialm
- the moduluspublic PolynomialZ modPow(int e, BigInteger n)
e
- the exponentn
- the modulusthis
e mod npublic PolynomialZ modPow(PolynomialZ p, BigInteger e, BigInteger n)
p
- the modulus polynomiale
- the exponentn
- the modulusthis
e mod (p, n)public PolynomialZ modPow(BigInteger e, int r, BigInteger n)
e
- the exponentr
- the degree of the monic polynomial xr - 1n
- the modulusIllegalArgumentException
- if r $lt; 0public BigInteger evaluate(BigInteger x)
x
- the argument value to be evaluatedpublic BigInteger evaluateMod(BigInteger x, BigInteger n)
x
- the argument value to be evaluatedn
- the moduluspublic BigInteger getDegree()
public String toBinaryString()
public String toHTMLString()
public String toString()
toString
in class AbstractMap<BigInteger,BigInteger>