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("ient.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}