Expand description
§neco-algnum
neco-algnum is a crate for exact real algebraic numbers.
A value is identified by a pair: an integer minimal polynomial and the index of a real root.
The minimal polynomial is kept in normal form (primitive, irreducible, positive leading coefficient), and root indices start at 0.
For example, $ \sqrt{2} + \sqrt{3} $ is represented by the pair below.
$$ m(x) = x^{4} - 10x^{2} + 1, \qquad k = 3 $$
The real roots of $ m $ are the four values $ \pm\sqrt{3} \pm \sqrt{2} $, and counting them in ascending order, the index $ k = 3 $ points to the largest root $ \sqrt{2} + \sqrt{3} $. Certified intervals with dyadic endpoints are used to construct and observe a value. The identity of the value itself is preserved by the minimal polynomial and root index.
§Polynomials and validated types
Integer and rational polynomials store their coefficients from the lowest degree upward. Values under construction and validated values are separated by type.
Polynomial: an integer polynomial with trailing zeroes removedRationalPolynomial: a rational polynomial with trailing zeroes removedCandidatePolynomial: a candidate polynomial of degree at least 1SquareFreePolynomial: a primitive, square-free polynomial with a positive leading coefficientIrreduciblePolynomial: a polynomial irreducible over the rationalsMinimalPolynomial: the irreducible polynomial that identifies a real algebraic numberPolynomialQuotient: operations in the quotient ringQ[x] / (m)GeneratorRepresentative: the generatorx mod mfor the same modulusRootIndex: the index of a real root of one irreducible polynomial, counted in ascending orderRealAlgebraic: an exact value made of a minimal polynomial and a real-root indexIsolatingInterval: a dyadic interval that contains an exact value and is used for observationCertifiedAlgebraic: a pair of an exact value and a certified interval obtained by root isolation
Polynomial supports addition, subtraction, multiplication, differentiation, evaluation at integer and rational points, and composition.
CandidatePolynomial::square_free removes the content (the greatest common divisor of the coefficients) and repeated factors.
Factorization enumerates every factor candidate with the Kronecker method. A polynomial that no enumerated candidate divides is determined to be irreducible.
§Polynomial quotient
PolynomialQuotient reduces operation results modulo the minimal polynomial and returns a RationalPolynomial of degree below the modulus.
reduce: reduce one polynomialadd: reduce the result of an additionsub: reduce the result of a subtractionmul: reduce the result of a multiplication
generator returns the generator reduced by the same modulus.
RationalPolynomial::to_real_algebraic_coefficients converts rational coefficients to real algebraic numbers and returns the result as RationalCoefficientConversion.
§Certified real roots
Sturm sequences isolate every real root into intervals that each contain exactly one distinct root, and the real roots of the same irreducible polynomial receive root indices in ascending order of value. Neighboring intervals may share an endpoint. A root is constructed either by isolating all real roots or by validating an interval supplied by the caller, and the exact value is then extracted from the result.
isolate_real_roots: return all real roots with certified intervalscertify_root: validate two caller-provided dyadic endpointsinto_value: extract the exact value from a certified construction result
§Interval refinement
RealAlgebraic::enclose and IsolatingInterval::refine refine an interval to at most the requested width while preserving the same minimal polynomial and root index.
§Exact observations
Comparison, sign, and the zero and one tests return exact results. The minimal polynomial and root index used for identification can also be read.
compare: compare two real algebraic numberscompare_dyadic: compare with a dyadic valuesign: determine the signis_zero: decide whether the value is zero from the minimal polynomial and root indexis_one: decide whether the value is the multiplicative unit 1 from the minimal polynomial and root indexminimal_polynomial: read the minimal polynomial used for identificationroot_index: read the root index used for identification
§Exact algebraic operations
RealAlgebraic provides the four arithmetic operations, powers, and roots.
It also converts from formal sums and tests equality with them.
add: add two real algebraic numberssub: subtract two real algebraic numbersmul: multiply two real algebraic numbersdiv: divide two real algebraic numberspow_integer: raise to an integer powerpow_rational: raise to a reduced rational power with a real valuenth_root: take a real root of positive degreefrom_form_sum: promote an exactFormSumto a real algebraic numberequals_form_sum: decide equality with a formal sum. The values are equal when substituting the formal sum into the minimal polynomial withFormSumarithmetic gives zero, and an interval containing the value of the formal sum meets only the interval of the root that the root index points to
Addition, subtraction, multiplication, division, powers, and roots all proceed through resultant construction, removal of square factors, complete factorization, and certified root selection, and return the result again as a pair of minimal polynomial and root index (RealAlgebraic).
Division first tests whether the divisor is zero and rejects it if so.
An even root of a negative value has no real value and returns a failure, while an odd root of a negative value returns the unique real root.
§Failures
AlgnumError distinguishes input, operation, representation, storage, and lower-crate failures.
ZeroPolynomial: no candidate of degree at least 1 existsInvalidIsolation: the endpoints are reversed or equal, or an endpoint is itself a root of the polynomialNoTargetRoot: the given interval contains no target rootMultipleTargetRoots: the given interval contains more than one target rootDivisionByZero: division by a value that is exactly zeroUndefinedZeroPower:0^0was requestedZeroToNegativePower: zero was raised to a negative powerZeroRootDegree: a root of degree 0 was requestedEvenRootOfNegative: an even root of a negative value was requestedRepresentationLimit: a degree, coefficient count, or Sylvester matrix size exceeded the representation limitAllocationLimit: the exact estimate of the required total element count exceeded theusizelimitAllocationFailure: the allocator refused an allocation; holds the resource and the requested element countBigint: holds aneco-bigintfailure with its variant and payloadFormSum: holds aneco-formsumfailure with its variant and payload
§Representation limits
RepresentationResource distinguishes the subjects that exceeded a limit:
- root degree
- polynomial degree
- coefficient count
- Sylvester matrix dimension
- Sylvester matrix element count
§Allocation subjects
AllocationResource distinguishes thirteen kinds of subjects whose allocation failed:
- polynomial coefficients
- rational coefficients
- Kronecker evaluation points
- divisors of the evaluated values
- indices that enumerate tuples of divisors
- factor candidates
- factors
- Sturm sequences
- root intervals
- Sylvester matrix elements
- permutations for the determinant expansion
- resultant coefficients
- root candidates
Storage failures come in two kinds: the total element count exceeds the platform limit, or the allocator refuses a request within that limit.
Public types that own variable-length values provide try_clone and return allocation failures during cloning through Result.
§Features and dependencies
With the default std feature enabled, AlgnumError can be used as a standard error type, and failures from lower crates remain reachable through the error source.
This feature also enables the feature of the same name in both dependencies.
Disabling default features selects the core + alloc configuration, which handles the same exact values and the same failures.
cargo check -p neco-algnum --no-default-featuresAt runtime, the crate depends on neco-bigint and neco-formsum.
§License
MIT License.
Structs§
- Candidate
Polynomial - Certified
Algebraic - Generator
Representative - Irreducible
Polynomial - Isolating
Interval - Minimal
Polynomial - Polynomial
- Polynomial
Quotient - Rational
Coefficient Conversion - Rational
Polynomial - Real
Algebraic - Root
Index - Square
Free Polynomial