1#![no_std]
2extern crate alloc;
18
19pub use num_bigint::{BigInt, BigUint};
20pub use num_rational::BigRational;
21pub use tpt_math_numeric as numeric;
22
23pub mod certify;
24pub mod roots;
25
26pub use certify::{certified_solve, CertifyError};
27use tpt_math_numeric::FromPrimitive;
28
29pub type Rational = BigRational;
31
32#[derive(Clone, Debug, PartialEq, Eq)]
49pub struct Interval<T> {
50 lo: T,
51 hi: T,
52}
53
54impl<T> Interval<T>
55where
56 T: Clone + PartialOrd,
57{
58 pub fn new(lo: T, hi: T) -> Self {
65 assert!(
66 !(lo.clone().partial_cmp(&hi) == Some(core::cmp::Ordering::Greater)),
67 "interval lower bound must not exceed upper bound"
68 );
69 Interval { lo, hi }
70 }
71
72 pub fn lo(&self) -> &T {
74 &self.lo
75 }
76
77 pub fn hi(&self) -> &T {
79 &self.hi
80 }
81
82 pub fn contains(&self, x: &T) -> bool {
84 self.lo
85 .partial_cmp(x)
86 .is_some_and(|o| o != core::cmp::Ordering::Greater)
87 && self
88 .hi
89 .partial_cmp(x)
90 .is_some_and(|o| o != core::cmp::Ordering::Less)
91 }
92
93 pub fn hull(&self, other: &Interval<T>) -> Interval<T>
95 where
96 T: Ord,
97 {
98 let lo = core::cmp::min(self.lo.clone(), other.lo.clone());
99 let hi = core::cmp::max(self.hi.clone(), other.hi.clone());
100 Interval::new(lo, hi)
101 }
102
103 pub fn intersect(&self, other: &Interval<T>) -> Option<Interval<T>>
105 where
106 T: Ord,
107 {
108 let lo = core::cmp::max(self.lo.clone(), other.lo.clone());
109 let hi = core::cmp::min(self.hi.clone(), other.hi.clone());
110 if lo <= hi {
111 Some(Interval::new(lo, hi))
112 } else {
113 None
114 }
115 }
116
117 pub fn is_point(&self) -> bool
119 where
120 T: PartialEq,
121 {
122 self.lo == self.hi
123 }
124}
125
126impl<T> Interval<T>
127where
128 T: Clone + Ord + core::ops::Add<Output = T> + core::ops::Sub<Output = T>,
129{
130 pub fn width(&self) -> T {
132 self.hi.clone() - self.lo.clone()
133 }
134
135 pub fn midpoint(&self) -> T
137 where
138 T: core::ops::Div<Output = T> + FromPrimitive,
139 {
140 let two = T::from_u8(2).expect("two");
141 (self.lo.clone() + self.hi.clone()) / two
142 }
143}
144
145macro_rules! impl_binop {
146 ($trait:ident, $fn:ident, $op:ident) => {
147 impl<T> core::ops::$trait<&Interval<T>> for &Interval<T>
148 where
149 T: Clone + Ord + core::ops::$trait<Output = T>,
150 {
151 type Output = Interval<T>;
152 fn $fn(self, rhs: &Interval<T>) -> Interval<T> {
153 let a = self.lo.clone().$op(rhs.lo.clone());
154 let b = self.lo.clone().$op(rhs.hi.clone());
155 let c = self.hi.clone().$op(rhs.lo.clone());
156 let d = self.hi.clone().$op(rhs.hi.clone());
157 let lo = core::cmp::min(
158 core::cmp::min(a.clone(), b.clone()),
159 core::cmp::min(c.clone(), d.clone()),
160 );
161 let hi = core::cmp::max(
162 core::cmp::max(a.clone(), b.clone()),
163 core::cmp::max(c.clone(), d.clone()),
164 );
165 Interval::new(lo, hi)
166 }
167 }
168 impl<T> core::ops::$trait<Interval<T>> for Interval<T>
169 where
170 T: Clone + Ord + core::ops::$trait<Output = T>,
171 {
172 type Output = Interval<T>;
173 fn $fn(self, rhs: Interval<T>) -> Interval<T> {
174 (&self).$fn(&rhs)
175 }
176 }
177 };
178}
179
180impl<T> core::ops::Add<&Interval<T>> for &Interval<T>
184where
185 T: Clone + Ord + core::ops::Add<Output = T>,
186{
187 type Output = Interval<T>;
188 fn add(self, rhs: &Interval<T>) -> Interval<T> {
189 Interval::new(
190 self.lo.clone() + rhs.lo.clone(),
191 self.hi.clone() + rhs.hi.clone(),
192 )
193 }
194}
195
196impl<T> core::ops::Add<Interval<T>> for Interval<T>
197where
198 T: Clone + Ord + core::ops::Add<Output = T>,
199{
200 type Output = Interval<T>;
201 fn add(self, rhs: Interval<T>) -> Interval<T> {
202 core::ops::Add::add(&self, &rhs)
203 }
204}
205
206impl<T> core::ops::Sub<&Interval<T>> for &Interval<T>
207where
208 T: Clone + Ord + core::ops::Sub<Output = T>,
209{
210 type Output = Interval<T>;
211 fn sub(self, rhs: &Interval<T>) -> Interval<T> {
212 Interval::new(
213 self.lo.clone() - rhs.hi.clone(),
214 self.hi.clone() - rhs.lo.clone(),
215 )
216 }
217}
218
219impl<T> core::ops::Sub<Interval<T>> for Interval<T>
220where
221 T: Clone + Ord + core::ops::Sub<Output = T>,
222{
223 type Output = Interval<T>;
224 fn sub(self, rhs: Interval<T>) -> Interval<T> {
225 core::ops::Sub::sub(&self, &rhs)
226 }
227}
228
229impl_binop!(Mul, mul, mul);
230
231impl<T> Interval<T>
232where
233 T: Clone + Ord + num_traits::Zero + core::ops::Div<Output = T> + core::ops::Mul<Output = T>,
234{
235 pub fn div_nonzero(&self, other: &Interval<T>) -> Option<Interval<T>> {
253 let zero = T::zero();
254 if other.lo <= zero && other.hi >= zero {
255 return None;
256 }
257 let corners = [
258 self.lo.clone() / other.lo.clone(),
259 self.lo.clone() / other.hi.clone(),
260 self.hi.clone() / other.lo.clone(),
261 self.hi.clone() / other.hi.clone(),
262 ];
263 let lo = corners.iter().min().cloned()?;
264 let hi = corners.iter().max().cloned()?;
265 Some(Interval::new(lo, hi))
266 }
267}
268
269#[cfg(test)]
270mod tests {
271 use super::*;
272 use num_rational::BigRational;
273
274 fn rat(n: i64) -> BigRational {
275 BigRational::new(n.into(), 1.into())
276 }
277 fn iv(a: i64, b: i64) -> Interval<BigRational> {
278 Interval::new(rat(a), rat(b))
279 }
280
281 #[test]
282 fn sub_endpoints_are_exact() {
283 let a = Interval::new(1i64, 2);
285 let b = Interval::new(3i64, 5);
286 assert_eq!(&a - &b, Interval::new(-4, -1));
287 assert_eq!(&a + &b, Interval::new(4, 7));
288 }
289
290 #[test]
291 fn add_encloses() {
292 let c = iv(1, 2) + iv(3, 4);
293 assert_eq!(c.lo(), &rat(4));
294 assert_eq!(c.hi(), &rat(6));
295 }
296
297 #[test]
298 fn mul_encloses_all_corners() {
299 let c = iv(-1, 2) * iv(-3, 4);
300 assert_eq!(c.lo(), &rat(-6));
301 assert_eq!(c.hi(), &rat(8));
302 }
303
304 #[test]
305 fn contains_and_hull() {
306 let a = iv(0, 5);
307 assert!(a.contains(&rat(3)));
308 assert!(!a.contains(&rat(6)));
309 let b = iv(3, 10);
310 let h = a.hull(&b);
311 assert_eq!(h.lo(), &rat(0));
312 assert_eq!(h.hi(), &rat(10));
313 }
314
315 #[test]
316 fn intersect() {
317 let a = iv(0, 5);
318 let b = iv(3, 10);
319 assert_eq!(a.intersect(&b), Some(iv(3, 5)));
320 assert_eq!(iv(0, 1).intersect(&iv(2, 3)), None);
321 }
322
323 #[test]
324 fn midpoint_and_width() {
325 let a = iv(2, 4);
326 assert_eq!(a.width(), rat(2));
327 let m = a.midpoint();
328 assert_eq!(m, rat(3));
329 }
330
331 #[test]
332 fn sub_encloses() {
333 let c = iv(1, 4) - iv(-2, 3);
335 assert_eq!(c.lo(), &rat(-2));
336 assert_eq!(c.hi(), &rat(6));
337 }
338
339 #[test]
340 fn is_point_detects_degenerate_interval() {
341 assert!(iv(3, 3).is_point());
342 assert!(!iv(3, 4).is_point());
343 }
344
345 #[test]
346 fn contains_respects_endpoints() {
347 let a = iv(0, 5);
348 assert!(a.contains(&rat(0)));
349 assert!(a.contains(&rat(5)));
350 assert!(a.contains(&rat(-0)));
351 }
352}