Skip to main content

Crate neco_calculus

Crate neco_calculus 

Source
Expand description

§neco-calculus

日本語

neco-calculus is the crate that gathers the public operations for exact polynomial and rational calculus. It combines exact evaluation, finite derivative sequences, validated enclosures (intervals verified to contain the exact value), root bracket narrowing, interval sign classification, and candidate root classification.

Root bracket narrowing shrinks an interval that contains a root by bisection or Newton-bisection. The process is kept in a narrowing witness (ConvergenceWitness) that holds the method, the convergence status, the iteration counts, and the initial and final intervals.

Interval sign classification determines whether the sign of a polynomial is constant on an interval or changes within it. Candidate root classification takes the candidate points supplied by the caller, keeps those that are roots of the polynomial, and separates odd-multiplicity roots, where the sign changes, from even-multiplicity roots, where the sign stays the same.

§Features

Exact Evaluation of Surface and Implicit Polynomials

A surface polynomial (SurfacePolynomial) is a polynomial in the variables u and v with rational coefficients. A rational parametric surface represents its x, y, and z coordinates and their common denominator by surface polynomials. An implicit polynomial (ImplicitPolynomial3) is a polynomial in the variables x, y, and z with real algebraic coefficients.

Both constructions arrange the terms in ascending lexicographic order of their exponent tuples. Surface polynomial construction adds terms with the same exponent tuple and removes terms whose coefficient is zero.

Implicit polynomial construction returns a failure for an input with a zero coefficient or a repeated exponent tuple. The evaluation functions return exact values or validated enclosures wrapped in result types that hide their internal representation.

Rational, Jet, and Root Operations

The crate also exposes rational evaluation and derivative sequences (Jet). Root operations have public functions for root bracket narrowing, interval sign classification, and candidate root classification.

  • refine_root_bisection: Narrows a root bracket by bisection.
  • refine_root_newton_bisection: Narrows a root bracket by Newton-bisection.
  • expose_region_sign: Returns the interval sign classification result (RegionSignJudgment).
  • expose_membership_transitions: Returns the candidate root classification.

Failures returned by dependency crates are kept as they are, including the values attached to them.

Transcendental Evaluation

Sine, cosine, exponential, and real powers are evaluated over interval arguments at a requested absolute precision. When the input interval contains a point where sine or cosine takes an extremum, the enclosure also contains that extremum. Whether such a point lies in the input interval is decided with an outward-rounded enclosure of pi.

For a requested precision of p bits, the target width is 2^-p. A result is an exact value, an enclosure no wider than the target width, or an undetermined result.

Evaluation estimates the width of the result enclosure. For sine and cosine, the width estimate is the width of the computed enclosure.

For the exponential, the width estimate is the width of the argument interval multiplied by an upper bound of the derivative magnitude. For real powers, the width estimate is the sum, over the base and the exponent, of the interval width multiplied by an upper bound of the partial derivative magnitude.

An undetermined result appears when the width estimate exceeds the target width, and it keeps the interval established so far. The actual width of that interval can still be within the target width.

  • evaluate_transcendental_function: Evaluates the function selected by TranscendentalFunction.
  • evaluate_transcendental_power: Evaluates a real power whose base is a strictly positive interval.
  • TranscendentalEvaluation::undetermined_achieved: Returns the interval kept by an undetermined result.
  • TranscendentalFunction: Names the functions that can be evaluated.
    • Sine
    • Cosine
    • Exponential

Certified Double-Precision Projection

A result can be projected to the nearest double-precision floating-point value (f64). The projected value comes with the enclosure before rounding and the actual absolute error of that rounding. The size of the error depends on the width of the enclosure (at most the target width) and the spacing of adjacent double-precision values.

  • TranscendentalEvaluation::certify_f64: Returns a CertifiedF64 for an exact value or an enclosure.

Validated Transcendental Enclosures

construct_transcendental_evaluation builds a transcendental evaluation result from an evaluation candidate supplied by the caller. An evaluation candidate (TranscendentalEvaluationCandidate) pairs a value with its provenance.

Before construction, the function validates that the candidate provenance matches the provenance the caller requires, that the requested precision is from 1 to 256 bits, and that the enclosure is no wider than the target width.

Certified Quadrature

Quadrature integrates over a closed interval whose bounds are dyadic rationals (rationals whose denominator is a power of two) and returns an enclosure of the integral. For a requested precision of p bits, the width of the enclosure is at most the target width 2^-p.

Quadrature divides the integration interval into subintervals and expands the integrand in a Taylor series at the midpoint of each subinterval. The quadrature order (the value of QuadratureOrder) is the number of even-order terms of this expansion kept before the remainder term. The remainder-term enclosure is computed from the range that the derivative whose order is twice the quadrature order takes over the subinterval.

The integrand implements IntervalDifferentiable and returns interval enclosures of its values and of its even-order derivatives. A quadrature result contains the number of subintervals and the sum of the widths of the remainder-term enclosures.

  • evaluate_quadrature: Encloses the integral of an integrand over a closed interval.
  • IntervalDifferentiable: The trait through which an integrand returns enclosures of its values and derivatives.
  • QuadratureOrder: Sets the quadrature order.
  • QuadratureRefinement: Sets the quadrature order and the maximum number of subintervals.
  • QuadratureEvaluation::certify_f64: Returns the certified double-precision value of the enclosure.

Observable Result Provenance

Results of transcendental evaluation, checked surface evaluation (evaluate_surface_checked), and quadrature keep their provenance. The provenance consists of the owner identifier, the evaluation requirement, and the implementation identity.

The evaluation requirement contains the consumer identifier (the place that receives the result), the list of expression identifiers, the decision request, and the requested precision. The decision request specifies which exact decision (zero, equality, sign, or degeneracy) the consumer requests on which of the listed expressions (two expressions for equality). An expression identifier (ExprId) names a node of an expression graph in neco-expr.

The implementation identity pairs a version with a public API identifier. Accessors return each part of the provenance as well as the result value.

  • owner: The owner identifier (OwnerId).
  • requirement: The evaluation requirement (ExactExpressionRequirement).
  • source: The implementation identity (NecoImplementationSource).

§Specifications and Constraints

OperationConstraintResult at the Limit
Surface Polynomial ConstructionTerms $\le 4,096$ and each exponent $\le 256$Returns CalculusFailure for a larger input
Implicit Polynomial ConstructionTerms $\le 4,096$Returns CalculusFailure for a larger input
Derivative and Root OperationsThe order, candidate, iteration, and precision limits set by the dependency crates holdKeeps the typed failure that a dependency crate returns when a resource limit is exceeded
Transcendental EvaluationPrecision from $1$ to $256$ bits and a base above zeroReturns EvaluationFailure for any other precision or base
Series Term LimitThe number of series terms, determined by the argument magnitude and the working precision (96 bits more than the requested precision), is at most $256$Returns EvaluationFailure that wraps the typed failure of the dependency crate
Undetermined ResultThe width estimate exceeds the target widthReturns the established interval as a success value; its width can still meet the target
Double-Precision ProjectionThe result holds an exact value or an enclosureReturns TranscendentalCertificationFailure for an undetermined result
Transcendental ValidationThe candidate provenance matches the request, the requested precision is from $1$ to $256$ bits, and the enclosure width is at most the target widthReturns EvaluationFailure::Lower for a candidate whose provenance differs from the request. Returns EvaluationFailure::PrecisionShortage when the requested precision is out of range or the enclosure is wider than the target width
QuadratureThe lower bound is below the upper bound and the requested bits are from $1$ to $256$Returns a typed failure; when the width remains larger than requested, the failure keeps the enclosure reached
Subinterval DivisionTwice the order $\le 64$ and subintervals $\le 65,536$Returns CalculusFailure for a larger order or number of subintervals
Result ConstructionThe struct result types (polynomial evaluation, rational evaluation, the evaluation of a polynomial with rational coefficients, interval evaluation, transcendental evaluation results, coordinate enclosures, and quadrature results) have private fieldsOnly public functions of this crate create these results. Transcendental evaluation results, the coordinate enclosures returned by checked surface evaluation, and quadrature results carry provenance, and that provenance is observable. The enums returned by surface and implicit evaluation hold an exact value in public fields when the result is exact. For checked surface evaluation, the enum holds the coordinate enclosure

§Runtime Configuration

The default configuration uses the standard library and also enables standard-library support in every dependency crate.

[dependencies]
neco-calculus = "0.2"

Disabling the default std feature leaves dynamic memory allocation as the only runtime requirement, so the crate can be used in environments without the standard library. Public values, results, and failure meanings are the same in both configurations.

[dependencies]
neco-calculus = { version = "0.2", default-features = false }

§Dependencies

  • neco-polynomial: Canonical polynomials and validated interval evaluation.
  • neco-rational: Exact rational functions and domain validation.
  • neco-jet: Finite derivative sequences.
  • neco-root: Root brackets, narrowing witnesses, interval sign classification, and candidate root classification.
  • neco-algnum: Exact values.
  • neco-bigint: Dyadic arithmetic.
  • neco-expr: Identifiers that make up provenance, and certified f64 values.

§License

MIT License. See the repository LICENSE for details.

Structs§

AbsoluteBits
CertifiedF64
ConsumerId
ConvergenceWitness
CoordinateEnclosure3
DerivativeOrder
Enclosure
ExactExpressionRequirement
ExprId
FailureLocation
ImplicitEvaluationInput
ImplicitPolynomial3
ImplicitTerm
IntervalEvaluation
Jet
LowerWitness
MembershipJudgmentRequest
MembershipLocus
MembershipTransitionReport
NecoImplementationSource
OwnerId
Polynomial
PolynomialEvaluation
ProvenanceMismatchPayload
ProvenanceRecord
QuadratureEvaluation
QuadratureEvidence
Evidence for the width of a quadrature enclosure.
QuadratureInput
QuadratureOrder
Number of even-order Taylor terms kept before the remainder. The integrand must be continuously differentiable up to twice this number and supplies those derivatives; zero uses value enclosures alone.
QuadratureRefinement
RationalEvaluation
RationalFunction
RationalPolynomialEvaluator
RationalPolynomialInput
RationalSurfacePolynomials
RegionSignJudgment
RootBracket
RootIsolation
SurfaceEvaluationInput
SurfaceEvaluationInput2
SurfacePolynomial
SurfaceTerm
TranscendentalEvaluation
TranscendentalEvaluationConstructionInput
TranscendentalEvaluationRequest
TranscendentalFunctionEvaluationInput
TranscendentalPowerEvaluationInput

Enums§

CalculusFailure
ConvergenceStatus
DomainWitness
EnclosureProjectionError
EvaluationFailure
EvaluationInputSnapshot
EvaluationOperation
ExactDecisionRequest
FailureOperation
ImplicitEvaluationProducer
IntervalFailure
JetFailure
LowerEvaluationFailure
MembershipLocusKind
NecoFailure
NewtonFallbackReason
PolynomialFailure
PolynomialResourceFailure
PrecisionFailurePayload
PrecisionShortageCause
PrecisionWitness
ProvenanceMismatchField
RationalFailure
RegionSign
RootEvidence
RootFailure
RootMultiplicity
RootRefinementMethod
SurfaceEvaluationProducer
TranscendentalCertificationFailure
TranscendentalConnectorFailure
TranscendentalEvaluationCandidate
TranscendentalEvaluationKind
TranscendentalFunction

Constants§

MAX_COEFFICIENTS
MAX_DERIVATIVE_ORDER
MAX_IMPLICIT_TERMS
MAX_JET_ORDER
MAX_PRECISION_BITS
MAX_QUADRATURE_PIECES
MAX_SURFACE_EXPONENT
MAX_SURFACE_TERMS
MAX_TRANSCENDENTAL_SERIES_TERMS
Term limit of one series evaluation.

Traits§

IntervalDifferentiable
An integrand that also encloses its derivatives; evaluate_interval is the order-zero case and encloses the value. The quadrature trusts every enclosure and does not verify it, so its result encloses the integral only if every enclosure is true for the integrand it describes.
IntervalEvaluable
JetSource

Functions§

classify_multiplicity
classify_region_sign
construct_transcendental_evaluation
differentiate
evaluate_implicit
evaluate_interval
evaluate_polynomial
evaluate_quadrature
Encloses the integral over a closed interval with dyadic bounds by bisecting the widest piece until the enclosure meets the requested absolute bits. A spent piece budget is a failure that keeps the enclosure reached, never a success value.
evaluate_rational
evaluate_rational_polynomial
evaluate_surface
evaluate_surface_checked
evaluate_transcendental_function
Evaluates a sine, cosine, or exponential over an interval argument. Returns an undetermined result when the width estimate exceeds the target width. The interval kept by that result may still meet the target width.
evaluate_transcendental_power
Evaluates a real power of a strictly positive base interval. A base reaching zero or below fails with a domain violation.
expose_membership_transitions
expose_region_sign
jet_at
locate_membership_transitions
refine_root_bisection
refine_root_newton_bisection