Polynomials must support the operations specified in this type class. All powers must be non-negative.

Scale the polynomial so that its leading coefficient is one.

>>> monic $ 4 * power 2 + 4 * power 1 + 4 :: IndexedPolynomial
x^2 + x + 1

The exception is when the polynomial is zero.

>>> monic 0 :: IndexedPolynomial
0

Maps the coefficients in a polynomial to form another polynomial.

For example, it can be used to convert a polynomial with Rational coefficients into a polynomial with Expression coefficients.

>>> let p = 2 * power 1 + 1 :: IndexedPolynomial
>>> let q = mapCoefficients fromRational p :: IndexedSymbolicPolynomial
>>> simplify $ coefficient q 1
Number 2

Polynomial division. It returns the quotient polynomial and the remainder polynomial.

For example, dividing \(p = x^3-12x^2-42\) by \(q = x^2 - 2x + 1\) returns \(x-10\) as the quotient and \(-21x-32\) as the remainder, since \(p = (x-10)q -21x - 32\):

>>> let p = power 3 - 12 * power 2 - 42 :: IndexedPolynomial
>>> let q = power 2 - 2 * power 1 + 1 :: IndexedPolynomial
>>> divide p q
(x + (-10),(-21)x + (-32))

Polynomial pseudo-division. It returns the pseudo-quotient and pseudo-remainder polynomials.

Equivalent to \(b^{\delta+1} p\) divided by \(q\), where \(p\) and \(q\) are polynomials with integer coefficients, \(b\) is the leading coefficient of \(q\) and \(\delta=\max(-1, \deg(p) - \deg(q))\). This guarantees the pseudo-quotient and pseudo-remainder exist, even when the quotient and remainder do not when only integer coefficients are allowed.

For example, with \(p = 3x^3 + x^2 + x + 5\) and \(q = 5x^2 - 3x + 1\), it is the case that \(5^2p = (15x + 14)q + (52x + 111)\):

>>> let p = 3 * power 3 + power 2 + power 1 + 5 :: IndexedPolynomial
>>> let q = 5 * power 2 - 3 * power 1 + 1 :: IndexedPolynomial
>>> pseudoDivide p q
(15x + 14,52x + 111)

The extended Euclidean algorithm. For polynomials \(p\) and \(q\), it returns the greatest common divisor between \(p\) and \(q\). It also returns \(s\) and \(t\) such that \(sp+tq = \gcd(p,q)\).

For example, for \(p=2x^5-2x\) and \(q=x^4-2x^2+1\), it is the case that \(\gcd(p,q)=-x^2+1\) and \((-\frac{1}{4}x) p + (\frac{1}{2}x^2 + 1) q = -x^2+1\):

>>> let p = 2 * power 5 - 2 * power 1 :: IndexedPolynomial
>>> let q = power 4 - 2 * power 2 + 1 :: IndexedPolynomial
>>> extendedEuclidean p q
(((-1) % 4)x,(1 % 2)x^2 + 1,(-1)x^2 + 1)

Solves \(sa + tb = c\) for given polynomials \(a\), \(b\), and \(c\). It will be the case that either \(s=0\) or the degree of \(s\) will be less than the degree of \(b\).

>>> let a = power 4 - 2 * power 3 - 6 * power 2 + 12 * power 1 + 15 :: IndexedPolynomial
>>> let b = power 3 + power 2 - 4 * power 1 - 4 :: IndexedPolynomial
>>> let c = power 2 - 1 :: IndexedPolynomial
>>> diophantineEuclidean a b c
Just (((-1) % 5)x^2 + (4 % 5)x + ((-3) % 5),(1 % 5)x^3 + ((-7) % 5)x^2 + (16 % 5)x + (-2))

If there is no such \((s,t)\), then Nothing is returned.

Returns the greatest common divisor btween two polynomials.

Convenient wrapper over extendedEuclidean which only returns the greatest common divisor.

Returns the resultant and the subresultant polynomial remainder sequence for the given polynomials.

>>> subresultant (power 2 + 1) (power 2 - 1 :: IndexedPolynomial)
(4 % 1,[x^2 + 1,x^2 + (-1),(-2),0])
>>> subresultant (2 * power 2 - 3 * power 1 + 1) (5 * power 2 + power 1 - 6 :: IndexedPolynomial)
(0 % 1,[2x^2 + (-3)x + 1,5x^2 + x + (-6),17x + (-17),0])
>>> subresultant (power 3 + 2 * power 2 + 3 * power 1 + 4) (5 * power 2 + 6 * power 1 + 7 :: IndexedPolynomial)
(832 % 1,[x^3 + 2x^2 + 3x + 4,5x^2 + 6x + 7,16x + 72,832,0])

Reference

Returns the derivative of the given polynomial.

>>> differentiate (power 2 + power 1 :: IndexedPolynomial)
2x + 1

Returns the integral of the given polynomial.

>>> integrate (power 2 + power 1 :: IndexedPolynomial)
(1 % 3)x^3 + (1 % 2)x^2

Returns the squarefree factorization of the given polynomial.

Specifically, for a polynomial \(p\), find \([p_1, p_2, \ldots, p_n]\) such that

\[ p = \sum_{k=1}^n p_k^k \]

where all \(p_k\) are squarefree, i.e., there is no polynomial \(q\) such that \(q^2 = p_k\).

For example, the squarefree factorization of \(x^8 + 6x^6 + 12x^4 + 8x^2\) is \(x^2 (x^2 + 2)^3\):

>>> squarefree (power 8 + 6 * power 6 + 12 * power 4 + 8 * power 2 :: IndexedPolynomial)
[1,x,x^2 + 2]