Skip to main content

tpt_math_exact/
lib.rs

1#![no_std]
2//! Arbitrary-precision rational arithmetic and interval arithmetic.
3//!
4//! This crate thin-wraps [`num_bigint`] and [`num_rational`] to expose exact
5//! rational numbers ([`BigRational`]), and layers an [`Interval`] type on top
6//! for rigorous (rounding-error-free) bounds. Because the bounds are exact
7//! rationals, interval arithmetic here never accumulates floating-point error.
8//!
9//! # Features
10//!
11//! * `std` (default) — enable the `std` feature of the wrapped crates.
12//! * `alloc` — signal an allocator is available (`no_std + alloc`).
13//!
14//! [`num_bigint`]: num_bigint
15//! [`num_rational`]: num_rational
16
17extern 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
29/// Exact rational number type alias.
30pub type Rational = BigRational;
31
32/// A closed interval `[lo, hi]` over an ordered, arithmetic type.
33///
34/// The endpoints are inclusive. Intervals support the usual arithmetic, where
35/// each operation computes the exact enclosure of the result set:
36///
37/// ```
38/// use tpt_math_exact::{Interval, Rational};
39/// use num_rational::BigRational;
40/// use num_traits::One;
41///
42/// let a = Interval::new(Rational::new(1.into(), 1.into()), Rational::new(2.into(), 1.into()));
43/// let b = Interval::new(Rational::new(3.into(), 1.into()), Rational::new(4.into(), 1.into()));
44/// let c = &a + &b;
45/// assert_eq!(c.lo(), &Rational::new(4.into(), 1.into()));
46/// assert_eq!(c.hi(), &Rational::new(6.into(), 1.into()));
47/// ```
48#[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    /// Construct an interval.
59    ///
60    /// # Panics
61    ///
62    /// Panics if `lo > hi`, in release as well as debug builds: an inverted
63    /// interval would silently make every enclosure claim wrong.
64    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    /// The lower bound.
73    pub fn lo(&self) -> &T {
74        &self.lo
75    }
76
77    /// The upper bound.
78    pub fn hi(&self) -> &T {
79        &self.hi
80    }
81
82    /// True if `x` lies within `[lo, hi]`.
83    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    /// The smallest interval containing both `self` and `other`.
94    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    /// The overlap of `self` and `other`, or `None` if they are disjoint.
104    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    /// True if the interval contains exactly one point.
118    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    /// The width `hi - lo`.
131    pub fn width(&self) -> T {
132        self.hi.clone() - self.lo.clone()
133    }
134
135    /// The midpoint `(lo + hi) / 2`.
136    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
180// Addition and subtraction need only two endpoint operations each. The
181// four-corner min/max used for products is unnecessary here: [a, b] + [c, d]
182// is [a + c, b + d] and [a, b] - [c, d] is [a - d, b - c].
183impl<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    /// Interval division `self / other`, defined only when `other` excludes zero.
236    ///
237    /// Returns `None` if `other` contains zero, because the quotient is then
238    /// unbounded or undefined. Otherwise the four endpoint quotients bound the
239    /// result, which is exact for an enclosure.
240    ///
241    /// # Examples
242    ///
243    /// ```
244    /// use tpt_math_exact::{BigInt, BigRational, Interval};
245    ///
246    /// let r = |n: i64| BigRational::from_integer(BigInt::from(n));
247    /// let q = Interval::new(r(2), r(4)).div_nonzero(&Interval::new(r(1), r(2))).unwrap();
248    /// assert_eq!(q.lo(), &r(1));
249    /// assert_eq!(q.hi(), &r(4));
250    /// assert!(Interval::new(r(1), r(2)).div_nonzero(&Interval::new(r(-1), r(1))).is_none());
251    /// ```
252    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        // [1, 2] - [3, 5] = [1 - 5, 2 - 3] = [-4, -1].
284        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        // [1, 4] - [-2, 3] = [1 - 3, 4 - (-2)] = [-2, 6].
334        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}