Skip to main content

neco_polynomial/
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 alloc::vec::Vec;
8use core::cmp::Ordering;
9
10use neco_algnum::{AlgnumError, RealAlgebraic};
11use neco_bigint::{BigInt, BigintError, Dyadic, DyadicEnclosure};
12
13pub const MAX_COEFFICIENTS: usize = 256;
14pub const MAX_DERIVATIVE_ORDER: usize = 64;
15pub const MAX_PRECISION_BITS: u32 = 256;
16
17#[derive(Debug, Eq, PartialEq)]
18pub struct Polynomial {
19    coefficients: Vec<RealAlgebraic>,
20}
21
22impl Polynomial {
23    pub fn from_coefficients(
24        mut coefficients: Vec<RealAlgebraic>,
25    ) -> Result<Self, PolynomialFailure> {
26        if coefficients.is_empty() {
27            return Err(PolynomialFailure::EmptyCoefficients);
28        }
29        if coefficients.len() > MAX_COEFFICIENTS {
30            return Err(ResourceFailure::CoefficientLimitExceeded {
31                requested: coefficients.len(),
32                maximum: MAX_COEFFICIENTS,
33            }
34            .into());
35        }
36        while coefficients.len() > 1 && coefficients.last().is_some_and(RealAlgebraic::is_zero) {
37            coefficients.pop();
38        }
39        Ok(Self { coefficients })
40    }
41
42    pub fn zero() -> Result<Self, PolynomialFailure> {
43        Self::constant(algebraic_integer(0)?)
44    }
45
46    pub fn constant(value: RealAlgebraic) -> Result<Self, PolynomialFailure> {
47        Self::from_coefficients(alloc::vec![value])
48    }
49
50    pub fn degree(&self) -> usize {
51        self.coefficients.len() - 1
52    }
53
54    pub fn coefficients(&self) -> &[RealAlgebraic] {
55        &self.coefficients
56    }
57
58    pub fn try_clone(&self) -> Result<Self, PolynomialFailure> {
59        let mut coefficients = Vec::new();
60        for coefficient in &self.coefficients {
61            coefficients.push(coefficient.try_clone()?);
62        }
63        Ok(Self { coefficients })
64    }
65
66    pub fn evaluate(&self, point: &RealAlgebraic) -> Result<RealAlgebraic, PolynomialFailure> {
67        let mut coefficients = self.coefficients.iter().rev();
68        let first = coefficients
69            .next()
70            .ok_or(PolynomialFailure::EmptyCoefficients)?
71            .try_clone()?;
72        let mut value = first;
73        for coefficient in coefficients {
74            value = value.mul(point)?.add(coefficient)?;
75        }
76        Ok(value)
77    }
78
79    pub fn derivative(&self, order: DerivativeOrder) -> Result<Self, PolynomialFailure> {
80        validate_derivative_order(order)?;
81        let mut result = self.try_clone()?;
82        for _ in 0..order.get() {
83            result = result.derivative_once()?;
84        }
85        Ok(result)
86    }
87
88    pub fn evaluate_enclosure(
89        &self,
90        domain: &Enclosure,
91        precision_bits: u32,
92    ) -> Result<Enclosure, PolynomialFailure> {
93        validate_precision(precision_bits)?;
94        let mut coefficients = self.coefficients.iter().rev();
95        let first = coefficients
96            .next()
97            .ok_or(PolynomialFailure::EmptyCoefficients)?
98            .enclose(precision_bits)?
99            .enclosure()
100            .try_clone()?;
101        let mut value = first;
102        for coefficient in coefficients {
103            let coefficient = coefficient
104                .enclose(precision_bits)?
105                .enclosure()
106                .try_clone()?;
107            value = enclosure_add(
108                &enclosure_mul(&value, domain.as_dyadic_enclosure())?,
109                &coefficient,
110            )?;
111        }
112        Ok(Enclosure::from_dyadic_enclosure(value))
113    }
114
115    fn derivative_once(&self) -> Result<Self, PolynomialFailure> {
116        if self.coefficients.len() <= 1 {
117            return Self::zero();
118        }
119        let mut coefficients = Vec::new();
120        for (degree, coefficient) in self.coefficients.iter().enumerate().skip(1) {
121            coefficients.push(coefficient.mul(&algebraic_integer(degree)?)?);
122        }
123        Self::from_coefficients(coefficients)
124    }
125}
126
127#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
128pub struct DerivativeOrder(usize);
129
130impl DerivativeOrder {
131    pub const fn new(value: usize) -> Self {
132        Self(value)
133    }
134
135    pub const fn get(self) -> usize {
136        self.0
137    }
138}
139
140#[derive(Debug, Eq, PartialEq)]
141pub struct Enclosure {
142    value: DyadicEnclosure,
143}
144
145impl Enclosure {
146    pub fn new(lower: Dyadic, upper: Dyadic) -> Result<Self, IntervalFailure> {
147        Ok(Self {
148            value: DyadicEnclosure::new(lower, upper)?,
149        })
150    }
151
152    pub fn from_dyadic_enclosure(value: DyadicEnclosure) -> Self {
153        Self { value }
154    }
155
156    pub fn as_dyadic_enclosure(&self) -> &DyadicEnclosure {
157        &self.value
158    }
159
160    pub fn lower(&self) -> &Dyadic {
161        self.value.lower()
162    }
163
164    pub fn upper(&self) -> &Dyadic {
165        self.value.upper()
166    }
167
168    pub fn width(&self) -> Result<Dyadic, IntervalFailure> {
169        Ok(self.value.width()?)
170    }
171
172    pub fn midpoint(&self) -> Result<Dyadic, IntervalFailure> {
173        Ok(self.value.midpoint()?)
174    }
175
176    pub fn contains(&self, value: &Dyadic) -> bool {
177        self.value.contains_dyadic(value)
178    }
179
180    pub fn contains_zero(&self) -> bool {
181        self.contains(&Dyadic::new(BigInt::zero(), 0))
182    }
183}
184
185#[derive(Debug, Eq, PartialEq)]
186pub enum PolynomialFailure {
187    EmptyCoefficients,
188    Algebra(AlgnumError),
189    Arithmetic(BigintError),
190    Interval(IntervalFailure),
191    Resource(ResourceFailure),
192}
193
194#[derive(Clone, Copy, Debug, Eq, PartialEq)]
195pub enum ResourceFailure {
196    CoefficientLimitExceeded { requested: usize, maximum: usize },
197    DerivativeOrderLimitExceeded { requested: usize, maximum: usize },
198    PrecisionLimitExceeded { requested: u32, maximum: u32 },
199}
200
201#[derive(Debug, Eq, PartialEq)]
202pub enum IntervalFailure {
203    Arithmetic(BigintError),
204}
205
206impl From<AlgnumError> for PolynomialFailure {
207    fn from(error: AlgnumError) -> Self {
208        Self::Algebra(error)
209    }
210}
211
212impl From<BigintError> for PolynomialFailure {
213    fn from(error: BigintError) -> Self {
214        Self::Arithmetic(error)
215    }
216}
217
218impl From<IntervalFailure> for PolynomialFailure {
219    fn from(error: IntervalFailure) -> Self {
220        Self::Interval(error)
221    }
222}
223
224impl From<ResourceFailure> for PolynomialFailure {
225    fn from(error: ResourceFailure) -> Self {
226        Self::Resource(error)
227    }
228}
229
230impl From<BigintError> for IntervalFailure {
231    fn from(error: BigintError) -> Self {
232        Self::Arithmetic(error)
233    }
234}
235
236fn algebraic_integer(value: usize) -> Result<RealAlgebraic, PolynomialFailure> {
237    Ok(RealAlgebraic::from_integer(BigInt::try_from(value)?)?)
238}
239
240fn validate_derivative_order(order: DerivativeOrder) -> Result<(), PolynomialFailure> {
241    if order.get() > MAX_DERIVATIVE_ORDER {
242        return Err(ResourceFailure::DerivativeOrderLimitExceeded {
243            requested: order.get(),
244            maximum: MAX_DERIVATIVE_ORDER,
245        }
246        .into());
247    }
248    Ok(())
249}
250
251fn validate_precision(precision_bits: u32) -> Result<(), PolynomialFailure> {
252    if precision_bits > MAX_PRECISION_BITS {
253        return Err(ResourceFailure::PrecisionLimitExceeded {
254            requested: precision_bits,
255            maximum: MAX_PRECISION_BITS,
256        }
257        .into());
258    }
259    Ok(())
260}
261
262fn enclosure_add(
263    left: &DyadicEnclosure,
264    right: &DyadicEnclosure,
265) -> Result<DyadicEnclosure, PolynomialFailure> {
266    Ok(DyadicEnclosure::new(
267        left.lower().add(right.lower())?,
268        left.upper().add(right.upper())?,
269    )?)
270}
271
272fn enclosure_mul(
273    left: &DyadicEnclosure,
274    right: &DyadicEnclosure,
275) -> Result<DyadicEnclosure, PolynomialFailure> {
276    let candidates = [
277        left.lower().mul(right.lower())?,
278        left.lower().mul(right.upper())?,
279        left.upper().mul(right.lower())?,
280        left.upper().mul(right.upper())?,
281    ];
282    let mut lower = candidates[0].try_clone()?;
283    let mut upper = candidates[0].try_clone()?;
284    for candidate in candidates.iter().skip(1) {
285        if candidate.cmp(&lower) == Ordering::Less {
286            lower = candidate.try_clone()?;
287        }
288        if candidate.cmp(&upper) == Ordering::Greater {
289            upper = candidate.try_clone()?;
290        }
291    }
292    Ok(DyadicEnclosure::new(lower, upper)?)
293}