poly: Polynomials

[ bsd3, library, math, numerical ] [ Propose Tags ]

Polynomials backed by Vector.


[Skip to Readme]
Versions [faq] 0.1.0.0, 0.2.0.0, 0.3.0.0, 0.3.1.0 (info)
Change log changelog.md
Dependencies base (>=4.9 && <5), primitive (>=0.6), semirings (>=0.2), vector (>=0.12.0.2), vector-algorithms (>=0.7) [details]
License BSD-3-Clause
Copyright 2019 Andrew Lelechenko
Author Andrew Lelechenko
Maintainer andrew.lelechenko@gmail.com
Category Math, Numerical
Home page https://github.com/Bodigrim/poly#readme
Source repo head: git clone https://github.com/Bodigrim/poly
Uploaded by Bodigrim at Tue Jul 23 18:10:39 UTC 2019
Distributions NixOS:0.3.1.0
Downloads 252 total (41 in the last 30 days)
Rating 2.0 (votes: 1) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs available [build log]
Last success reported on 2019-07-23 [all 1 reports]

Modules

[Index] [Quick Jump]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees


Readme for poly-0.3.1.0

[back to package description]

poly Build Status Hackage Hackage CI Stackage LTS Stackage Nightly

Haskell library for univariate polynomials, backed by Vector.

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

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

Vectors

Poly v a is polymorphic over a container v, implementing Vector interface, and coefficients of type a. Usually v is either a boxed vector from Data.Vector or an unboxed vector from Data.Vector.Unboxed. Use unboxed vectors whenever possible, e. g., when coefficients are Int or Double.

There are handy type synonyms:

type VPoly a = Poly Data.Vector.Vector         a
type UPoly a = Poly Data.Vector.Unboxed.Vector a

Construction

The simplest way to construct a polynomial is using the pattern X:

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

(Unfortunately, a type is often ambiguous and must be given explicitly.)

While being convenient to read and write in REPL, X is relatively slow. The fastest approach is to use toPoly, providing it with a vector of coefficients (head is the constant term):

> toPoly (Data.Vector.Unboxed.fromList [2, -3, 1 :: Int])
1 * X^2 + (-3) * X + 2

Alternatively one can enable {-# LANGUAGE OverloadedLists #-} and simply write

> [2, -3, 1] :: UPoly Int
1 * X^2 + (-3) * X + 2

There is a shortcut to construct a monomial:

> monomial 2 3.5 :: UPoly Double
3.5 * X^2 + 0.0 * X + 0.0

Operations

Most operations are provided by means of instances, like Eq and Num. For example,

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

One can also find convenient to scale by monomial (cf. monomial above):

> scale 2 3.5 (X^2 + 1) :: UPoly Double
3.5 * X^4 + 0.0 * X^3 + 3.5 * X^2 + 0.0 * X + 0.0

While Poly cannot be made an instance of Integral (because there is no meaningful toInteger), it is an instance of GcdDomain and Euclidean from semirings package. These type classes cover main functionality of Integral, providing division with remainder and gcd / lcm:

> Data.Euclidean.gcd (X^2 + 7 * X + 6) (X^2 - 5 * X - 6) :: Data.Poly.UPoly Int
1 * X + 1

> Data.Euclidean.quotRem (X^3 + 2) (X^2 - 1 :: Data.Poly.UPoly Double)
(1.0 * X + 0.0,1.0 * X + 2.0)

Miscellaneous utilities include eval for evaluation at a given value of indeterminate, and reciprocals deriv / integral:

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

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

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

Deconstruction

Use unPoly to deconstruct a polynomial to a vector of coefficients (head is the constant term):

> unPoly (X^2 - 3 * X + 2 :: UPoly Int)
[2,-3,1]

Further, leading is a shortcut to obtain the leading term of a non-zero polynomial, expressed as a power and a coefficient:

> leading (X^2 - 3 * X + 2 :: UPoly Double)
Just (2,1.0)

Flavours

The same API is exposed in four flavours:

  • Data.Poly provides dense polynomials with Num-based interface. This is a default choice for most users.

  • Data.Poly.Semiring provides dense polynomials with Semiring-based interface.

  • Data.Poly.Sparse provides sparse polynomials with Num-based interface. Besides that, you may find it easier to use in REPL because of a more readable Show instance, skipping zero coefficients.

  • Data.Poly.Sparse.Semiring provides sparse polynomials with Semiring-based interface.

All flavours are available backed by boxed or unboxed vectors.

Performance

As a rough guide, poly is at least 20x-40x faster than polynomial library. Multiplication is implemented via Karatsuba algorithm. Here is a couple of benchmarks for UPoly Int.

| Benchmark | polynomial, μs | poly, μs | speedup | :---------------------------- | --------------: | -------: | ------: | addition, 100 coeffs. | 45 | 2 | 22x | addition, 1000 coeffs. | 441 | 17 | 25x | addition, 10000 coeffs. | 6545 | 167 | 39x | multiplication, 100 coeffs. | 1733 | 33 | 52x | multiplication, 1000 coeffs. | 442000 | 1456 | 303x