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}