Skip to content

polyfrac

Exact real-root counting over the rationals

Sturm's theorem over exact rational arithmetic: the number of distinct real roots in an interval, as an integer, with no floating point anywhere.

:material-github: Source

68 tests · ~390 lines of source · MIT

Install

$ pip install polyfrac

Honest scope

Reproduced from the package README, which is the source of truth.

Exactness is enforced at the boundary, not merely intended. Passing a float raises InexactInput rather than being converted, because 0.1 is not one tenth — it is 3602879701896397/36028797018963968, and exact arithmetic on it produces an exact answer to a question you did not ask. Use Fraction(1, 10), the string "0.1", or the explicit Poly.from_floats() when a float really is the value you mean.

>>> Poly([0.1])
InexactInput: refusing the float 0.1: it is a binary approximation ...
>>> Poly(["0.1"]).c[0]
Fraction(1, 10)

What it proves. An exact count of distinct real roots in the half-open interval (a, b], and an exact sign certificate over an interval. No sampling, no tolerance, no numerical root finding — the count comes from sign changes in a Sturm chain over exact rationals.

What it does not prove.

  • Univariate only, over ℚ. For multivariate sign conditions you want cylindrical algebraic decomposition, which this package does not implement.
  • Multiplicities are not reported. Poly.from_roots([2, 2, 2]) has one distinct root.
  • Irrational and complex roots are outside the interval arithmetic entirely; only real roots at rational-bounded intervals are counted.
  • The interval convention is half-open (a, b] — the left endpoint is excluded and the right is included. Off-by-one here is silent, so it is asserted in the test suite.
  • gauss_solve requires a non-singular system; a singular one raises rather than returning a value.
  • The zero polynomial raises. It is zero at every point, so no finite root count exists, and returning 0 would be a confident wrong answer.

Full documentation, quickstart and troubleshooting live in the repository README.