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 pub fn undetermined_achieved(&self) -> Option<&Enclosure> {
470 match &self.value {
471 TranscendentalEvaluationValue::Undetermined { achieved, .. } => Some(achieved),
472 _ => None,
473 }
474 }
475
476 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
532pub 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
1515pub 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
1565pub 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(÷_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("ient.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}