Skip to main content

neco_calculus/
lib.rs

1#![cfg_attr(not(feature = "std"), no_std)]
2#![forbid(unsafe_code)]
3#![doc = include_str!("../README.md")]
4
5extern crate alloc;
6
7mod quadrature;
8
9use alloc::boxed::Box;
10use alloc::vec::Vec;
11use core::cmp::Ordering;
12use core::num::NonZeroUsize;
13
14use neco_algnum::{AlgnumError, RationalPolynomial, RealAlgebraic};
15use neco_bigint::{
16    BigInt, BigUint, BigintError, Dyadic, DyadicEnclosure, RawRational, ReducedRational, Sign,
17};
18use neco_expr::project_enclosure_f64;
19pub use neco_expr::{
20    AbsoluteBits, CertifiedF64, ConsumerId, EnclosureProjectionError, ExactDecisionRequest,
21    ExactExpressionRequirement, ExprId, FailureLocation, FailureOperation, NecoFailure,
22    NecoImplementationSource, OwnerId, PrecisionFailurePayload, ProvenanceMismatchField,
23    ProvenanceMismatchPayload, ProvenanceRecord,
24};
25pub use neco_jet::{Jet, JetFailure, MAX_JET_ORDER};
26pub use neco_polynomial::{
27    DerivativeOrder, Enclosure, IntervalFailure, Polynomial, PolynomialFailure,
28    ResourceFailure as PolynomialResourceFailure, MAX_COEFFICIENTS, MAX_DERIVATIVE_ORDER,
29    MAX_PRECISION_BITS,
30};
31pub use neco_rational::{RationalFailure, RationalFunction};
32pub use neco_root::{
33    classify_multiplicity, classify_region_sign, locate_membership_transitions, ConvergenceStatus,
34    ConvergenceWitness, MembershipJudgmentRequest, MembershipLocus, MembershipLocusKind,
35    MembershipTransitionReport, NewtonFallbackReason, RegionSign, RegionSignJudgment, RootBracket,
36    RootEvidence, RootFailure, RootIsolation, RootMultiplicity, RootRefinementMethod,
37};
38pub use quadrature::{
39    evaluate_quadrature, IntervalDifferentiable, QuadratureEvaluation, QuadratureEvidence,
40    QuadratureInput, QuadratureOrder, QuadratureRefinement,
41};
42
43pub fn expose_region_sign(
44    request: &MembershipJudgmentRequest,
45) -> Result<RegionSignJudgment, CalculusFailure> {
46    Ok(classify_region_sign(request)?)
47}
48
49pub fn expose_membership_transitions(
50    request: &MembershipJudgmentRequest,
51) -> Result<MembershipTransitionReport, CalculusFailure> {
52    Ok(locate_membership_transitions(request)?)
53}
54
55#[derive(Debug, Eq, PartialEq)]
56pub struct PolynomialEvaluation {
57    value: RealAlgebraic,
58}
59
60impl PolynomialEvaluation {
61    fn new(value: RealAlgebraic) -> Self {
62        Self { value }
63    }
64
65    pub fn value(&self) -> &RealAlgebraic {
66        &self.value
67    }
68
69    pub fn into_value(self) -> RealAlgebraic {
70        self.value
71    }
72}
73
74#[derive(Debug, Eq, PartialEq)]
75pub struct RationalEvaluation {
76    value: RealAlgebraic,
77}
78
79impl RationalEvaluation {
80    fn new(value: RealAlgebraic) -> Self {
81        Self { value }
82    }
83
84    pub fn value(&self) -> &RealAlgebraic {
85        &self.value
86    }
87
88    pub fn into_value(self) -> RealAlgebraic {
89        self.value
90    }
91}
92
93#[derive(Debug, Eq, PartialEq)]
94pub struct IntervalEvaluation {
95    enclosure: Enclosure,
96}
97
98impl IntervalEvaluation {
99    fn new(enclosure: Enclosure) -> Self {
100        Self { enclosure }
101    }
102
103    pub fn enclosure(&self) -> &Enclosure {
104        &self.enclosure
105    }
106
107    pub fn into_enclosure(self) -> Enclosure {
108        self.enclosure
109    }
110}
111
112#[derive(Clone, Copy, Debug, Eq, PartialEq)]
113pub enum TranscendentalFunction {
114    Sine,
115    Cosine,
116    Exponential,
117}
118
119#[derive(Clone, Copy, Debug, Eq, PartialEq)]
120pub enum EvaluationOperation {
121    SurfaceExact,
122    SurfaceChecked,
123    Transcendental,
124    TranscendentalFunction(TranscendentalFunction),
125    TranscendentalPower,
126    Quadrature,
127}
128
129#[derive(Debug, Eq, PartialEq)]
130pub enum EvaluationInputSnapshot {
131    SurfaceChecked {
132        surface: RationalSurfacePolynomials,
133        u: Enclosure,
134        v: Enclosure,
135    },
136    Transcendental {
137        candidate: TranscendentalEvaluationCandidate,
138    },
139    TranscendentalFunction {
140        function: TranscendentalFunction,
141        argument: Enclosure,
142    },
143    TranscendentalPower {
144        base: Enclosure,
145        exponent: Enclosure,
146    },
147    Quadrature {
148        lower: Dyadic,
149        upper: Dyadic,
150        order: QuadratureOrder,
151        maximum_pieces: NonZeroUsize,
152    },
153}
154
155#[derive(Debug, Eq, PartialEq)]
156pub enum DomainWitness {
157    ZeroDenominatorPolynomial,
158    DomainContainsZero {
159        denominator: Enclosure,
160    },
161    PointOutsideDomain {
162        point: RealAlgebraic,
163    },
164    NonPositiveBase {
165        base: Enclosure,
166        exponent: Enclosure,
167    },
168    NonIncreasingBounds {
169        lower: Dyadic,
170        upper: Dyadic,
171    },
172}
173
174#[derive(Debug, Eq, PartialEq)]
175pub enum PrecisionWitness {
176    Limit { maximum: u32 },
177    Enclosure { enclosure: Enclosure },
178}
179
180#[derive(Debug, Eq, PartialEq)]
181pub enum PrecisionShortageCause {
182    RequestedBeyondLimit {
183        requested: AbsoluteBits,
184        maximum: u32,
185    },
186    Exhausted(NecoFailure),
187}
188
189#[derive(Clone, Copy, Debug, Eq, PartialEq)]
190pub struct LowerWitness {
191    operation: EvaluationOperation,
192}
193
194impl LowerWitness {
195    pub const fn new(operation: EvaluationOperation) -> Self {
196        Self { operation }
197    }
198
199    pub const fn operation(&self) -> EvaluationOperation {
200        self.operation
201    }
202}
203
204#[derive(Debug, Eq, PartialEq)]
205pub enum LowerEvaluationFailure {
206    Calculus(Box<CalculusFailure>),
207    Expression(NecoFailure),
208}
209
210#[derive(Debug, Eq, PartialEq)]
211pub enum EvaluationFailure {
212    ZeroImplicitTerm,
213    DuplicateImplicitExponent,
214    SurfaceTermLimitExceeded {
215        requested: usize,
216        maximum: usize,
217    },
218    SurfaceExponentLimitExceeded {
219        requested: u32,
220        maximum: u32,
221    },
222    ImplicitTermLimitExceeded {
223        requested: usize,
224        maximum: usize,
225    },
226    DomainViolation {
227        operation: EvaluationOperation,
228        owner: OwnerId,
229        requirement: ExactExpressionRequirement,
230        source: NecoImplementationSource,
231        input: EvaluationInputSnapshot,
232        witness: DomainWitness,
233        lower: RationalFailure,
234    },
235    TranscendentalDomainViolation {
236        operation: EvaluationOperation,
237        owner: OwnerId,
238        requirement: ExactExpressionRequirement,
239        source: NecoImplementationSource,
240        input: EvaluationInputSnapshot,
241        witness: DomainWitness,
242    },
243    PrecisionShortage {
244        operation: EvaluationOperation,
245        owner: OwnerId,
246        requirement: ExactExpressionRequirement,
247        source: NecoImplementationSource,
248        input: EvaluationInputSnapshot,
249        requested: AbsoluteBits,
250        witness: PrecisionWitness,
251        lower: PrecisionShortageCause,
252    },
253    Lower {
254        operation: EvaluationOperation,
255        owner: OwnerId,
256        requirement: ExactExpressionRequirement,
257        source: NecoImplementationSource,
258        input: EvaluationInputSnapshot,
259        witness: LowerWitness,
260        lower: LowerEvaluationFailure,
261    },
262    QuadraturePieceLimitExceeded {
263        requested: usize,
264        maximum: usize,
265    },
266    QuadratureDomainViolation {
267        operation: EvaluationOperation,
268        owner: OwnerId,
269        requirement: ExactExpressionRequirement,
270        source: NecoImplementationSource,
271        input: EvaluationInputSnapshot,
272        witness: DomainWitness,
273    },
274    QuadratureNotConverged {
275        operation: EvaluationOperation,
276        owner: OwnerId,
277        requirement: ExactExpressionRequirement,
278        source: NecoImplementationSource,
279        input: EvaluationInputSnapshot,
280        achieved: Enclosure,
281        evidence: QuadratureEvidence,
282    },
283}
284
285pub const MAX_SURFACE_TERMS: usize = 4_096;
286pub const MAX_SURFACE_EXPONENT: u32 = 256;
287pub const MAX_IMPLICIT_TERMS: usize = 4_096;
288pub const MAX_QUADRATURE_PIECES: usize = 65_536;
289
290#[derive(Debug, Eq, PartialEq)]
291pub enum CalculusFailure {
292    Polynomial(PolynomialFailure),
293    Rational(RationalFailure),
294    Jet(JetFailure),
295    Interval(IntervalFailure),
296    Root(RootFailure),
297    Transcendental(TranscendentalConnectorFailure),
298    Evaluation(Box<EvaluationFailure>),
299    Algebra(AlgnumError),
300    Arithmetic(BigintError),
301}
302
303#[derive(Debug, Eq, PartialEq)]
304pub struct TranscendentalEvaluationRequest {
305    owner: OwnerId,
306    requirement: ExactExpressionRequirement,
307    source: NecoImplementationSource,
308}
309
310impl TranscendentalEvaluationRequest {
311    pub fn new(
312        owner: OwnerId,
313        requirement: ExactExpressionRequirement,
314        source: NecoImplementationSource,
315    ) -> Self {
316        Self {
317            owner,
318            requirement,
319            source,
320        }
321    }
322
323    pub const fn owner(&self) -> OwnerId {
324        self.owner
325    }
326
327    pub fn requirement(&self) -> &ExactExpressionRequirement {
328        &self.requirement
329    }
330
331    pub const fn source(&self) -> NecoImplementationSource {
332        self.source
333    }
334}
335
336#[derive(Debug, Eq, PartialEq)]
337pub enum TranscendentalEvaluationCandidate {
338    ExactAlgebraic {
339        value: RealAlgebraic,
340        owner: OwnerId,
341        requirement: ExactExpressionRequirement,
342        source: NecoImplementationSource,
343    },
344    Enclosure {
345        enclosure: Enclosure,
346        owner: OwnerId,
347        requirement: ExactExpressionRequirement,
348        source: NecoImplementationSource,
349    },
350    Undetermined {
351        achieved: Enclosure,
352        owner: OwnerId,
353        requirement: ExactExpressionRequirement,
354        source: NecoImplementationSource,
355    },
356}
357
358#[derive(Debug, Eq, PartialEq)]
359pub struct TranscendentalEvaluationConstructionInput {
360    candidate: TranscendentalEvaluationCandidate,
361    request: TranscendentalEvaluationRequest,
362}
363
364impl TranscendentalEvaluationConstructionInput {
365    pub const fn new(
366        candidate: TranscendentalEvaluationCandidate,
367        request: TranscendentalEvaluationRequest,
368    ) -> Self {
369        Self { candidate, request }
370    }
371}
372
373#[derive(Clone, Copy, Debug, Eq, PartialEq)]
374pub enum TranscendentalEvaluationKind {
375    ExactAlgebraic,
376    Enclosure,
377    Undetermined,
378}
379
380#[derive(Debug, Eq, PartialEq)]
381enum TranscendentalEvaluationValue {
382    ExactAlgebraic {
383        value: RealAlgebraic,
384        owner: OwnerId,
385        requirement: ExactExpressionRequirement,
386        source: NecoImplementationSource,
387    },
388    Enclosure {
389        enclosure: Enclosure,
390        owner: OwnerId,
391        requirement: ExactExpressionRequirement,
392        source: NecoImplementationSource,
393    },
394    Undetermined {
395        achieved: Enclosure,
396        owner: OwnerId,
397        requirement: ExactExpressionRequirement,
398        source: NecoImplementationSource,
399    },
400}
401
402#[derive(Debug, Eq, PartialEq)]
403pub struct TranscendentalEvaluation {
404    value: TranscendentalEvaluationValue,
405}
406
407impl TranscendentalEvaluation {
408    pub const fn kind(&self) -> TranscendentalEvaluationKind {
409        match &self.value {
410            TranscendentalEvaluationValue::ExactAlgebraic { .. } => {
411                TranscendentalEvaluationKind::ExactAlgebraic
412            }
413            TranscendentalEvaluationValue::Enclosure { .. } => {
414                TranscendentalEvaluationKind::Enclosure
415            }
416            TranscendentalEvaluationValue::Undetermined { .. } => {
417                TranscendentalEvaluationKind::Undetermined
418            }
419        }
420    }
421
422    pub fn as_exact_algebraic(&self) -> Option<&RealAlgebraic> {
423        match &self.value {
424            TranscendentalEvaluationValue::ExactAlgebraic { value, .. } => Some(value),
425            _ => None,
426        }
427    }
428
429    pub fn as_enclosure(&self) -> Option<&Enclosure> {
430        match &self.value {
431            TranscendentalEvaluationValue::Enclosure { enclosure, .. } => Some(enclosure),
432            _ => None,
433        }
434    }
435
436    pub const fn is_undetermined(&self) -> bool {
437        matches!(
438            self.value,
439            TranscendentalEvaluationValue::Undetermined { .. }
440        )
441    }
442
443    pub const fn owner(&self) -> OwnerId {
444        match &self.value {
445            TranscendentalEvaluationValue::ExactAlgebraic { owner, .. }
446            | TranscendentalEvaluationValue::Enclosure { owner, .. }
447            | TranscendentalEvaluationValue::Undetermined { owner, .. } => *owner,
448        }
449    }
450
451    pub fn requirement(&self) -> &ExactExpressionRequirement {
452        match &self.value {
453            TranscendentalEvaluationValue::ExactAlgebraic { requirement, .. }
454            | TranscendentalEvaluationValue::Enclosure { requirement, .. }
455            | TranscendentalEvaluationValue::Undetermined { requirement, .. } => requirement,
456        }
457    }
458
459    pub const fn source(&self) -> NecoImplementationSource {
460        match &self.value {
461            TranscendentalEvaluationValue::ExactAlgebraic { source, .. }
462            | TranscendentalEvaluationValue::Enclosure { source, .. }
463            | TranscendentalEvaluationValue::Undetermined { source, .. } => *source,
464        }
465    }
466
467    /// Interval kept when the width estimate exceeds the target width. Its
468    /// actual width can still meet the target.
469    pub fn undetermined_achieved(&self) -> Option<&Enclosure> {
470        match &self.value {
471            TranscendentalEvaluationValue::Undetermined { achieved, .. } => Some(achieved),
472            _ => None,
473        }
474    }
475
476    /// Nearest f64 with the enclosure and absolute error of the rounding.
477    pub fn certify_f64(&self) -> Result<CertifiedF64, TranscendentalCertificationFailure> {
478        let (enclosure, requirement) = match &self.value {
479            TranscendentalEvaluationValue::ExactAlgebraic {
480                value, requirement, ..
481            } => {
482                let isolating = value
483                    .enclose(requirement.precision().get())
484                    .map_err(TranscendentalCertificationFailure::Algebraic)?;
485                (isolating.enclosure().try_clone(), requirement)
486            }
487            TranscendentalEvaluationValue::Enclosure {
488                enclosure,
489                requirement,
490                ..
491            } => (enclosure.as_dyadic_enclosure().try_clone(), requirement),
492            TranscendentalEvaluationValue::Undetermined { .. } => {
493                return Err(TranscendentalCertificationFailure::Undetermined)
494            }
495        };
496        let enclosure = enclosure.map_err(|error| {
497            TranscendentalCertificationFailure::Projection(EnclosureProjectionError::Bigint(error))
498        })?;
499        project_enclosure_f64(enclosure, requirement.precision())
500            .map_err(TranscendentalCertificationFailure::Projection)
501    }
502}
503
504#[derive(Clone, Copy, Debug, Eq, PartialEq)]
505pub enum TranscendentalConnectorFailure {
506    PrecisionLimitExceeded { requested: u32, maximum: u32 },
507    PrecisionMustBePositive,
508    EnclosureTooWide { requested_precision_bits: u32 },
509}
510
511#[derive(Debug, Eq, PartialEq)]
512pub enum TranscendentalCertificationFailure {
513    Undetermined,
514    Algebraic(AlgnumError),
515    Projection(EnclosureProjectionError),
516}
517
518#[derive(Debug, Eq, PartialEq)]
519pub struct TranscendentalFunctionEvaluationInput {
520    pub function: TranscendentalFunction,
521    pub argument: Enclosure,
522    pub request: TranscendentalEvaluationRequest,
523}
524
525#[derive(Debug, Eq, PartialEq)]
526pub struct TranscendentalPowerEvaluationInput {
527    pub base: Enclosure,
528    pub exponent: Enclosure,
529    pub request: TranscendentalEvaluationRequest,
530}
531
532/// Term limit of one series evaluation.
533pub const MAX_TRANSCENDENTAL_SERIES_TERMS: u32 = 256;
534
535pub fn evaluate_polynomial(
536    polynomial: &Polynomial,
537    point: &RealAlgebraic,
538) -> Result<PolynomialEvaluation, CalculusFailure> {
539    Ok(PolynomialEvaluation::new(polynomial.evaluate(point)?))
540}
541
542pub struct RationalPolynomialInput {
543    pub polynomial: RationalPolynomial,
544    pub point: RealAlgebraic,
545}
546
547#[derive(Debug, Eq, PartialEq)]
548pub struct RationalPolynomialEvaluator {
549    value: RealAlgebraic,
550}
551
552impl RationalPolynomialEvaluator {
553    pub fn value(&self) -> &RealAlgebraic {
554        &self.value
555    }
556
557    pub fn into_value(self) -> RealAlgebraic {
558        self.value
559    }
560}
561
562pub fn evaluate_rational_polynomial(
563    input: RationalPolynomialInput,
564) -> Result<RationalPolynomialEvaluator, CalculusFailure> {
565    if input.polynomial.coefficients().len() > MAX_COEFFICIENTS {
566        return Err(PolynomialFailure::Resource(
567            PolynomialResourceFailure::CoefficientLimitExceeded {
568                requested: input.polynomial.coefficients().len(),
569                maximum: MAX_COEFFICIENTS,
570            },
571        )
572        .into());
573    }
574    let coefficients = input.polynomial.to_real_algebraic_coefficients()?;
575    let polynomial = Polynomial::from_coefficients(coefficients.into_coefficients())?;
576    Ok(RationalPolynomialEvaluator {
577        value: polynomial.evaluate(&input.point)?,
578    })
579}
580
581pub fn evaluate_rational(
582    function: &RationalFunction,
583    point: &RealAlgebraic,
584) -> Result<RationalEvaluation, CalculusFailure> {
585    Ok(RationalEvaluation::new(function.evaluate(point)?))
586}
587
588pub fn differentiate(
589    polynomial: &Polynomial,
590    order: DerivativeOrder,
591) -> Result<Polynomial, CalculusFailure> {
592    Ok(polynomial.derivative(order)?)
593}
594
595pub trait JetSource {
596    fn jet_at(&self, point: &RealAlgebraic, order: DerivativeOrder)
597        -> Result<Jet, CalculusFailure>;
598}
599
600impl JetSource for Polynomial {
601    fn jet_at(
602        &self,
603        point: &RealAlgebraic,
604        order: DerivativeOrder,
605    ) -> Result<Jet, CalculusFailure> {
606        validate_jet_order(order)?;
607        let mut derivatives = Vec::new();
608        for current in 0..=order.get() {
609            derivatives.push(
610                self.derivative(DerivativeOrder::new(current))?
611                    .evaluate(point)?,
612            );
613        }
614        let value = derivatives[0].try_clone()?;
615        Ok(Jet::from_value_and_derivatives(value, derivatives)?)
616    }
617}
618
619pub fn jet_at<F>(
620    function: &F,
621    point: &RealAlgebraic,
622    order: DerivativeOrder,
623) -> Result<Jet, CalculusFailure>
624where
625    F: JetSource + ?Sized,
626{
627    validate_jet_order(order)?;
628    function.jet_at(point, order)
629}
630
631fn validate_jet_order(order: DerivativeOrder) -> Result<(), CalculusFailure> {
632    if order.get() > MAX_JET_ORDER {
633        return Err(JetFailure::OrderLimitExceeded {
634            requested: order.get(),
635            maximum: MAX_JET_ORDER,
636        }
637        .into());
638    }
639    Ok(())
640}
641
642pub trait IntervalEvaluable {
643    fn evaluate_interval(
644        &self,
645        domain: &Enclosure,
646        precision_bits: u32,
647    ) -> Result<Enclosure, CalculusFailure>;
648}
649
650impl IntervalEvaluable for Polynomial {
651    fn evaluate_interval(
652        &self,
653        domain: &Enclosure,
654        precision_bits: u32,
655    ) -> Result<Enclosure, CalculusFailure> {
656        Ok(self.evaluate_enclosure(domain, precision_bits)?)
657    }
658}
659
660impl IntervalEvaluable for RationalFunction {
661    fn evaluate_interval(
662        &self,
663        domain: &Enclosure,
664        precision_bits: u32,
665    ) -> Result<Enclosure, CalculusFailure> {
666        Ok(self.evaluate_on(domain, precision_bits)?)
667    }
668}
669
670pub fn evaluate_interval<F>(
671    function: &F,
672    domain: &Enclosure,
673    precision_bits: u32,
674) -> Result<IntervalEvaluation, CalculusFailure>
675where
676    F: IntervalEvaluable + ?Sized,
677{
678    Ok(IntervalEvaluation::new(
679        function.evaluate_interval(domain, precision_bits)?,
680    ))
681}
682
683#[derive(Debug, Eq, PartialEq)]
684pub struct SurfaceTerm {
685    pub coefficient: neco_bigint::ReducedRational,
686    pub exponent_u: u32,
687    pub exponent_v: u32,
688}
689
690#[derive(Debug, Eq, PartialEq)]
691pub struct SurfacePolynomial {
692    terms: Vec<SurfaceTerm>,
693}
694
695impl SurfacePolynomial {
696    pub fn try_from_terms(mut terms: Vec<SurfaceTerm>) -> Result<Self, CalculusFailure> {
697        if terms.len() > MAX_SURFACE_TERMS {
698            return Err(EvaluationFailure::SurfaceTermLimitExceeded {
699                requested: terms.len(),
700                maximum: MAX_SURFACE_TERMS,
701            }
702            .into());
703        }
704        for term in &terms {
705            if term.exponent_u > MAX_SURFACE_EXPONENT {
706                return Err(EvaluationFailure::SurfaceExponentLimitExceeded {
707                    requested: term.exponent_u,
708                    maximum: MAX_SURFACE_EXPONENT,
709                }
710                .into());
711            }
712            if term.exponent_v > MAX_SURFACE_EXPONENT {
713                return Err(EvaluationFailure::SurfaceExponentLimitExceeded {
714                    requested: term.exponent_v,
715                    maximum: MAX_SURFACE_EXPONENT,
716                }
717                .into());
718            }
719        }
720        terms.sort_unstable_by_key(|term| (term.exponent_u, term.exponent_v));
721
722        let mut normalized: Vec<SurfaceTerm> = Vec::with_capacity(terms.len());
723        for term in terms {
724            if term.coefficient.is_zero() {
725                continue;
726            }
727            if let Some(previous) = normalized.last_mut() {
728                if (previous.exponent_u, previous.exponent_v) == (term.exponent_u, term.exponent_v)
729                {
730                    previous.coefficient = previous.coefficient.add(&term.coefficient)?;
731                    if previous.coefficient.is_zero() {
732                        normalized.pop();
733                    }
734                    continue;
735                }
736            }
737            normalized.push(term);
738        }
739        Ok(Self { terms: normalized })
740    }
741
742    pub fn terms(&self) -> &[SurfaceTerm] {
743        &self.terms
744    }
745}
746
747pub struct SurfaceEvaluationInput {
748    pub x: SurfacePolynomial,
749    pub y: SurfacePolynomial,
750    pub z: SurfacePolynomial,
751    pub denominator: SurfacePolynomial,
752    pub u: RealAlgebraic,
753    pub v: RealAlgebraic,
754}
755
756#[derive(Debug, Eq, PartialEq)]
757pub struct RationalSurfacePolynomials {
758    pub x: SurfacePolynomial,
759    pub y: SurfacePolynomial,
760    pub z: SurfacePolynomial,
761    pub denominator: SurfacePolynomial,
762}
763
764#[derive(Debug, Eq, PartialEq)]
765pub struct SurfaceEvaluationInput2 {
766    surface: RationalSurfacePolynomials,
767    u: Enclosure,
768    v: Enclosure,
769    owner: OwnerId,
770    requirement: ExactExpressionRequirement,
771    source: NecoImplementationSource,
772}
773
774impl SurfaceEvaluationInput2 {
775    pub fn new(
776        surface: RationalSurfacePolynomials,
777        u: Enclosure,
778        v: Enclosure,
779        owner: OwnerId,
780        requirement: ExactExpressionRequirement,
781        source: NecoImplementationSource,
782    ) -> Result<Self, CalculusFailure> {
783        let requested = requirement.precision();
784        if requested.get() == 0 || requested.get() > MAX_PRECISION_BITS {
785            return Err(EvaluationFailure::PrecisionShortage {
786                operation: EvaluationOperation::SurfaceChecked,
787                owner,
788                requirement,
789                source,
790                input: EvaluationInputSnapshot::SurfaceChecked { surface, u, v },
791                requested,
792                witness: PrecisionWitness::Limit {
793                    maximum: MAX_PRECISION_BITS,
794                },
795                lower: PrecisionShortageCause::RequestedBeyondLimit {
796                    requested,
797                    maximum: MAX_PRECISION_BITS,
798                },
799            }
800            .into());
801        }
802        Ok(Self {
803            surface,
804            u,
805            v,
806            owner,
807            requirement,
808            source,
809        })
810    }
811
812    pub fn surface(&self) -> &RationalSurfacePolynomials {
813        &self.surface
814    }
815
816    pub fn u(&self) -> &Enclosure {
817        &self.u
818    }
819
820    pub fn v(&self) -> &Enclosure {
821        &self.v
822    }
823
824    pub const fn owner(&self) -> OwnerId {
825        self.owner
826    }
827
828    pub fn requirement(&self) -> &ExactExpressionRequirement {
829        &self.requirement
830    }
831
832    pub const fn source(&self) -> NecoImplementationSource {
833        self.source
834    }
835}
836
837#[derive(Debug, Eq, PartialEq)]
838pub struct CoordinateEnclosure3 {
839    x: Enclosure,
840    y: Enclosure,
841    z: Enclosure,
842    owner: OwnerId,
843    requirement: ExactExpressionRequirement,
844    source: NecoImplementationSource,
845}
846
847impl CoordinateEnclosure3 {
848    fn new(
849        x: Enclosure,
850        y: Enclosure,
851        z: Enclosure,
852        owner: OwnerId,
853        requirement: ExactExpressionRequirement,
854        source: NecoImplementationSource,
855    ) -> Self {
856        Self {
857            x,
858            y,
859            z,
860            owner,
861            requirement,
862            source,
863        }
864    }
865
866    pub fn x(&self) -> &Enclosure {
867        &self.x
868    }
869
870    pub fn y(&self) -> &Enclosure {
871        &self.y
872    }
873
874    pub fn z(&self) -> &Enclosure {
875        &self.z
876    }
877
878    pub const fn owner(&self) -> OwnerId {
879        self.owner
880    }
881
882    pub fn requirement(&self) -> &ExactExpressionRequirement {
883        &self.requirement
884    }
885
886    pub const fn source(&self) -> NecoImplementationSource {
887        self.source
888    }
889}
890
891#[derive(Debug, Eq, PartialEq)]
892pub enum SurfaceEvaluationProducer {
893    Exact {
894        x: RealAlgebraic,
895        y: RealAlgebraic,
896        z: RealAlgebraic,
897    },
898    Certified {
899        coordinates: Box<CoordinateEnclosure3>,
900    },
901}
902
903pub fn evaluate_surface_checked(
904    input: SurfaceEvaluationInput2,
905) -> Result<SurfaceEvaluationProducer, CalculusFailure> {
906    let SurfaceEvaluationInput2 {
907        surface,
908        u,
909        v,
910        owner,
911        requirement,
912        source,
913    } = input;
914    if surface.denominator.terms.is_empty() {
915        return Err(EvaluationFailure::DomainViolation {
916            operation: EvaluationOperation::SurfaceChecked,
917            owner,
918            requirement,
919            source,
920            input: EvaluationInputSnapshot::SurfaceChecked { surface, u, v },
921            witness: DomainWitness::ZeroDenominatorPolynomial,
922            lower: RationalFailure::ZeroDenominatorPolynomial,
923        }
924        .into());
925    }
926    let denominator = match evaluate_surface_polynomial_interval(
927        &surface.denominator,
928        &u,
929        &v,
930        requirement.precision().get(),
931    ) {
932        Ok(value) => value,
933        Err(error) => {
934            return Err(evaluation_lower_failure(
935                EvaluationOperation::SurfaceChecked,
936                owner,
937                requirement,
938                source,
939                EvaluationInputSnapshot::SurfaceChecked { surface, u, v },
940                error,
941            ))
942        }
943    };
944    if denominator.contains_zero() {
945        return Err(EvaluationFailure::DomainViolation {
946            operation: EvaluationOperation::SurfaceChecked,
947            owner,
948            requirement,
949            source,
950            input: EvaluationInputSnapshot::SurfaceChecked { surface, u, v },
951            witness: DomainWitness::DomainContainsZero { denominator },
952            lower: RationalFailure::DomainContainsZero,
953        }
954        .into());
955    }
956    let x = match evaluate_surface_polynomial_interval(
957        &surface.x,
958        &u,
959        &v,
960        requirement.precision().get(),
961    ) {
962        Ok(value) => value,
963        Err(error) => {
964            return Err(evaluation_lower_failure(
965                EvaluationOperation::SurfaceChecked,
966                owner,
967                requirement,
968                source,
969                EvaluationInputSnapshot::SurfaceChecked { surface, u, v },
970                error,
971            ))
972        }
973    };
974    let y = match evaluate_surface_polynomial_interval(
975        &surface.y,
976        &u,
977        &v,
978        requirement.precision().get(),
979    ) {
980        Ok(value) => value,
981        Err(error) => {
982            return Err(evaluation_lower_failure(
983                EvaluationOperation::SurfaceChecked,
984                owner,
985                requirement,
986                source,
987                EvaluationInputSnapshot::SurfaceChecked { surface, u, v },
988                error,
989            ))
990        }
991    };
992    let z = match evaluate_surface_polynomial_interval(
993        &surface.z,
994        &u,
995        &v,
996        requirement.precision().get(),
997    ) {
998        Ok(value) => value,
999        Err(error) => {
1000            return Err(evaluation_lower_failure(
1001                EvaluationOperation::SurfaceChecked,
1002                owner,
1003                requirement,
1004                source,
1005                EvaluationInputSnapshot::SurfaceChecked { surface, u, v },
1006                error,
1007            ))
1008        }
1009    };
1010    let x = match enclosure_div(
1011        x.as_dyadic_enclosure(),
1012        denominator.as_dyadic_enclosure(),
1013        requirement.precision().get(),
1014    ) {
1015        Ok(value) => Enclosure::from_dyadic_enclosure(value),
1016        Err(error) => {
1017            return Err(evaluation_lower_failure(
1018                EvaluationOperation::SurfaceChecked,
1019                owner,
1020                requirement,
1021                source,
1022                EvaluationInputSnapshot::SurfaceChecked { surface, u, v },
1023                error.into(),
1024            ))
1025        }
1026    };
1027    let y = match enclosure_div(
1028        y.as_dyadic_enclosure(),
1029        denominator.as_dyadic_enclosure(),
1030        requirement.precision().get(),
1031    ) {
1032        Ok(value) => Enclosure::from_dyadic_enclosure(value),
1033        Err(error) => {
1034            return Err(evaluation_lower_failure(
1035                EvaluationOperation::SurfaceChecked,
1036                owner,
1037                requirement,
1038                source,
1039                EvaluationInputSnapshot::SurfaceChecked { surface, u, v },
1040                error.into(),
1041            ))
1042        }
1043    };
1044    let z = match enclosure_div(
1045        z.as_dyadic_enclosure(),
1046        denominator.as_dyadic_enclosure(),
1047        requirement.precision().get(),
1048    ) {
1049        Ok(value) => Enclosure::from_dyadic_enclosure(value),
1050        Err(error) => {
1051            return Err(evaluation_lower_failure(
1052                EvaluationOperation::SurfaceChecked,
1053                owner,
1054                requirement,
1055                source,
1056                EvaluationInputSnapshot::SurfaceChecked { surface, u, v },
1057                error.into(),
1058            ))
1059        }
1060    };
1061    Ok(SurfaceEvaluationProducer::Certified {
1062        coordinates: Box::new(CoordinateEnclosure3::new(
1063            x,
1064            y,
1065            z,
1066            owner,
1067            requirement,
1068            source,
1069        )),
1070    })
1071}
1072
1073fn precision_shortage_location(requirement: &ExactExpressionRequirement) -> FailureLocation {
1074    FailureLocation::operation(FailureOperation::Resolve)
1075        .with_consumer(requirement.consumer_id())
1076        .with_expr(
1077            requirement
1078                .expressions()
1079                .first()
1080                .copied()
1081                .unwrap_or_else(|| ExprId::new(0)),
1082        )
1083}
1084
1085fn evaluation_lower_failure(
1086    operation: EvaluationOperation,
1087    owner: OwnerId,
1088    requirement: ExactExpressionRequirement,
1089    source: NecoImplementationSource,
1090    input: EvaluationInputSnapshot,
1091    error: CalculusFailure,
1092) -> CalculusFailure {
1093    EvaluationFailure::Lower {
1094        operation,
1095        owner,
1096        requirement,
1097        source,
1098        input,
1099        witness: LowerWitness::new(operation),
1100        lower: LowerEvaluationFailure::Calculus(Box::new(error)),
1101    }
1102    .into()
1103}
1104
1105fn evaluate_surface_polynomial_interval(
1106    polynomial: &SurfacePolynomial,
1107    u: &Enclosure,
1108    v: &Enclosure,
1109    precision_bits: u32,
1110) -> Result<Enclosure, CalculusFailure> {
1111    let mut result = DyadicEnclosure::new(
1112        Dyadic::new(BigInt::zero(), 0),
1113        Dyadic::new(BigInt::zero(), 0),
1114    )?;
1115    for term in &polynomial.terms {
1116        let coefficient = RealAlgebraic::from_reduced_rational(&term.coefficient)?
1117            .enclose(precision_bits)?
1118            .enclosure()
1119            .try_clone()?;
1120        let u_power = interval_power_horner(u.as_dyadic_enclosure(), term.exponent_u)?;
1121        let v_power = interval_power_horner(v.as_dyadic_enclosure(), term.exponent_v)?;
1122        let term_value = enclosure_mul(&enclosure_mul(&u_power, &v_power)?, &coefficient)?;
1123        result = enclosure_add(&result, &term_value)?;
1124    }
1125    Ok(Enclosure::from_dyadic_enclosure(result))
1126}
1127
1128fn interval_power_horner(
1129    base: &DyadicEnclosure,
1130    exponent: u32,
1131) -> Result<DyadicEnclosure, CalculusFailure> {
1132    let mut result = DyadicEnclosure::new(
1133        Dyadic::new(BigInt::try_from(1_u8)?, 0),
1134        Dyadic::new(BigInt::try_from(1_u8)?, 0),
1135    )?;
1136    for _ in 0..exponent {
1137        result = enclosure_mul(&result, base)?;
1138    }
1139    Ok(result)
1140}
1141
1142fn enclosure_add(
1143    left: &DyadicEnclosure,
1144    right: &DyadicEnclosure,
1145) -> Result<DyadicEnclosure, BigintError> {
1146    DyadicEnclosure::new(
1147        left.lower().add(right.lower())?,
1148        left.upper().add(right.upper())?,
1149    )
1150}
1151
1152fn enclosure_mul(
1153    left: &DyadicEnclosure,
1154    right: &DyadicEnclosure,
1155) -> Result<DyadicEnclosure, BigintError> {
1156    let candidates = [
1157        left.lower().mul(right.lower())?,
1158        left.lower().mul(right.upper())?,
1159        left.upper().mul(right.lower())?,
1160        left.upper().mul(right.upper())?,
1161    ];
1162    let mut lower = candidates[0].try_clone()?;
1163    let mut upper = candidates[0].try_clone()?;
1164    for candidate in candidates.iter().skip(1) {
1165        if candidate.cmp(&lower) == Ordering::Less {
1166            lower = candidate.try_clone()?;
1167        }
1168        if candidate.cmp(&upper) == Ordering::Greater {
1169            upper = candidate.try_clone()?;
1170        }
1171    }
1172    DyadicEnclosure::new(lower, upper)
1173}
1174
1175fn enclosure_div(
1176    numerator: &DyadicEnclosure,
1177    denominator: &DyadicEnclosure,
1178    precision_bits: u32,
1179) -> Result<DyadicEnclosure, BigintError> {
1180    let candidates = [
1181        dyadic_to_rational(numerator.lower())?.div(&dyadic_to_rational(denominator.lower())?)?,
1182        dyadic_to_rational(numerator.lower())?.div(&dyadic_to_rational(denominator.upper())?)?,
1183        dyadic_to_rational(numerator.upper())?.div(&dyadic_to_rational(denominator.lower())?)?,
1184        dyadic_to_rational(numerator.upper())?.div(&dyadic_to_rational(denominator.upper())?)?,
1185    ];
1186    let mut lower = candidates[0].try_clone()?;
1187    let mut upper = candidates[0].try_clone()?;
1188    for candidate in candidates.iter().skip(1) {
1189        if candidate.cmp(&lower) == Ordering::Less {
1190            lower = candidate.try_clone()?;
1191        }
1192        if candidate.cmp(&upper) == Ordering::Greater {
1193            upper = candidate.try_clone()?;
1194        }
1195    }
1196    DyadicEnclosure::new(
1197        lower.dyadic_floor(precision_bits)?,
1198        upper.dyadic_ceil(precision_bits)?,
1199    )
1200}
1201
1202fn dyadic_to_rational(value: &Dyadic) -> Result<ReducedRational, BigintError> {
1203    let denominator = BigUint::one()?.shl_bits(value.exponent() as usize)?;
1204    RawRational::new(value.integer().try_clone()?, denominator)
1205        .reduce()
1206        .map(|reduction| reduction.into_reduced())
1207}
1208
1209pub fn evaluate_surface(
1210    input: SurfaceEvaluationInput,
1211) -> Result<SurfaceEvaluationProducer, CalculusFailure> {
1212    let denominator = evaluate_surface_polynomial(&input.denominator, &input.u, &input.v)?;
1213    if denominator.is_zero() {
1214        return Err(CalculusFailure::Rational(RationalFailure::UndefinedDomain));
1215    }
1216    let x = evaluate_surface_polynomial(&input.x, &input.u, &input.v)?.div(&denominator)?;
1217    let y = evaluate_surface_polynomial(&input.y, &input.u, &input.v)?.div(&denominator)?;
1218    let z = evaluate_surface_polynomial(&input.z, &input.u, &input.v)?.div(&denominator)?;
1219    Ok(SurfaceEvaluationProducer::Exact { x, y, z })
1220}
1221
1222fn evaluate_surface_polynomial(
1223    polynomial: &SurfacePolynomial,
1224    u: &RealAlgebraic,
1225    v: &RealAlgebraic,
1226) -> Result<RealAlgebraic, CalculusFailure> {
1227    let mut result = RealAlgebraic::from_integer(neco_bigint::BigInt::zero())?;
1228    for term in &polynomial.terms {
1229        let coefficient = RealAlgebraic::from_reduced_rational(&term.coefficient)?;
1230        let u_power = algebraic_power(u, term.exponent_u)?;
1231        let v_power = algebraic_power(v, term.exponent_v)?;
1232        let term_value = u_power.mul(&v_power)?.mul(&coefficient)?;
1233        result = result.add(&term_value)?;
1234    }
1235    Ok(result)
1236}
1237
1238fn algebraic_power(base: &RealAlgebraic, exponent: u32) -> Result<RealAlgebraic, CalculusFailure> {
1239    if exponent == 0 {
1240        Ok(RealAlgebraic::from_integer(BigInt::try_from(1_u8)?)?)
1241    } else {
1242        Ok(base.pow_integer(&BigInt::try_from(exponent)?)?)
1243    }
1244}
1245
1246#[derive(Debug, Eq, PartialEq)]
1247pub struct ImplicitTerm {
1248    pub coefficient: RealAlgebraic,
1249    pub exponent_x: u32,
1250    pub exponent_y: u32,
1251    pub exponent_z: u32,
1252}
1253
1254#[derive(Debug, Eq, PartialEq)]
1255pub struct ImplicitPolynomial3 {
1256    terms: Vec<ImplicitTerm>,
1257}
1258
1259impl ImplicitPolynomial3 {
1260    pub fn try_from_terms(mut terms: Vec<ImplicitTerm>) -> Result<Self, CalculusFailure> {
1261        if terms.len() > MAX_IMPLICIT_TERMS {
1262            return Err(EvaluationFailure::ImplicitTermLimitExceeded {
1263                requested: terms.len(),
1264                maximum: MAX_IMPLICIT_TERMS,
1265            }
1266            .into());
1267        }
1268        terms.sort_unstable_by_key(|term| (term.exponent_x, term.exponent_y, term.exponent_z));
1269        if terms.iter().any(|term| term.coefficient.is_zero()) {
1270            return Err(EvaluationFailure::ZeroImplicitTerm.into());
1271        }
1272        if terms.windows(2).any(|pair| {
1273            (pair[0].exponent_x, pair[0].exponent_y, pair[0].exponent_z)
1274                == (pair[1].exponent_x, pair[1].exponent_y, pair[1].exponent_z)
1275        }) {
1276            return Err(EvaluationFailure::DuplicateImplicitExponent.into());
1277        }
1278        Ok(Self { terms })
1279    }
1280
1281    pub fn terms(&self) -> &[ImplicitTerm] {
1282        &self.terms
1283    }
1284}
1285
1286pub struct ImplicitEvaluationInput {
1287    pub equation: ImplicitPolynomial3,
1288    pub x: RealAlgebraic,
1289    pub y: RealAlgebraic,
1290    pub z: RealAlgebraic,
1291}
1292
1293#[derive(Debug, Eq, PartialEq)]
1294pub enum ImplicitEvaluationProducer {
1295    Exact { scalar: RealAlgebraic },
1296}
1297
1298pub fn evaluate_implicit(
1299    input: ImplicitEvaluationInput,
1300) -> Result<ImplicitEvaluationProducer, CalculusFailure> {
1301    let mut scalar = RealAlgebraic::from_integer(neco_bigint::BigInt::zero())?;
1302    for term in input.equation.terms {
1303        let value = input
1304            .x
1305            .pow_integer(&neco_bigint::BigInt::try_from(term.exponent_x)?)?
1306            .mul(
1307                &input
1308                    .y
1309                    .pow_integer(&neco_bigint::BigInt::try_from(term.exponent_y)?)?,
1310            )?
1311            .mul(
1312                &input
1313                    .z
1314                    .pow_integer(&neco_bigint::BigInt::try_from(term.exponent_z)?)?,
1315            )?
1316            .mul(&term.coefficient)?;
1317        scalar = scalar.add(&value)?;
1318    }
1319    Ok(ImplicitEvaluationProducer::Exact { scalar })
1320}
1321
1322pub fn refine_root_bisection(
1323    bracket: &RootBracket,
1324    iterations: usize,
1325) -> Result<RootIsolation, CalculusFailure> {
1326    Ok(bracket.refine_bisection(iterations)?)
1327}
1328
1329pub fn refine_root_newton_bisection(
1330    bracket: &RootBracket,
1331    iterations: usize,
1332    precision_bits: u32,
1333) -> Result<RootIsolation, CalculusFailure> {
1334    Ok(bracket.refine_newton_bisection(iterations, precision_bits)?)
1335}
1336
1337pub fn construct_transcendental_evaluation(
1338    input: TranscendentalEvaluationConstructionInput,
1339) -> Result<TranscendentalEvaluation, CalculusFailure> {
1340    let TranscendentalEvaluationConstructionInput { candidate, request } = input;
1341    let TranscendentalEvaluationRequest {
1342        owner,
1343        requirement,
1344        source,
1345    } = request;
1346    let requested = requirement.precision();
1347    if requested.get() == 0 || requested.get() > MAX_PRECISION_BITS {
1348        return Err(precision_limit_failure(
1349            EvaluationOperation::Transcendental,
1350            owner,
1351            requirement,
1352            source,
1353            EvaluationInputSnapshot::Transcendental { candidate },
1354            requested,
1355        ));
1356    }
1357    if let Err(error) = candidate_matches_request(&candidate, owner, &requirement, source) {
1358        return Err(evaluation_expression_failure(
1359            EvaluationOperation::Transcendental,
1360            owner,
1361            requirement,
1362            source,
1363            candidate,
1364            error,
1365        ));
1366    }
1367    if let TranscendentalEvaluationCandidate::Enclosure { enclosure, .. } = &candidate {
1368        let maximum_width = Dyadic::new(BigInt::try_from(1_u8)?, requested.get());
1369        let width = enclosure.width()?;
1370        if width > maximum_width {
1371            let witness = clone_enclosure_value(enclosure)?;
1372            let location = precision_shortage_location(&requirement);
1373            let lower = PrecisionShortageCause::Exhausted(NecoFailure::PrecisionExhaustion {
1374                location,
1375                requested,
1376                payload: Box::new(PrecisionFailurePayload::EnclosureWidth {
1377                    actual_width: width,
1378                }),
1379            });
1380            return Err(EvaluationFailure::PrecisionShortage {
1381                operation: EvaluationOperation::Transcendental,
1382                owner,
1383                requirement,
1384                source,
1385                input: EvaluationInputSnapshot::Transcendental { candidate },
1386                requested,
1387                witness: PrecisionWitness::Enclosure { enclosure: witness },
1388                lower,
1389            }
1390            .into());
1391        }
1392    }
1393    match candidate {
1394        TranscendentalEvaluationCandidate::ExactAlgebraic { value, .. } => {
1395            Ok(TranscendentalEvaluation {
1396                value: TranscendentalEvaluationValue::ExactAlgebraic {
1397                    value,
1398                    owner,
1399                    requirement,
1400                    source,
1401                },
1402            })
1403        }
1404        TranscendentalEvaluationCandidate::Enclosure { enclosure, .. } => {
1405            Ok(TranscendentalEvaluation {
1406                value: TranscendentalEvaluationValue::Enclosure {
1407                    enclosure,
1408                    owner,
1409                    requirement,
1410                    source,
1411                },
1412            })
1413        }
1414        TranscendentalEvaluationCandidate::Undetermined { achieved, .. } => {
1415            Ok(TranscendentalEvaluation {
1416                value: TranscendentalEvaluationValue::Undetermined {
1417                    achieved,
1418                    owner,
1419                    requirement,
1420                    source,
1421                },
1422            })
1423        }
1424    }
1425}
1426
1427fn precision_limit_failure(
1428    operation: EvaluationOperation,
1429    owner: OwnerId,
1430    requirement: ExactExpressionRequirement,
1431    source: NecoImplementationSource,
1432    input: EvaluationInputSnapshot,
1433    requested: AbsoluteBits,
1434) -> CalculusFailure {
1435    EvaluationFailure::PrecisionShortage {
1436        operation,
1437        owner,
1438        requirement,
1439        source,
1440        input,
1441        requested,
1442        witness: PrecisionWitness::Limit {
1443            maximum: MAX_PRECISION_BITS,
1444        },
1445        lower: PrecisionShortageCause::RequestedBeyondLimit {
1446            requested,
1447            maximum: MAX_PRECISION_BITS,
1448        },
1449    }
1450    .into()
1451}
1452
1453const SERIES_WORKING_GUARD_BITS: u32 = 16;
1454const SERIES_GUARD_BITS: u32 = 96;
1455const COARSE_BITS: u32 = 32;
1456const MAX_BINARY_EXPONENT: u32 = 1 << 20;
1457
1458#[derive(Debug)]
1459enum SeriesFailure {
1460    Arithmetic(BigintError),
1461    PrecisionLimit { requested: u32, maximum: u32 },
1462    ReductionRange,
1463}
1464
1465impl From<BigintError> for SeriesFailure {
1466    fn from(error: BigintError) -> Self {
1467        Self::Arithmetic(error)
1468    }
1469}
1470
1471impl From<SeriesFailure> for CalculusFailure {
1472    fn from(error: SeriesFailure) -> Self {
1473        match error {
1474            SeriesFailure::Arithmetic(error) => Self::Arithmetic(error),
1475            SeriesFailure::PrecisionLimit { requested, maximum } => {
1476                Self::Polynomial(PolynomialFailure::Resource(
1477                    PolynomialResourceFailure::PrecisionLimitExceeded { requested, maximum },
1478                ))
1479            }
1480            SeriesFailure::ReductionRange => {
1481                Self::Interval(IntervalFailure::Arithmetic(BigintError::InvalidInterval))
1482            }
1483        }
1484    }
1485}
1486
1487#[derive(Clone, Copy)]
1488enum SeriesKind {
1489    Sine,
1490    Cosine,
1491    Exponential,
1492    DoubledArtanh,
1493}
1494
1495enum TranscendentalOutcome {
1496    Exact(u8),
1497    Enclosure(Enclosure),
1498    Undetermined(Enclosure),
1499}
1500
1501const SINE_QUARTER_TURNS: [(SeriesKind, bool); 4] = [
1502    (SeriesKind::Sine, false),
1503    (SeriesKind::Cosine, false),
1504    (SeriesKind::Sine, true),
1505    (SeriesKind::Cosine, true),
1506];
1507
1508const COSINE_QUARTER_TURNS: [(SeriesKind, bool); 4] = [
1509    (SeriesKind::Cosine, false),
1510    (SeriesKind::Sine, true),
1511    (SeriesKind::Cosine, true),
1512    (SeriesKind::Sine, false),
1513];
1514
1515/// Evaluates a sine, cosine, or exponential over an interval argument.
1516/// Returns an undetermined result when the width estimate exceeds the target
1517/// width. The interval kept by that result may still meet the target width.
1518pub fn evaluate_transcendental_function(
1519    input: TranscendentalFunctionEvaluationInput,
1520) -> Result<TranscendentalEvaluation, CalculusFailure> {
1521    let TranscendentalFunctionEvaluationInput {
1522        function,
1523        argument,
1524        request,
1525    } = input;
1526    let TranscendentalEvaluationRequest {
1527        owner,
1528        requirement,
1529        source,
1530    } = request;
1531    let operation = EvaluationOperation::TranscendentalFunction(function);
1532    let requested = requirement.precision();
1533    if requested.get() == 0 || requested.get() > MAX_PRECISION_BITS {
1534        return Err(precision_limit_failure(
1535            operation,
1536            owner,
1537            requirement,
1538            source,
1539            EvaluationInputSnapshot::TranscendentalFunction { function, argument },
1540            requested,
1541        ));
1542    }
1543    let outcome = match function_outcome(function, &argument, requested) {
1544        Ok(outcome) => outcome,
1545        Err(error) => {
1546            return Err(evaluation_lower_failure(
1547                operation,
1548                owner,
1549                requirement,
1550                source,
1551                EvaluationInputSnapshot::TranscendentalFunction { function, argument },
1552                error.into(),
1553            ))
1554        }
1555    };
1556    construct_from_outcome(
1557        operation,
1558        EvaluationInputSnapshot::TranscendentalFunction { function, argument },
1559        (owner, requirement, source),
1560        outcome,
1561    )
1562    .map_err(|error| *error)
1563}
1564
1565/// Evaluates a real power of a strictly positive base interval.
1566/// A base reaching zero or below fails with a domain violation.
1567pub fn evaluate_transcendental_power(
1568    input: TranscendentalPowerEvaluationInput,
1569) -> Result<TranscendentalEvaluation, CalculusFailure> {
1570    let TranscendentalPowerEvaluationInput {
1571        base,
1572        exponent,
1573        request,
1574    } = input;
1575    let TranscendentalEvaluationRequest {
1576        owner,
1577        requirement,
1578        source,
1579    } = request;
1580    let operation = EvaluationOperation::TranscendentalPower;
1581    let requested = requirement.precision();
1582    if requested.get() == 0 || requested.get() > MAX_PRECISION_BITS {
1583        return Err(precision_limit_failure(
1584            operation,
1585            owner,
1586            requirement,
1587            source,
1588            EvaluationInputSnapshot::TranscendentalPower { base, exponent },
1589            requested,
1590        ));
1591    }
1592    if base.lower().integer().sign() != Sign::Positive {
1593        let witness = match (
1594            clone_enclosure_value(&base),
1595            clone_enclosure_value(&exponent),
1596        ) {
1597            (Ok(base), Ok(exponent)) => DomainWitness::NonPositiveBase { base, exponent },
1598            (Err(error), _) | (_, Err(error)) => {
1599                return Err(evaluation_lower_failure(
1600                    operation,
1601                    owner,
1602                    requirement,
1603                    source,
1604                    EvaluationInputSnapshot::TranscendentalPower { base, exponent },
1605                    error.into(),
1606                ))
1607            }
1608        };
1609        return Err(EvaluationFailure::TranscendentalDomainViolation {
1610            operation,
1611            owner,
1612            requirement,
1613            source,
1614            input: EvaluationInputSnapshot::TranscendentalPower { base, exponent },
1615            witness,
1616        }
1617        .into());
1618    }
1619    let outcome = match power_outcome(&base, &exponent, requested) {
1620        Ok(outcome) => outcome,
1621        Err(error) => {
1622            return Err(evaluation_lower_failure(
1623                operation,
1624                owner,
1625                requirement,
1626                source,
1627                EvaluationInputSnapshot::TranscendentalPower { base, exponent },
1628                error.into(),
1629            ))
1630        }
1631    };
1632    construct_from_outcome(
1633        operation,
1634        EvaluationInputSnapshot::TranscendentalPower { base, exponent },
1635        (owner, requirement, source),
1636        outcome,
1637    )
1638    .map_err(|error| *error)
1639}
1640
1641fn construct_from_outcome(
1642    operation: EvaluationOperation,
1643    input: EvaluationInputSnapshot,
1644    lineage: (
1645        OwnerId,
1646        ExactExpressionRequirement,
1647        NecoImplementationSource,
1648    ),
1649    outcome: TranscendentalOutcome,
1650) -> Result<TranscendentalEvaluation, Box<CalculusFailure>> {
1651    let (owner, requirement, source) = lineage;
1652    let candidate_requirement = match ExactExpressionRequirement::new(
1653        requirement.consumer_id(),
1654        requirement.expressions(),
1655        requirement.decision(),
1656        requirement.precision(),
1657    ) {
1658        Ok(duplicate) => duplicate,
1659        Err(error) => {
1660            return Err(Box::new(
1661                EvaluationFailure::Lower {
1662                    operation,
1663                    owner,
1664                    requirement,
1665                    source,
1666                    input,
1667                    witness: LowerWitness::new(operation),
1668                    lower: LowerEvaluationFailure::Expression(error),
1669                }
1670                .into(),
1671            ))
1672        }
1673    };
1674    let candidate = match outcome {
1675        TranscendentalOutcome::Exact(integer) => {
1676            let integer = match BigInt::try_from(integer) {
1677                Ok(integer) => integer,
1678                Err(error) => {
1679                    return Err(Box::new(evaluation_lower_failure(
1680                        operation,
1681                        owner,
1682                        requirement,
1683                        source,
1684                        input,
1685                        error.into(),
1686                    )))
1687                }
1688            };
1689            let value = match RealAlgebraic::from_integer(integer) {
1690                Ok(value) => value,
1691                Err(error) => {
1692                    return Err(Box::new(evaluation_lower_failure(
1693                        operation,
1694                        owner,
1695                        requirement,
1696                        source,
1697                        input,
1698                        error.into(),
1699                    )))
1700                }
1701            };
1702            TranscendentalEvaluationCandidate::ExactAlgebraic {
1703                value,
1704                owner,
1705                requirement: candidate_requirement,
1706                source,
1707            }
1708        }
1709        TranscendentalOutcome::Enclosure(enclosure) => {
1710            TranscendentalEvaluationCandidate::Enclosure {
1711                enclosure,
1712                owner,
1713                requirement: candidate_requirement,
1714                source,
1715            }
1716        }
1717        TranscendentalOutcome::Undetermined(achieved) => {
1718            TranscendentalEvaluationCandidate::Undetermined {
1719                achieved,
1720                owner,
1721                requirement: candidate_requirement,
1722                source,
1723            }
1724        }
1725    };
1726    construct_transcendental_evaluation(TranscendentalEvaluationConstructionInput::new(
1727        candidate,
1728        TranscendentalEvaluationRequest::new(owner, requirement, source),
1729    ))
1730    .map_err(Box::new)
1731}
1732
1733fn function_outcome(
1734    function: TranscendentalFunction,
1735    argument: &Enclosure,
1736    requested: AbsoluteBits,
1737) -> Result<TranscendentalOutcome, SeriesFailure> {
1738    if argument.lower().is_zero() && argument.upper().is_zero() {
1739        let exact = match function {
1740            TranscendentalFunction::Sine => 0_u8,
1741            TranscendentalFunction::Cosine | TranscendentalFunction::Exponential => 1_u8,
1742        };
1743        return Ok(TranscendentalOutcome::Exact(exact));
1744    }
1745    let precision = requested.get();
1746    let value = function_enclosure(
1747        function,
1748        argument.as_dyadic_enclosure(),
1749        precision + SERIES_GUARD_BITS,
1750    )?;
1751    let width = argument.as_dyadic_enclosure().width()?;
1752    let estimate = estimate_reachable_width(function, &width, &value)?;
1753    let value = Enclosure::from_dyadic_enclosure(value);
1754    if estimate_reaches_target(&estimate, precision)? {
1755        Ok(TranscendentalOutcome::Enclosure(value))
1756    } else {
1757        Ok(TranscendentalOutcome::Undetermined(value))
1758    }
1759}
1760
1761fn power_outcome(
1762    base: &Enclosure,
1763    exponent: &Enclosure,
1764    requested: AbsoluteBits,
1765) -> Result<TranscendentalOutcome, SeriesFailure> {
1766    let one = Dyadic::new(BigInt::one()?, 0);
1767    let base_is_one = base.lower() == &one && base.upper() == &one;
1768    if base_is_one || (exponent.lower().is_zero() && exponent.upper().is_zero()) {
1769        return Ok(TranscendentalOutcome::Exact(1));
1770    }
1771    let precision = requested.get();
1772    let bits = precision + SERIES_GUARD_BITS;
1773    let coarse = enclosure_mul(
1774        &natural_log_interval(base, COARSE_BITS)?,
1775        exponent.as_dyadic_enclosure(),
1776    )?;
1777    let growth = round_dyadic(coarse.upper(), 0, true)?;
1778    let growth = if growth.integer().sign() == Sign::Positive {
1779        unsigned_bound(growth.integer())?
1780    } else {
1781        0
1782    };
1783    let exponent_ceiling = round_dyadic(&max_magnitude(exponent.as_dyadic_enclosure())?, 0, true)?;
1784    let exponent_bits = exponent_ceiling.integer().magnitude().bit_len() as u64;
1785    let log_bits = bits + bounded_limit(growth + growth / 2 + exponent_bits + 4)?;
1786    let logarithm = natural_log_interval(base, log_bits)?;
1787    let product = round_enclosure(
1788        &enclosure_mul(&logarithm, exponent.as_dyadic_enclosure())?,
1789        log_bits,
1790    )?;
1791    let value = exponential_interval(&product, bits)?;
1792
1793    let base_width = base.as_dyadic_enclosure().width()?;
1794    let exponent_width = exponent.as_dyadic_enclosure().width()?;
1795    let base_term = base_width
1796        .mul(&max_magnitude(exponent.as_dyadic_enclosure())?)?
1797        .mul(value.upper())?;
1798    let base_term = enclosure_div(
1799        &point_enclosure(&base_term)?,
1800        &point_enclosure(base.lower())?,
1801        bits,
1802    )?;
1803    let exponent_term = exponent_width
1804        .mul(value.upper())?
1805        .mul(&max_magnitude(&logarithm)?)?;
1806    let estimate = base_term.upper().add(&exponent_term)?;
1807    let value = Enclosure::from_dyadic_enclosure(value);
1808    if estimate_reaches_target(&estimate, precision)? {
1809        Ok(TranscendentalOutcome::Enclosure(value))
1810    } else {
1811        Ok(TranscendentalOutcome::Undetermined(value))
1812    }
1813}
1814
1815fn estimate_reaches_target(estimate: &Dyadic, precision: u32) -> Result<bool, BigintError> {
1816    let slack = Dyadic::new(BigInt::one()?, precision + SERIES_GUARD_BITS / 2);
1817    let target = Dyadic::new(BigInt::one()?, precision);
1818    Ok(estimate.add(&slack)? <= target)
1819}
1820
1821fn estimate_reachable_width(
1822    function: TranscendentalFunction,
1823    width: &Dyadic,
1824    value: &DyadicEnclosure,
1825) -> Result<Dyadic, BigintError> {
1826    match function {
1827        TranscendentalFunction::Sine | TranscendentalFunction::Cosine => value.width(),
1828        TranscendentalFunction::Exponential => width.mul(value.upper()),
1829    }
1830}
1831
1832fn binary_magnitude(value: &Dyadic) -> i64 {
1833    value.integer().magnitude().bit_len() as i64 - i64::from(value.exponent())
1834}
1835
1836fn unsigned_bound(value: &BigInt) -> Result<u64, BigintError> {
1837    match value.magnitude().to_u32() {
1838        Some(bound) => Ok(u64::from(bound)),
1839        None => Err(BigintError::ExponentOverflow {
1840            required: value.magnitude().try_clone()?,
1841            maximum: MAX_BINARY_EXPONENT,
1842        }),
1843    }
1844}
1845
1846fn bounded_limit(value: u64) -> Result<u32, BigintError> {
1847    match u32::try_from(value) {
1848        Ok(bounded) if bounded <= MAX_BINARY_EXPONENT => Ok(bounded),
1849        _ => Err(BigintError::ExponentOverflow {
1850            required: BigUint::try_from(value)?,
1851            maximum: MAX_BINARY_EXPONENT,
1852        }),
1853    }
1854}
1855
1856fn integer_part_bits(value: &Dyadic) -> u64 {
1857    (value.integer().magnitude().bit_len() as u64).saturating_sub(u64::from(value.exponent()))
1858}
1859
1860fn power_of_two(exponent: u32) -> Result<BigInt, BigintError> {
1861    Ok(BigInt::from_sign_magnitude(
1862        Sign::Positive,
1863        BigUint::one()?.shl_bits(exponent as usize)?,
1864    ))
1865}
1866
1867fn round_dyadic(value: &Dyadic, bits: u32, upward: bool) -> Result<Dyadic, BigintError> {
1868    if value.exponent() <= bits {
1869        return value.try_clone();
1870    }
1871    let divisor = power_of_two(value.exponent() - bits)?;
1872    let (mut quotient, remainder) = value.integer().div_rem_euclid(&divisor)?;
1873    if upward && !remainder.is_zero() {
1874        quotient = quotient.add(&BigInt::one()?)?;
1875    }
1876    Ok(Dyadic::new(quotient, bits))
1877}
1878
1879fn round_enclosure(enclosure: &DyadicEnclosure, bits: u32) -> Result<DyadicEnclosure, BigintError> {
1880    DyadicEnclosure::new(
1881        round_dyadic(enclosure.lower(), bits, false)?,
1882        round_dyadic(enclosure.upper(), bits, true)?,
1883    )
1884}
1885
1886fn scale_by_power_of_two(value: &Dyadic, shift: i64) -> Result<Dyadic, BigintError> {
1887    if value.is_zero() {
1888        return value.try_clone();
1889    }
1890    let exponent = i64::from(value.exponent());
1891    let remaining = exponent - shift;
1892    if remaining >= 0 {
1893        let Ok(remaining_exponent) = u32::try_from(remaining) else {
1894            return Err(BigintError::ExponentOverflow {
1895                required: BigUint::try_from(remaining.unsigned_abs())?,
1896                maximum: u32::MAX,
1897            });
1898        };
1899        return Ok(Dyadic::new(
1900            value.integer().try_clone()?,
1901            remaining_exponent,
1902        ));
1903    }
1904    let left =
1905        usize::try_from(remaining.unsigned_abs()).map_err(|_| BigintError::CapacityOverflow)?;
1906    Ok(Dyadic::new(
1907        BigInt::from_sign_magnitude(
1908            value.integer().sign(),
1909            value.integer().magnitude().shl_bits(left)?,
1910        ),
1911        0,
1912    ))
1913}
1914
1915fn point_enclosure(value: &Dyadic) -> Result<DyadicEnclosure, BigintError> {
1916    DyadicEnclosure::new(value.try_clone()?, value.try_clone()?)
1917}
1918
1919fn negate_dyadic(value: &Dyadic) -> Result<Dyadic, BigintError> {
1920    Ok(Dyadic::new(value.integer().negated()?, value.exponent()))
1921}
1922
1923fn negate_enclosure(enclosure: &DyadicEnclosure) -> Result<DyadicEnclosure, BigintError> {
1924    DyadicEnclosure::new(
1925        negate_dyadic(enclosure.upper())?,
1926        negate_dyadic(enclosure.lower())?,
1927    )
1928}
1929
1930fn enclosure_sub(
1931    left: &DyadicEnclosure,
1932    right: &DyadicEnclosure,
1933) -> Result<DyadicEnclosure, BigintError> {
1934    enclosure_add(left, &negate_enclosure(right)?)
1935}
1936
1937fn max_magnitude(enclosure: &DyadicEnclosure) -> Result<Dyadic, BigintError> {
1938    let negated_lower = negate_dyadic(enclosure.lower())?;
1939    if negated_lower > *enclosure.upper() {
1940        Ok(negated_lower)
1941    } else {
1942        enclosure.upper().try_clone()
1943    }
1944}
1945
1946fn inverse_series_fixed_point(
1947    divisor: u32,
1948    scale: u32,
1949    alternating: bool,
1950) -> Result<(BigInt, u64), BigintError> {
1951    let square = BigInt::try_from(u64::from(divisor) * u64::from(divisor))?;
1952    let mut power = power_of_two(scale)?
1953        .div_rem_euclid(&BigInt::try_from(divisor)?)?
1954        .0;
1955    let mut sum = BigInt::zero();
1956    let mut count = 0_u64;
1957    let mut denominator = 1_u64;
1958    while !power.is_zero() {
1959        let term = power.div_rem_euclid(&BigInt::try_from(denominator)?)?.0;
1960        sum = if alternating && count % 2 == 1 {
1961            sum.sub(&term)?
1962        } else {
1963            sum.add(&term)?
1964        };
1965        power = power.div_rem_euclid(&square)?.0;
1966        denominator += 2;
1967        count += 1;
1968    }
1969    Ok((sum, count))
1970}
1971
1972fn pi_enclosure(bits: u32) -> Result<DyadicEnclosure, BigintError> {
1973    let scale = bits + 24;
1974    let (fifth, fifth_terms) = inverse_series_fixed_point(5, scale, true)?;
1975    let (small, small_terms) = inverse_series_fixed_point(239, scale, true)?;
1976    let center = fifth
1977        .mul(&BigInt::try_from(16_u8)?)?
1978        .sub(&small.mul(&BigInt::try_from(4_u8)?)?)?;
1979    let error = BigInt::try_from(16 * (fifth_terms + 2) + 4 * (small_terms + 2))?;
1980    DyadicEnclosure::new(
1981        Dyadic::new(center.sub(&error)?, scale),
1982        Dyadic::new(center.add(&error)?, scale),
1983    )
1984}
1985
1986fn ln2_enclosure(bits: u32) -> Result<DyadicEnclosure, BigintError> {
1987    let scale = bits + 24;
1988    let (sum, terms) = inverse_series_fixed_point(3, scale, false)?;
1989    let center = sum.mul(&BigInt::try_from(2_u8)?)?;
1990    let error = BigInt::try_from(2 * (terms + 2))?;
1991    DyadicEnclosure::new(
1992        Dyadic::new(center.sub(&error)?, scale),
1993        Dyadic::new(center.add(&error)?, scale),
1994    )
1995}
1996
1997fn series_terms(kind: SeriesKind, bits: u32) -> Result<u32, SeriesFailure> {
1998    if let SeriesKind::DoubledArtanh = kind {
1999        let terms = (bits + 4).div_ceil(4);
2000        if terms > MAX_TRANSCENDENTAL_SERIES_TERMS {
2001            return Err(SeriesFailure::PrecisionLimit {
2002                requested: bits,
2003                maximum: MAX_TRANSCENDENTAL_SERIES_TERMS * 4 - 4,
2004            });
2005        }
2006        return Ok(terms);
2007    }
2008    let growth = match kind {
2009        SeriesKind::Exponential => 2,
2010        _ => 0,
2011    };
2012    let mut factorial = BigUint::one()?;
2013    for terms in 1..=MAX_TRANSCENDENTAL_SERIES_TERMS {
2014        factorial = factorial.mul(&BigUint::try_from(terms)?)?;
2015        if factorial.bit_len() as u64 >= u64::from(bits) + 5 + growth {
2016            return Ok(terms);
2017        }
2018    }
2019    let capacity = (factorial.bit_len() as u64).saturating_sub(5 + growth);
2020    Err(SeriesFailure::PrecisionLimit {
2021        requested: bits,
2022        maximum: u32::try_from(capacity).unwrap_or(u32::MAX),
2023    })
2024}
2025
2026fn shift_left(value: &BigInt, bits: u32) -> Result<BigInt, BigintError> {
2027    Ok(BigInt::from_sign_magnitude(
2028        value.sign(),
2029        value.magnitude().shl_bits(bits as usize)?,
2030    ))
2031}
2032
2033fn divide_dyadic(
2034    value: &Dyadic,
2035    divisor: u64,
2036    bits: u32,
2037    upward: bool,
2038) -> Result<Dyadic, BigintError> {
2039    let divisor = BigInt::try_from(divisor)?;
2040    let (numerator, denominator) = if value.exponent() <= bits {
2041        (
2042            shift_left(value.integer(), bits - value.exponent())?,
2043            divisor,
2044        )
2045    } else {
2046        (
2047            value.integer().try_clone()?,
2048            divisor.mul(&power_of_two(value.exponent() - bits)?)?,
2049        )
2050    };
2051    let (mut quotient, remainder) = numerator.div_rem_euclid(&denominator)?;
2052    if upward && !remainder.is_zero() {
2053        quotient = quotient.add(&BigInt::one()?)?;
2054    }
2055    Ok(Dyadic::new(quotient, bits))
2056}
2057
2058fn divide_enclosure(
2059    enclosure: &DyadicEnclosure,
2060    divisor: u64,
2061    bits: u32,
2062) -> Result<DyadicEnclosure, BigintError> {
2063    DyadicEnclosure::new(
2064        divide_dyadic(enclosure.lower(), divisor, bits, false)?,
2065        divide_dyadic(enclosure.upper(), divisor, bits, true)?,
2066    )
2067}
2068
2069fn evaluate_bounded_series(
2070    kind: SeriesKind,
2071    domain: &DyadicEnclosure,
2072    bits: u32,
2073) -> Result<DyadicEnclosure, SeriesFailure> {
2074    let bound = match kind {
2075        SeriesKind::DoubledArtanh => Dyadic::new(BigInt::one()?, 2),
2076        _ => Dyadic::new(BigInt::one()?, 0),
2077    };
2078    if max_magnitude(domain)? > bound {
2079        return Err(SeriesFailure::ReductionRange);
2080    }
2081    let terms = series_terms(kind, bits)?;
2082    let working = bits + SERIES_WORKING_GUARD_BITS;
2083    let one = point_enclosure(&Dyadic::new(BigInt::one()?, 0))?;
2084    let value = match kind {
2085        SeriesKind::Exponential => {
2086            let mut accumulator = one.try_clone()?;
2087            for divisor in (1..terms).rev() {
2088                let step = divide_enclosure(
2089                    &enclosure_mul(domain, &accumulator)?,
2090                    u64::from(divisor),
2091                    working,
2092                )?;
2093                accumulator = round_enclosure(&enclosure_add(&one, &step)?, working)?;
2094            }
2095            accumulator
2096        }
2097        SeriesKind::Sine | SeriesKind::Cosine => {
2098            let sine = matches!(kind, SeriesKind::Sine);
2099            let square = round_enclosure(&enclosure_mul(domain, domain)?, working)?;
2100            let mut accumulator = one.try_clone()?;
2101            for index in (1..=(terms - 1) / 2).rev() {
2102                let index = u64::from(index);
2103                let divisor = if sine {
2104                    2 * index * (2 * index + 1)
2105                } else {
2106                    (2 * index - 1) * (2 * index)
2107                };
2108                let step =
2109                    divide_enclosure(&enclosure_mul(&square, &accumulator)?, divisor, working)?;
2110                accumulator = round_enclosure(&enclosure_sub(&one, &step)?, working)?;
2111            }
2112            if sine {
2113                round_enclosure(&enclosure_mul(domain, &accumulator)?, working)?
2114            } else {
2115                accumulator
2116            }
2117        }
2118        SeriesKind::DoubledArtanh => {
2119            let square = round_enclosure(&enclosure_mul(domain, domain)?, working)?;
2120            let last = u64::from(terms - 1);
2121            let mut accumulator = divide_enclosure(&one, 2 * last + 1, working)?;
2122            for index in (0..last).rev() {
2123                let carried = enclosure_mul(&square, &accumulator)?;
2124                accumulator = round_enclosure(
2125                    &enclosure_add(&divide_enclosure(&one, 2 * index + 1, working)?, &carried)?,
2126                    working,
2127                )?;
2128            }
2129            let product = enclosure_mul(domain, &accumulator)?;
2130            round_enclosure(&enclosure_add(&product, &product)?, working)?
2131        }
2132    };
2133    let remainder = Dyadic::new(BigInt::one()?, bits + 2);
2134    let lower = value.lower().sub(&remainder)?;
2135    let upper = value.upper().add(&remainder)?;
2136    Ok(round_enclosure(&DyadicEnclosure::new(lower, upper)?, bits)?)
2137}
2138
2139fn nearest_integer_ratio(
2140    numerator: &Dyadic,
2141    scale: &DyadicEnclosure,
2142) -> Result<BigInt, BigintError> {
2143    let quotient = enclosure_div(&point_enclosure(numerator)?, scale, 4)?;
2144    let half = Dyadic::new(BigInt::one()?, 1);
2145    let nearest = round_dyadic(&quotient.lower().add(&half)?, 0, false)?;
2146    nearest.integer().try_clone()
2147}
2148
2149fn trigonometric_point(
2150    sine: bool,
2151    x: &Dyadic,
2152    bits: u32,
2153) -> Result<DyadicEnclosure, SeriesFailure> {
2154    let point = round_enclosure(&point_enclosure(x)?, bits)?;
2155    let magnitude_bits = bounded_limit(integer_part_bits(x))?;
2156    let pi = pi_enclosure(bits + magnitude_bits + 16)?;
2157    let multiple = nearest_integer_ratio(&scale_by_power_of_two(point.lower(), 1)?, &pi)?;
2158    let count = point_enclosure(&Dyadic::new(multiple.try_clone()?, 0))?;
2159    let turns = enclosure_mul(&count, &pi)?;
2160    let turns = DyadicEnclosure::new(
2161        scale_by_power_of_two(turns.lower(), -1)?,
2162        scale_by_power_of_two(turns.upper(), -1)?,
2163    )?;
2164    let reduced = round_enclosure(&enclosure_sub(&point, &turns)?, bits)?;
2165    let (_, remainder) = multiple.div_rem_euclid(&BigInt::try_from(4_u8)?)?;
2166    let phase = remainder.limbs_le().first().copied().unwrap_or(0) as usize & 3;
2167    let table = if sine {
2168        &SINE_QUARTER_TURNS
2169    } else {
2170        &COSINE_QUARTER_TURNS
2171    };
2172    let (kind, negate) = table[phase];
2173    let value = evaluate_bounded_series(kind, &reduced, bits)?;
2174    if negate {
2175        Ok(negate_enclosure(&value)?)
2176    } else {
2177        Ok(value)
2178    }
2179}
2180
2181fn dyadic_ratio(numerator: &Dyadic, denominator: &Dyadic) -> Result<(BigInt, BigInt), BigintError> {
2182    let mut numerator_integer = numerator.integer().try_clone()?;
2183    let mut denominator_integer = BigInt::from_sign_magnitude(
2184        Sign::Positive,
2185        denominator.integer().magnitude().try_clone()?,
2186    );
2187    if denominator.exponent() >= numerator.exponent() {
2188        numerator_integer = shift_left(
2189            &numerator_integer,
2190            denominator.exponent() - numerator.exponent(),
2191        )?;
2192    } else {
2193        denominator_integer = shift_left(
2194            &denominator_integer,
2195            numerator.exponent() - denominator.exponent(),
2196        )?;
2197    }
2198    Ok((numerator_integer, denominator_integer))
2199}
2200
2201fn integer_ratio_bound(
2202    numerator: &Dyadic,
2203    denominator: &Dyadic,
2204    half_shift: bool,
2205    upward: bool,
2206) -> Result<BigInt, BigintError> {
2207    let (mut numerator, mut denominator) = dyadic_ratio(numerator, denominator)?;
2208    if half_shift {
2209        numerator = shift_left(&numerator, 1)?.sub(&denominator)?;
2210        denominator = shift_left(&denominator, 1)?;
2211    }
2212    let (mut quotient, remainder) = numerator.div_rem_euclid(&denominator)?;
2213    if upward && !remainder.is_zero() {
2214        quotient = quotient.add(&BigInt::one()?)?;
2215    }
2216    Ok(quotient)
2217}
2218
2219fn trigonometric_extrema(
2220    sine: bool,
2221    argument: &DyadicEnclosure,
2222    bits: u32,
2223) -> Result<(bool, bool), SeriesFailure> {
2224    let magnitude_bits = bounded_limit(
2225        integer_part_bits(argument.lower()).max(integer_part_bits(argument.upper())),
2226    )?;
2227    let pi_bits = bits
2228        .checked_add(magnitude_bits)
2229        .and_then(|value| value.checked_add(16))
2230        .ok_or(BigintError::CapacityOverflow)?;
2231    let pi_bits = bounded_limit(u64::from(pi_bits))?;
2232    let pi = pi_enclosure(pi_bits)?;
2233    let lower_pi = if argument.lower().integer().sign() == Sign::Negative {
2234        pi.lower()
2235    } else {
2236        pi.upper()
2237    };
2238    let upper_pi = if argument.upper().integer().sign() == Sign::Negative {
2239        pi.upper()
2240    } else {
2241        pi.lower()
2242    };
2243    let lower_index = integer_ratio_bound(argument.lower(), lower_pi, sine, true)?;
2244    let upper_index = integer_ratio_bound(argument.upper(), upper_pi, sine, false)?;
2245    if upper_index < lower_index {
2246        return Ok((false, false));
2247    }
2248    if upper_index > lower_index {
2249        return Ok((true, true));
2250    }
2251    let odd = lower_index.magnitude().bit(0);
2252    Ok((!odd, odd))
2253}
2254
2255fn trigonometric_interval(
2256    sine: bool,
2257    argument: &DyadicEnclosure,
2258    bits: u32,
2259) -> Result<DyadicEnclosure, SeriesFailure> {
2260    let lower_point = trigonometric_point(sine, argument.lower(), bits)?;
2261    if argument.lower() == argument.upper() {
2262        return Ok(lower_point);
2263    }
2264    let upper_point = trigonometric_point(sine, argument.upper(), bits)?;
2265    let mut lower = if lower_point.lower() < upper_point.lower() {
2266        lower_point.lower().try_clone()?
2267    } else {
2268        upper_point.lower().try_clone()?
2269    };
2270    let mut upper = if lower_point.upper() > upper_point.upper() {
2271        lower_point.upper().try_clone()?
2272    } else {
2273        upper_point.upper().try_clone()?
2274    };
2275    let (contains_maximum, contains_minimum) = trigonometric_extrema(sine, argument, bits)?;
2276    if contains_maximum {
2277        upper = Dyadic::new(BigInt::one()?, 0);
2278    }
2279    if contains_minimum {
2280        lower = Dyadic::new(BigInt::one()?.negated()?, 0);
2281    }
2282    Ok(DyadicEnclosure::new(lower, upper)?)
2283}
2284
2285fn small_integer(value: &BigInt) -> Result<i64, BigintError> {
2286    let bound = i64::from(bounded_limit(unsigned_bound(value)?)?);
2287    Ok(if value.sign() == Sign::Negative {
2288        -bound
2289    } else {
2290        bound
2291    })
2292}
2293
2294fn exponential_point(x: &Dyadic, bits: u32) -> Result<DyadicEnclosure, SeriesFailure> {
2295    let magnitude_bits = bounded_limit(integer_part_bits(x))?;
2296    let coarse_ln2 = ln2_enclosure(magnitude_bits + 16)?;
2297    let multiple = small_integer(&nearest_integer_ratio(x, &coarse_ln2)?)?;
2298    let working =
2299        bits + u32::try_from(multiple.max(0)).map_err(|_| BigintError::CapacityOverflow)?;
2300    series_terms(SeriesKind::Exponential, working)?;
2301    let point = round_enclosure(&point_enclosure(x)?, working)?;
2302    let ln2 = ln2_enclosure(working + magnitude_bits + 16)?;
2303    let count = point_enclosure(&Dyadic::new(BigInt::try_from(multiple)?, 0))?;
2304    let reduced = round_enclosure(
2305        &enclosure_sub(&point, &enclosure_mul(&count, &ln2)?)?,
2306        working,
2307    )?;
2308    let series = evaluate_bounded_series(SeriesKind::Exponential, &reduced, working)?;
2309    Ok(round_enclosure(
2310        &DyadicEnclosure::new(
2311            scale_by_power_of_two(series.lower(), multiple)?,
2312            scale_by_power_of_two(series.upper(), multiple)?,
2313        )?,
2314        bits,
2315    )?)
2316}
2317
2318fn exponential_interval(
2319    argument: &DyadicEnclosure,
2320    bits: u32,
2321) -> Result<DyadicEnclosure, SeriesFailure> {
2322    let lower_point = exponential_point(argument.lower(), bits)?;
2323    if argument.lower() == argument.upper() {
2324        return Ok(lower_point);
2325    }
2326    let upper_point = exponential_point(argument.upper(), bits)?;
2327    Ok(DyadicEnclosure::new(
2328        lower_point.lower().try_clone()?,
2329        upper_point.upper().try_clone()?,
2330    )?)
2331}
2332
2333fn natural_log_point(value: &Dyadic, bits: u32) -> Result<DyadicEnclosure, SeriesFailure> {
2334    let floor_log2 = binary_magnitude(value) - 1;
2335    let leading = scale_by_power_of_two(value, -floor_log2)?;
2336    let three_halves = Dyadic::new(BigInt::try_from(3_u8)?, 1);
2337    let (binary_exponent, mantissa) = if leading >= three_halves {
2338        (floor_log2 + 1, scale_by_power_of_two(&leading, -1)?)
2339    } else {
2340        (floor_log2, leading)
2341    };
2342    let mantissa = round_enclosure(&point_enclosure(&mantissa)?, bits)?;
2343    let one = point_enclosure(&Dyadic::new(BigInt::one()?, 0))?;
2344    let minus_one = point_enclosure(&Dyadic::new(BigInt::one()?.negated()?, 0))?;
2345    let ratio = enclosure_div(
2346        &enclosure_add(&mantissa, &minus_one)?,
2347        &enclosure_add(&mantissa, &one)?,
2348        bits,
2349    )?;
2350    let series = evaluate_bounded_series(SeriesKind::DoubledArtanh, &ratio, bits)?;
2351    let exponent_bits = 64 - binary_exponent.unsigned_abs().leading_zeros();
2352    let ln2 = ln2_enclosure(bits + exponent_bits + 16)?;
2353    let count = point_enclosure(&Dyadic::new(BigInt::try_from(binary_exponent)?, 0))?;
2354    Ok(round_enclosure(
2355        &enclosure_add(&series, &enclosure_mul(&count, &ln2)?)?,
2356        bits,
2357    )?)
2358}
2359
2360fn natural_log_interval(base: &Enclosure, bits: u32) -> Result<DyadicEnclosure, SeriesFailure> {
2361    let lower = natural_log_point(base.lower(), bits)?;
2362    if base.lower() == base.upper() {
2363        return Ok(lower);
2364    }
2365    let upper = natural_log_point(base.upper(), bits)?;
2366    Ok(DyadicEnclosure::new(
2367        lower.lower().try_clone()?,
2368        upper.upper().try_clone()?,
2369    )?)
2370}
2371
2372fn function_enclosure(
2373    function: TranscendentalFunction,
2374    argument: &DyadicEnclosure,
2375    bits: u32,
2376) -> Result<DyadicEnclosure, SeriesFailure> {
2377    match function {
2378        TranscendentalFunction::Sine => trigonometric_interval(true, argument, bits),
2379        TranscendentalFunction::Cosine => trigonometric_interval(false, argument, bits),
2380        TranscendentalFunction::Exponential => exponential_interval(argument, bits),
2381    }
2382}
2383
2384fn candidate_matches_request(
2385    candidate: &TranscendentalEvaluationCandidate,
2386    owner: OwnerId,
2387    requirement: &ExactExpressionRequirement,
2388    source: NecoImplementationSource,
2389) -> Result<(), NecoFailure> {
2390    match candidate {
2391        TranscendentalEvaluationCandidate::ExactAlgebraic {
2392            owner: actual_owner,
2393            requirement: actual_requirement,
2394            source: actual_source,
2395            ..
2396        }
2397        | TranscendentalEvaluationCandidate::Enclosure {
2398            owner: actual_owner,
2399            requirement: actual_requirement,
2400            source: actual_source,
2401            ..
2402        }
2403        | TranscendentalEvaluationCandidate::Undetermined {
2404            owner: actual_owner,
2405            requirement: actual_requirement,
2406            source: actual_source,
2407            ..
2408        } => validate_lineage(
2409            owner,
2410            requirement,
2411            source,
2412            *actual_owner,
2413            actual_requirement,
2414            *actual_source,
2415        ),
2416    }
2417}
2418
2419fn validate_lineage(
2420    expected_owner: OwnerId,
2421    expected_requirement: &ExactExpressionRequirement,
2422    expected_source: NecoImplementationSource,
2423    actual_owner: OwnerId,
2424    actual_requirement: &ExactExpressionRequirement,
2425    actual_source: NecoImplementationSource,
2426) -> Result<(), NecoFailure> {
2427    let field = if expected_requirement.consumer_id() != actual_requirement.consumer_id() {
2428        ProvenanceMismatchField::Consumer
2429    } else if expected_owner != actual_owner {
2430        ProvenanceMismatchField::Owner
2431    } else if expected_requirement.expressions() != actual_requirement.expressions()
2432        || expected_requirement.decision() != actual_requirement.decision()
2433    {
2434        ProvenanceMismatchField::Expression
2435    } else if expected_requirement.precision() != actual_requirement.precision() {
2436        ProvenanceMismatchField::Precision
2437    } else if expected_source != actual_source {
2438        ProvenanceMismatchField::Source
2439    } else {
2440        return Ok(());
2441    };
2442    let actual_expression = actual_requirement
2443        .expressions()
2444        .first()
2445        .copied()
2446        .unwrap_or_else(|| ExprId::new(0));
2447    let location = FailureLocation::operation(FailureOperation::Assemble)
2448        .with_consumer(actual_requirement.consumer_id())
2449        .with_expr(actual_expression);
2450    Err(NecoFailure::ProvenanceMismatch {
2451        location,
2452        payload: Box::new(ProvenanceMismatchPayload::new(
2453            field,
2454            lineage_record(expected_owner, expected_requirement, expected_source),
2455            lineage_record(actual_owner, actual_requirement, actual_source),
2456        )),
2457    })
2458}
2459
2460fn lineage_record(
2461    owner: OwnerId,
2462    requirement: &ExactExpressionRequirement,
2463    source: NecoImplementationSource,
2464) -> ProvenanceRecord {
2465    ProvenanceRecord::new(
2466        Some(owner),
2467        Some(requirement.consumer_id()),
2468        requirement.expressions().first().copied(),
2469        Some(requirement.precision()),
2470        Some(source.revision_identity()),
2471        Some(source.public_api_identity()),
2472    )
2473}
2474
2475fn evaluation_expression_failure(
2476    operation: EvaluationOperation,
2477    owner: OwnerId,
2478    requirement: ExactExpressionRequirement,
2479    source: NecoImplementationSource,
2480    candidate: TranscendentalEvaluationCandidate,
2481    error: NecoFailure,
2482) -> CalculusFailure {
2483    EvaluationFailure::Lower {
2484        operation,
2485        owner,
2486        requirement,
2487        source,
2488        input: EvaluationInputSnapshot::Transcendental { candidate },
2489        witness: LowerWitness::new(operation),
2490        lower: LowerEvaluationFailure::Expression(error),
2491    }
2492    .into()
2493}
2494
2495fn clone_enclosure_value(enclosure: &Enclosure) -> Result<Enclosure, BigintError> {
2496    Ok(Enclosure::from_dyadic_enclosure(
2497        enclosure.as_dyadic_enclosure().try_clone()?,
2498    ))
2499}
2500
2501impl From<neco_bigint::BigintError> for CalculusFailure {
2502    fn from(error: neco_bigint::BigintError) -> Self {
2503        Self::Arithmetic(error)
2504    }
2505}
2506
2507impl From<AlgnumError> for CalculusFailure {
2508    fn from(error: AlgnumError) -> Self {
2509        Self::Algebra(error)
2510    }
2511}
2512
2513impl From<PolynomialFailure> for CalculusFailure {
2514    fn from(error: PolynomialFailure) -> Self {
2515        Self::Polynomial(error)
2516    }
2517}
2518
2519impl From<RationalFailure> for CalculusFailure {
2520    fn from(error: RationalFailure) -> Self {
2521        Self::Rational(error)
2522    }
2523}
2524
2525impl From<JetFailure> for CalculusFailure {
2526    fn from(error: JetFailure) -> Self {
2527        Self::Jet(error)
2528    }
2529}
2530
2531impl From<IntervalFailure> for CalculusFailure {
2532    fn from(error: IntervalFailure) -> Self {
2533        Self::Interval(error)
2534    }
2535}
2536
2537impl From<RootFailure> for CalculusFailure {
2538    fn from(error: RootFailure) -> Self {
2539        Self::Root(error)
2540    }
2541}
2542
2543impl From<EvaluationFailure> for CalculusFailure {
2544    fn from(error: EvaluationFailure) -> Self {
2545        Self::Evaluation(Box::new(error))
2546    }
2547}
2548
2549impl From<TranscendentalConnectorFailure> for CalculusFailure {
2550    fn from(error: TranscendentalConnectorFailure) -> Self {
2551        Self::Transcendental(error)
2552    }
2553}
2554
2555#[cfg(test)]
2556mod tests {
2557    use super::*;
2558
2559    const PI_400: &str = "3243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89452821e638d01377be5466cf34e90c6cc0ac";
2560    const LN_TWO_400: &str = "b17217f7d1cf79abc9e3b39803f2f6af40f343267298b62d8a0d175b8baafa2be7b876206debac98559552fb4afa1b10ed2e";
2561    const SINE_QUARTER_300: &str =
2562        "3f55dda9e62aed7513bd7b8e6a3d1635dd5676648d7db525898d7086af9330f03c7f285442a";
2563    const COSINE_QUARTER_300: &str =
2564        "f80aa4fbef750ba783d33cb95f94f8a41426dbe79edc4a023ef9ec13c944551c0795b84fee1";
2565    const EXPONENTIAL_QUARTER_300: &str =
2566        "148b5e3c3e81866767bc3b69baabe534ec43887164bbe2b0a993e8cf15a620bebaf42e6764e4";
2567    const DOUBLED_ARTANH_QUARTER_300: &str =
2568        "82c577d408a28d393b5e17c1021db53e8b382de73efea01c477373c22acc8611c66c126c4be";
2569
2570    fn hex(digits: &str, exponent: u32) -> Dyadic {
2571        let sixteen = BigInt::try_from(16_u8).unwrap();
2572        let mut value = BigInt::zero();
2573        for digit in digits.chars() {
2574            let digit = BigInt::try_from(digit.to_digit(16).unwrap()).unwrap();
2575            value = value.mul(&sixteen).unwrap().add(&digit).unwrap();
2576        }
2577        Dyadic::new(value, exponent)
2578    }
2579
2580    fn unit(exponent: u32) -> Dyadic {
2581        Dyadic::new(BigInt::one().unwrap(), exponent)
2582    }
2583
2584    fn assert_contains_reference(enclosure: &DyadicEnclosure, digits: &str, exponent: u32) {
2585        let floor = hex(digits, exponent);
2586        let ceiling = floor.add(&unit(exponent)).unwrap();
2587        assert!(enclosure.contains_dyadic(&floor));
2588        assert!(enclosure.contains_dyadic(&ceiling));
2589    }
2590
2591    #[test]
2592    fn pi_and_ln2_enclosures_contain_independent_references() {
2593        for bits in [64, 128, 256] {
2594            assert_contains_reference(&pi_enclosure(bits).unwrap(), PI_400, 400);
2595            assert_contains_reference(&ln2_enclosure(bits).unwrap(), LN_TWO_400, 400);
2596        }
2597    }
2598
2599    #[test]
2600    fn bounded_series_over_a_point_keeps_the_truncation_slack() {
2601        let quarter = point_enclosure(&Dyadic::new(BigInt::one().unwrap(), 2)).unwrap();
2602        let cases = [
2603            (SeriesKind::Sine, SINE_QUARTER_300),
2604            (SeriesKind::Cosine, COSINE_QUARTER_300),
2605            (SeriesKind::Exponential, EXPONENTIAL_QUARTER_300),
2606            (SeriesKind::DoubledArtanh, DOUBLED_ARTANH_QUARTER_300),
2607        ];
2608        for (kind, reference) in cases {
2609            for bits in [64, 200] {
2610                let result = evaluate_bounded_series(kind, &quarter, bits).unwrap();
2611                assert!(result.width().unwrap() >= unit(bits + 1));
2612                assert_contains_reference(&result, reference, 300);
2613            }
2614        }
2615        let zero = point_enclosure(&Dyadic::new(BigInt::zero(), 0)).unwrap();
2616        for (kind, exact) in [(SeriesKind::Exponential, 1_u8), (SeriesKind::Sine, 0_u8)] {
2617            for bits in [64, 200] {
2618                let result = evaluate_bounded_series(kind, &zero, bits).unwrap();
2619                assert!(result.width().unwrap() >= unit(bits + 1));
2620                let exact = Dyadic::new(BigInt::try_from(exact).unwrap(), 0);
2621                assert!(result.contains_dyadic(&exact));
2622            }
2623        }
2624    }
2625
2626    #[test]
2627    fn bounded_series_rejects_out_of_range_domains_and_excess_precision() {
2628        let two = point_enclosure(&Dyadic::new(BigInt::try_from(2_u8).unwrap(), 0)).unwrap();
2629        assert!(matches!(
2630            evaluate_bounded_series(SeriesKind::Sine, &two, 64),
2631            Err(SeriesFailure::ReductionRange)
2632        ));
2633        let half = point_enclosure(&Dyadic::new(BigInt::one().unwrap(), 1)).unwrap();
2634        assert!(matches!(
2635            evaluate_bounded_series(SeriesKind::Exponential, &half, 2000),
2636            Err(SeriesFailure::PrecisionLimit {
2637                requested: 2000,
2638                maximum: 1677
2639            })
2640        ));
2641    }
2642}