Documentation

Polynomials of one variable with coefficients from a, backed by a Vector v (boxed, unboxed, storable, etc.).

Use the pattern X for construction:

>>> (X + 1) + (X - 1) :: VPoly Integer
2 * X + 0
>>> (X + 1) * (X - 1) :: UPoly Int
1 * X^2 + 0 * X + (-1)

Polynomials are stored normalized, without leading zero coefficients, so 0 * X + 1 equals to 1.

The Ord instance does not make much sense mathematically, it is defined only for the sake of Set, Map, etc.

Due to being polymorphic by multiple axis, the performance of Poly crucially depends on specialisation of instances. Clients are strongly recommended to compile with ghc-options: -fspecialise-aggressively and suggested to enable -O2.

Since: 0.1.0.0

Polynomials backed by boxed vectors.

Since: 0.2.0.0

Polynomials backed by unboxed vectors.

Since: 0.2.0.0

Convert a Poly to a vector of coefficients (first element corresponds to the constant term).

Since: 0.1.0.0

Return the leading power and coefficient of a non-zero polynomial.

>>> leading ((2 * X + 1) * (2 * X^2 - 1) :: UPoly Int)
Just (3,4)
>>> leading (0 :: UPoly Int)
Nothing

Since: 0.3.0.0

Make a Poly from a vector of coefficients (first element corresponds to the constant term).

>>> :set -XOverloadedLists
>>> toPoly [1,2,3] :: VPoly Integer
3 * X^2 + 2 * X + 1
>>> toPoly [0,0,0] :: UPoly Int
0

Since: 0.2.0.0

Create a monomial from a power and a coefficient.

Since: 0.3.0.0

Multiply a polynomial by a monomial, expressed as a power and a coefficient.

>>> scale 2 3 (X^2 + 1) :: UPoly Int
3 * X^4 + 0 * X^3 + 3 * X^2 + 0 * X + 0

Since: 0.3.0.0

The polynomial X.

X == monomial 1 one

Since: 0.2.0.0

Evaluate the polynomial at a given point.

>>> eval (X^2 + 1 :: UPoly Int) 3
10

Since: 0.2.0.0

Substitute another polynomial instead of X.

>>> subst (X^2 + 1 :: UPoly Int) (X + 1 :: UPoly Int)
1 * X^2 + 2 * X + 2

Since: 0.3.3.0

Take the derivative of the polynomial.

>>> deriv (X^3 + 3 * X) :: UPoly Int
3 * X^2 + 0 * X + 3

Since: 0.2.0.0

Compute an indefinite integral of the polynomial, setting the constant term to zero.

>>> integral (3 * X^2 + 3) :: UPoly Double
1.0 * X^3 + 0.0 * X^2 + 3.0 * X + 0.0

Since: 0.3.2.0

Karatsuba multiplication algorithm for polynomials over rings.

Convert from dense to sparse polynomials.

>>> :set -XFlexibleContexts
>>> denseToSparse (1 `Data.Semiring.plus` Data.Poly.X^2) :: Data.Poly.Sparse.UPoly Int
1 * X^2 + 1

Since: 0.5.0.0

Convert from sparse to dense polynomials.

>>> :set -XFlexibleContexts
>>> sparseToDense (1 `Data.Semiring.plus` Data.Poly.Sparse.X^2) :: Data.Poly.UPoly Int
1 * X^2 + 0 * X + 1

Since: 0.5.0.0

Discrete Fourier transform \( y_k = \sum_{j=0}^{N-1} x_j \sqrt[N]{1}^{jk} \).

Since: 0.5.0.0

Inverse discrete Fourier transform \( x_k = {1\over N} \sum_{j=0}^{N-1} y_j \sqrt[N]{1}^{-jk} \).

Since: 0.5.0.0

Multiplication of polynomials using discrete Fourier transform. It could be faster than (*) for large polynomials if multiplication of coefficients is particularly expensive.

Since: 0.5.0.0