Skip to main content

neco_root/
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
7use core::cmp::Ordering;
8
9use neco_algnum::{AlgnumError, RealAlgebraic};
10use neco_bigint::{
11    BigInt, BigUint, BigintError, Dyadic, DyadicEnclosure, RawRational, ReducedRational, Sign,
12};
13use neco_formsum::{FormSumErrorKind, RawFormSum, RawTerm};
14use neco_monomial::RawMonomial;
15use neco_polynomial::{DerivativeOrder, Enclosure, IntervalFailure, Polynomial, PolynomialFailure};
16
17pub const MAX_CANDIDATE_POINTS: usize = 4_096;
18pub const MAX_DERIVATIVE_ORDER: usize = 64;
19pub const MAX_ROOT_REFINEMENT_ITERATIONS: usize = 19;
20pub const MAX_ROOT_REFINEMENT_PRECISION_BITS: u32 = 256;
21
22#[derive(Debug, Eq, PartialEq)]
23pub struct RootBracket {
24    polynomial: Polynomial,
25    enclosure: Enclosure,
26    evidence: RootEvidence,
27}
28
29impl RootBracket {
30    pub fn sign_change(polynomial: Polynomial, enclosure: Enclosure) -> Result<Self, RootFailure> {
31        let lower = sign_at(&polynomial, enclosure.lower())?;
32        let upper = sign_at(&polynomial, enclosure.upper())?;
33        if !opposite_nonzero(lower, upper) {
34            return Err(RootFailure::NoSignChange);
35        }
36        Ok(Self {
37            polynomial,
38            enclosure,
39            evidence: RootEvidence::SignChange { lower, upper },
40        })
41    }
42
43    pub fn even_multiplicity_touch(
44        polynomial: Polynomial,
45        enclosure: Enclosure,
46        point: Dyadic,
47        max_order: DerivativeOrder,
48    ) -> Result<Self, RootFailure> {
49        if !enclosure.contains(&point) {
50            return Err(RootFailure::PointOutsideEnclosure);
51        }
52        let multiplicity = classify_multiplicity(&polynomial, &point, max_order)?;
53        match multiplicity {
54            RootMultiplicity::Multiple(order) if order.get() >= 2 && order.get() % 2 == 0 => {
55                Ok(Self {
56                    polynomial,
57                    enclosure,
58                    evidence: RootEvidence::EvenMultiplicityTouch {
59                        point,
60                        multiplicity,
61                    },
62                })
63            }
64            _ => Err(RootFailure::NoEvenMultiplicityTouch),
65        }
66    }
67
68    pub fn polynomial(&self) -> &Polynomial {
69        &self.polynomial
70    }
71
72    pub fn enclosure(&self) -> &Enclosure {
73        &self.enclosure
74    }
75
76    pub fn evidence(&self) -> &RootEvidence {
77        &self.evidence
78    }
79
80    pub fn refine_bisection(&self, iterations: usize) -> Result<RootIsolation, RootFailure> {
81        validate_resource_limit(
82            RootResource::RefinementIterations,
83            iterations,
84            MAX_ROOT_REFINEMENT_ITERATIONS,
85        )?;
86        match &self.evidence {
87            RootEvidence::SignChange { lower, .. } => {
88                refine_sign_change(self, iterations, *lower, RootRefinementMethod::Bisection, 0)
89            }
90            RootEvidence::EvenMultiplicityTouch { point, .. } => {
91                exact_root_isolation(self, point, RootRefinementMethod::Bisection)
92            }
93        }
94    }
95
96    pub fn refine_newton_bisection(
97        &self,
98        iterations: usize,
99        precision_bits: u32,
100    ) -> Result<RootIsolation, RootFailure> {
101        validate_resource_limit(
102            RootResource::RefinementIterations,
103            iterations,
104            MAX_ROOT_REFINEMENT_ITERATIONS,
105        )?;
106        validate_resource_limit(
107            RootResource::RefinementPrecisionBits,
108            precision_bits as usize,
109            MAX_ROOT_REFINEMENT_PRECISION_BITS as usize,
110        )?;
111        match &self.evidence {
112            RootEvidence::SignChange { lower, .. } => refine_sign_change(
113                self,
114                iterations,
115                *lower,
116                RootRefinementMethod::NewtonBisection,
117                precision_bits,
118            ),
119            RootEvidence::EvenMultiplicityTouch { point, .. } => {
120                exact_root_isolation(self, point, RootRefinementMethod::NewtonBisection)
121            }
122        }
123    }
124}
125
126#[derive(Debug, Eq, PartialEq)]
127pub enum RootEvidence {
128    SignChange {
129        lower: Sign,
130        upper: Sign,
131    },
132    EvenMultiplicityTouch {
133        point: Dyadic,
134        multiplicity: RootMultiplicity,
135    },
136}
137
138#[derive(Clone, Copy, Debug, Eq, PartialEq)]
139pub enum RootMultiplicity {
140    Simple,
141    Multiple(DerivativeOrder),
142}
143
144#[derive(Debug, Eq, PartialEq)]
145pub struct MembershipJudgmentRequest {
146    target_polynomial: Polynomial,
147    target_enclosure: Enclosure,
148    candidate_points: alloc::vec::Vec<Dyadic>,
149    max_order: DerivativeOrder,
150    zero_exclusion_precision_bits: u32,
151}
152
153impl MembershipJudgmentRequest {
154    pub fn new(
155        target_polynomial: Polynomial,
156        target_enclosure: Enclosure,
157        candidate_points: alloc::vec::Vec<Dyadic>,
158        max_order: DerivativeOrder,
159        zero_exclusion_precision_bits: u32,
160    ) -> Result<Self, RootFailure> {
161        validate_resource_limit(
162            RootResource::CandidatePoints,
163            candidate_points.len(),
164            MAX_CANDIDATE_POINTS,
165        )?;
166        validate_resource_limit(
167            RootResource::DerivativeOrder,
168            max_order.get(),
169            MAX_DERIVATIVE_ORDER,
170        )?;
171        validate_resource_limit(
172            RootResource::RegionSignPrecisionBits,
173            zero_exclusion_precision_bits as usize,
174            MAX_ROOT_REFINEMENT_PRECISION_BITS as usize,
175        )?;
176        Ok(Self {
177            target_polynomial,
178            target_enclosure,
179            candidate_points,
180            max_order,
181            zero_exclusion_precision_bits,
182        })
183    }
184
185    pub fn target_polynomial(&self) -> &Polynomial {
186        &self.target_polynomial
187    }
188
189    pub fn target_enclosure(&self) -> &Enclosure {
190        &self.target_enclosure
191    }
192
193    pub fn candidate_points(&self) -> &[Dyadic] {
194        &self.candidate_points
195    }
196
197    pub fn max_order(&self) -> DerivativeOrder {
198        self.max_order
199    }
200
201    pub fn zero_exclusion_precision_bits(&self) -> u32 {
202        self.zero_exclusion_precision_bits
203    }
204}
205
206#[derive(Clone, Copy, Debug, Eq, PartialEq)]
207pub enum RegionSign {
208    ConstantPositive,
209    ConstantNegative,
210    ConstantZero,
211    SignVaries,
212    ContainsZero,
213    Undetermined,
214}
215
216#[derive(Clone, Debug, Eq, PartialEq)]
217pub struct RegionSignJudgment {
218    sign: RegionSign,
219}
220
221impl RegionSignJudgment {
222    fn new(sign: RegionSign) -> Self {
223        Self { sign }
224    }
225
226    pub fn sign(&self) -> RegionSign {
227        self.sign
228    }
229}
230
231#[derive(Clone, Debug, Eq, PartialEq)]
232pub struct MembershipTransitionReport {
233    loci: alloc::vec::Vec<MembershipLocus>,
234}
235impl MembershipTransitionReport {
236    fn new(loci: alloc::vec::Vec<MembershipLocus>) -> Self {
237        Self { loci }
238    }
239
240    pub fn loci(&self) -> &[MembershipLocus] {
241        &self.loci
242    }
243}
244
245#[derive(Clone, Debug, Eq, PartialEq)]
246pub struct MembershipLocus {
247    point_index: usize,
248    kind: MembershipLocusKind,
249    multiplicity: RootMultiplicity,
250}
251
252impl MembershipLocus {
253    fn new(point_index: usize, kind: MembershipLocusKind, multiplicity: RootMultiplicity) -> Self {
254        Self {
255            point_index,
256            kind,
257            multiplicity,
258        }
259    }
260
261    pub fn point_index(&self) -> usize {
262        self.point_index
263    }
264
265    pub fn kind(&self) -> MembershipLocusKind {
266        self.kind
267    }
268
269    pub fn multiplicity(&self) -> RootMultiplicity {
270        self.multiplicity
271    }
272}
273
274#[derive(Clone, Copy, Debug, Eq, PartialEq)]
275pub enum MembershipLocusKind {
276    Transition,
277    SingularContact,
278}
279
280fn classify_local_multiplicity(
281    request: &MembershipJudgmentRequest,
282) -> Result<alloc::vec::Vec<(usize, RootMultiplicity)>, RootFailure> {
283    for point in request.candidate_points() {
284        if !request.target_enclosure().contains(point) {
285            return Err(RootFailure::PointOutsideEnclosure);
286        }
287    }
288
289    let mut roots = alloc::vec::Vec::new();
290    for (index, point) in request.candidate_points().iter().enumerate() {
291        let algebraic_point = dyadic_to_algebraic(point)?;
292        if request
293            .target_polynomial()
294            .evaluate(&algebraic_point)?
295            .is_zero()
296        {
297            let multiplicity =
298                classify_multiplicity(request.target_polynomial(), point, request.max_order())?;
299            roots.push((index, multiplicity));
300        }
301    }
302    Ok(roots)
303}
304
305pub fn classify_region_sign(
306    request: &MembershipJudgmentRequest,
307) -> Result<RegionSignJudgment, RootFailure> {
308    if request.target_polynomial().degree() == 0 {
309        let coefficient = request
310            .target_polynomial()
311            .coefficients()
312            .first()
313            .ok_or(PolynomialFailure::EmptyCoefficients)?;
314        return match coefficient.sign()? {
315            Sign::Positive => Ok(RegionSignJudgment::new(RegionSign::ConstantPositive)),
316            Sign::Negative => Ok(RegionSignJudgment::new(RegionSign::ConstantNegative)),
317            Sign::Zero => Ok(RegionSignJudgment::new(RegionSign::ConstantZero)),
318        };
319    }
320
321    let roots = classify_local_multiplicity(request)?;
322    if !roots.is_empty() {
323        if roots.iter().any(|(point_index, multiplicity)| {
324            let point = &request.candidate_points()[*point_index];
325            let is_interior = request.target_enclosure().lower() < point
326                && point < request.target_enclosure().upper();
327            let has_odd_multiplicity = match multiplicity {
328                RootMultiplicity::Simple => true,
329                RootMultiplicity::Multiple(order) => order.get() % 2 == 1,
330            };
331            is_interior && has_odd_multiplicity
332        }) {
333            return Ok(RegionSignJudgment::new(RegionSign::SignVaries));
334        }
335        return Ok(RegionSignJudgment::new(RegionSign::ContainsZero));
336    }
337
338    let range = request.target_polynomial().evaluate_enclosure(
339        request.target_enclosure(),
340        request.zero_exclusion_precision_bits(),
341    )?;
342    if range.lower().integer().sign() == Sign::Positive {
343        return Ok(RegionSignJudgment::new(RegionSign::ConstantPositive));
344    }
345    if range.upper().integer().sign() == Sign::Negative {
346        return Ok(RegionSignJudgment::new(RegionSign::ConstantNegative));
347    }
348
349    let lower_sign = sign_at(
350        request.target_polynomial(),
351        request.target_enclosure().lower(),
352    )?;
353    let upper_sign = sign_at(
354        request.target_polynomial(),
355        request.target_enclosure().upper(),
356    )?;
357
358    match (lower_sign, upper_sign) {
359        (Sign::Positive, Sign::Negative) | (Sign::Negative, Sign::Positive) => {
360            Ok(RegionSignJudgment::new(RegionSign::SignVaries))
361        }
362        _ => Ok(RegionSignJudgment::new(RegionSign::Undetermined)),
363    }
364}
365
366pub fn locate_membership_transitions(
367    request: &MembershipJudgmentRequest,
368) -> Result<MembershipTransitionReport, RootFailure> {
369    let roots = classify_local_multiplicity(request)?;
370    let mut loci = alloc::vec::Vec::new();
371
372    for (point_index, multiplicity) in roots {
373        let kind = match multiplicity {
374            RootMultiplicity::Simple => MembershipLocusKind::Transition,
375            RootMultiplicity::Multiple(order) => {
376                if order.get() % 2 == 0 {
377                    MembershipLocusKind::SingularContact
378                } else {
379                    MembershipLocusKind::Transition
380                }
381            }
382        };
383        loci.push(MembershipLocus::new(point_index, kind, multiplicity));
384    }
385
386    Ok(MembershipTransitionReport::new(loci))
387}
388
389#[derive(Debug, Eq, PartialEq)]
390pub struct RootIsolation {
391    enclosure: Enclosure,
392    witness: ConvergenceWitness,
393}
394
395impl RootIsolation {
396    fn new(enclosure: Enclosure, witness: ConvergenceWitness) -> Self {
397        Self { enclosure, witness }
398    }
399
400    pub fn enclosure(&self) -> &Enclosure {
401        &self.enclosure
402    }
403
404    pub fn witness(&self) -> &ConvergenceWitness {
405        &self.witness
406    }
407}
408
409#[derive(Debug, Eq, PartialEq)]
410pub struct ConvergenceWitness {
411    method: RootRefinementMethod,
412    status: ConvergenceStatus,
413    iterations: usize,
414    newton_steps: usize,
415    newton_fallbacks: usize,
416    initial: Enclosure,
417    final_enclosure: Enclosure,
418}
419
420impl ConvergenceWitness {
421    fn new(
422        method: RootRefinementMethod,
423        status: ConvergenceStatus,
424        iterations: usize,
425        newton_steps: usize,
426        newton_fallbacks: usize,
427        initial: Enclosure,
428        final_enclosure: Enclosure,
429    ) -> Self {
430        Self {
431            method,
432            status,
433            iterations,
434            newton_steps,
435            newton_fallbacks,
436            initial,
437            final_enclosure,
438        }
439    }
440
441    pub fn method(&self) -> RootRefinementMethod {
442        self.method
443    }
444
445    pub fn status(&self) -> ConvergenceStatus {
446        self.status
447    }
448
449    pub fn iterations(&self) -> usize {
450        self.iterations
451    }
452
453    pub fn newton_steps(&self) -> usize {
454        self.newton_steps
455    }
456
457    pub fn newton_fallback_count(&self) -> usize {
458        self.newton_fallbacks
459    }
460
461    pub fn newton_fallback_reason(&self) -> Option<NewtonFallbackReason> {
462        (self.newton_fallbacks > 0).then_some(NewtonFallbackReason::DerivativeEnclosureContainsZero)
463    }
464
465    pub fn initial(&self) -> &Enclosure {
466        &self.initial
467    }
468
469    pub fn final_enclosure(&self) -> &Enclosure {
470        &self.final_enclosure
471    }
472}
473
474#[derive(Clone, Copy, Debug, Eq, PartialEq)]
475pub enum RootRefinementMethod {
476    Bisection,
477    NewtonBisection,
478}
479
480#[derive(Clone, Copy, Debug, Eq, PartialEq)]
481pub enum NewtonFallbackReason {
482    DerivativeEnclosureContainsZero,
483}
484
485#[derive(Clone, Copy, Debug, Eq, PartialEq)]
486pub enum ConvergenceStatus {
487    ExactDyadicRoot,
488    Refined,
489    IterationLimit,
490}
491
492#[derive(Debug, Eq, PartialEq)]
493pub enum RootFailure {
494    Polynomial(PolynomialFailure),
495    Interval(IntervalFailure),
496    Algebra(AlgnumError),
497    Arithmetic(BigintError),
498    FormSum(FormSumErrorKind),
499    NoSignChange,
500    NoRootAtPoint,
501    NoEvenMultiplicityTouch,
502    PointOutsideEnclosure,
503    MultiplicityUndetermined,
504    NewtonDerivativeContainsZero,
505    ResourceLimit {
506        resource: RootResource,
507        requested: usize,
508        maximum: usize,
509    },
510}
511
512#[derive(Clone, Copy, Debug, Eq, PartialEq)]
513pub enum RootResource {
514    CandidatePoints,
515    DerivativeOrder,
516    RefinementIterations,
517    RefinementPrecisionBits,
518    RegionSignPrecisionBits,
519}
520
521pub fn classify_multiplicity(
522    polynomial: &Polynomial,
523    point: &Dyadic,
524    max_order: DerivativeOrder,
525) -> Result<RootMultiplicity, RootFailure> {
526    validate_resource_limit(
527        RootResource::DerivativeOrder,
528        max_order.get(),
529        MAX_DERIVATIVE_ORDER,
530    )?;
531    let algebraic_point = dyadic_to_algebraic(point)?;
532    if polynomial.evaluate(&algebraic_point)?.sign()? != Sign::Zero {
533        return Err(RootFailure::NoRootAtPoint);
534    }
535    for order in 1..=max_order.get() {
536        let derivative = polynomial.derivative(DerivativeOrder::new(order))?;
537        if derivative.evaluate(&algebraic_point)?.sign()? != Sign::Zero {
538            return if order == 1 {
539                Ok(RootMultiplicity::Simple)
540            } else {
541                Ok(RootMultiplicity::Multiple(DerivativeOrder::new(order)))
542            };
543        }
544    }
545    Err(RootFailure::MultiplicityUndetermined)
546}
547
548impl From<PolynomialFailure> for RootFailure {
549    fn from(error: PolynomialFailure) -> Self {
550        Self::Polynomial(error)
551    }
552}
553
554impl From<IntervalFailure> for RootFailure {
555    fn from(error: IntervalFailure) -> Self {
556        Self::Interval(error)
557    }
558}
559
560impl From<AlgnumError> for RootFailure {
561    fn from(error: AlgnumError) -> Self {
562        Self::Algebra(error)
563    }
564}
565
566impl From<BigintError> for RootFailure {
567    fn from(error: BigintError) -> Self {
568        Self::Arithmetic(error)
569    }
570}
571
572impl From<FormSumErrorKind> for RootFailure {
573    fn from(error: FormSumErrorKind) -> Self {
574        Self::FormSum(error)
575    }
576}
577
578fn refine_sign_change(
579    bracket: &RootBracket,
580    iterations: usize,
581    initial_lower_sign: Sign,
582    method: RootRefinementMethod,
583    precision_bits: u32,
584) -> Result<RootIsolation, RootFailure> {
585    let initial = clone_enclosure(bracket.enclosure())?;
586    let mut lower = bracket.enclosure().lower().try_clone()?;
587    let mut upper = bracket.enclosure().upper().try_clone()?;
588    let mut lower_sign = initial_lower_sign;
589    let mut status = ConvergenceStatus::IterationLimit;
590    let mut used_iterations = 0;
591    let mut newton_steps = 0;
592    let mut newton_fallbacks = 0;
593
594    for _ in 0..iterations {
595        used_iterations += 1;
596        let candidate = if method == RootRefinementMethod::NewtonBisection {
597            match newton_candidate(&bracket.polynomial, &lower, &upper, precision_bits) {
598                Ok(candidate) if lower < candidate && candidate < upper => {
599                    newton_steps += 1;
600                    candidate
601                }
602                Ok(_) => lower.midpoint(&upper)?,
603                Err(RootFailure::NewtonDerivativeContainsZero) => {
604                    newton_fallbacks += 1;
605                    lower.midpoint(&upper)?
606                }
607                Err(error) => return Err(error),
608            }
609        } else {
610            lower.midpoint(&upper)?
611        };
612        let sign = sign_at(&bracket.polynomial, &candidate)?;
613        if sign == Sign::Zero {
614            lower = candidate.try_clone()?;
615            upper = candidate;
616            status = ConvergenceStatus::ExactDyadicRoot;
617            break;
618        }
619        if sign == lower_sign {
620            lower = candidate;
621            lower_sign = sign;
622        } else {
623            upper = candidate;
624        }
625        status = ConvergenceStatus::Refined;
626    }
627
628    let final_enclosure = Enclosure::new(lower, upper)?;
629    Ok(RootIsolation::new(
630        clone_enclosure(&final_enclosure)?,
631        ConvergenceWitness::new(
632            method,
633            status,
634            used_iterations,
635            newton_steps,
636            newton_fallbacks,
637            initial,
638            final_enclosure,
639        ),
640    ))
641}
642
643fn exact_root_isolation(
644    bracket: &RootBracket,
645    point: &Dyadic,
646    method: RootRefinementMethod,
647) -> Result<RootIsolation, RootFailure> {
648    let exact = Enclosure::new(point.try_clone()?, point.try_clone()?)?;
649    Ok(RootIsolation::new(
650        clone_enclosure(&exact)?,
651        ConvergenceWitness::new(
652            method,
653            ConvergenceStatus::ExactDyadicRoot,
654            0,
655            0,
656            0,
657            clone_enclosure(&bracket.enclosure)?,
658            exact,
659        ),
660    ))
661}
662
663fn newton_candidate(
664    polynomial: &Polynomial,
665    lower: &Dyadic,
666    upper: &Dyadic,
667    precision_bits: u32,
668) -> Result<Dyadic, RootFailure> {
669    let midpoint = lower.midpoint(upper)?;
670    let midpoint_value = dyadic_to_algebraic(&midpoint)?;
671    let derivative = polynomial.derivative(DerivativeOrder::new(1))?;
672    let value_enclosure = polynomial
673        .evaluate(&midpoint_value)?
674        .enclose(precision_bits)?
675        .enclosure()
676        .try_clone()?;
677    let derivative_enclosure = derivative
678        .evaluate(&midpoint_value)?
679        .enclose(precision_bits)?
680        .enclosure()
681        .try_clone()?;
682    if contains_zero(&derivative_enclosure) {
683        return Err(RootFailure::NewtonDerivativeContainsZero);
684    }
685    let quotient = enclosure_div(&value_enclosure, &derivative_enclosure, precision_bits)?;
686    midpoint.sub(&quotient.midpoint()?).map_err(Into::into)
687}
688
689fn sign_at(polynomial: &Polynomial, point: &Dyadic) -> Result<Sign, RootFailure> {
690    Ok(polynomial.evaluate(&dyadic_to_algebraic(point)?)?.sign()?)
691}
692
693fn dyadic_to_algebraic(value: &Dyadic) -> Result<RealAlgebraic, RootFailure> {
694    if value.is_zero() {
695        return Ok(RealAlgebraic::from_form_sum(&neco_formsum::FormSum::zero())?);
696    }
697    let denominator = BigUint::one()?.shl_bits(value.exponent() as usize)?;
698    let raw = RawFormSum::new(alloc::vec![RawTerm::new(
699        RawRational::new(value.integer().try_clone()?, denominator),
700        RawMonomial::positive(alloc::vec![]),
701    )]);
702    let sum = raw
703        .normalize()
704        .map_err(|errors| RootFailure::FormSum(errors.into_parts().0))?;
705    Ok(RealAlgebraic::from_form_sum(&sum)?)
706}
707
708fn clone_enclosure(enclosure: &Enclosure) -> Result<Enclosure, RootFailure> {
709    Ok(Enclosure::from_dyadic_enclosure(
710        enclosure.as_dyadic_enclosure().try_clone()?,
711    ))
712}
713
714fn contains_zero(enclosure: &DyadicEnclosure) -> bool {
715    enclosure.contains_dyadic(&Dyadic::new(BigInt::zero(), 0))
716}
717
718fn enclosure_div(
719    numerator: &DyadicEnclosure,
720    denominator: &DyadicEnclosure,
721    precision_bits: u32,
722) -> Result<DyadicEnclosure, RootFailure> {
723    let candidates = [
724        dyadic_to_rational(numerator.lower())?.div(&dyadic_to_rational(denominator.lower())?)?,
725        dyadic_to_rational(numerator.lower())?.div(&dyadic_to_rational(denominator.upper())?)?,
726        dyadic_to_rational(numerator.upper())?.div(&dyadic_to_rational(denominator.lower())?)?,
727        dyadic_to_rational(numerator.upper())?.div(&dyadic_to_rational(denominator.upper())?)?,
728    ];
729    let mut lower = candidates[0].try_clone()?;
730    let mut upper = candidates[0].try_clone()?;
731    for candidate in candidates.iter().skip(1) {
732        if candidate.cmp(&lower) == Ordering::Less {
733            lower = candidate.try_clone()?;
734        }
735        if candidate.cmp(&upper) == Ordering::Greater {
736            upper = candidate.try_clone()?;
737        }
738    }
739    Ok(DyadicEnclosure::new(
740        lower.dyadic_floor(precision_bits)?,
741        upper.dyadic_ceil(precision_bits)?,
742    )?)
743}
744
745fn dyadic_to_rational(value: &Dyadic) -> Result<ReducedRational, BigintError> {
746    let denominator = BigUint::one()?.shl_bits(value.exponent() as usize)?;
747    RawRational::new(value.integer().try_clone()?, denominator)
748        .reduce()
749        .map(|reduction| reduction.into_reduced())
750}
751
752fn opposite_nonzero(left: Sign, right: Sign) -> bool {
753    matches!(
754        (left, right),
755        (Sign::Negative, Sign::Positive) | (Sign::Positive, Sign::Negative)
756    )
757}
758
759fn validate_resource_limit(
760    resource: RootResource,
761    requested: usize,
762    maximum: usize,
763) -> Result<(), RootFailure> {
764    if requested > maximum {
765        return Err(RootFailure::ResourceLimit {
766            resource,
767            requested,
768            maximum,
769        });
770    }
771    Ok(())
772}