#![allow(clippy::float_cmp)]
use core::fmt;
use core::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign};
use crate::dd::DoubleDouble;
use crate::eft::{fast_two_sum, two_prod};
const ETA: f64 = f64::from_bits(1);
const EXACT_RESIDUAL: f64 = f64::from_bits((1023 - 968) << 52);
const EXACT_SQRT_RESIDUAL: f64 = f64::from_bits((1023 - 900) << 52);
const UPSCALE: f64 = f64::from_bits((1023 + 200) << 52);
const DOWNSCALE: f64 = f64::from_bits((1023 - 200) << 52);
const DOWNSCALE_SQRT: f64 = f64::from_bits((1023 - 100) << 52);
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Dir {
Down,
Up,
}
#[inline]
fn step(v: f64, sigma: f64, dir: Dir) -> f64 {
debug_assert!(v.is_finite() && !sigma.is_nan(), "step({v:e}, {sigma:e})");
match dir {
Dir::Down if sigma < 0.0 => v.next_down(),
Dir::Up if sigma > 0.0 => v.next_up(),
_ => v,
}
}
#[inline]
fn overflow(v: f64, dir: Dir) -> f64 {
debug_assert!(v.is_infinite());
match (dir, v > 0.0) {
(Dir::Down, true) => f64::MAX,
(Dir::Up, false) => f64::MIN,
_ => v,
}
}
#[inline]
fn descale(w: f64, delta: f64, dir: Dir) -> f64 {
let v = w * DOWNSCALE; let tau = w - v * UPSCALE; step(v, if tau == 0.0 { delta } else { tau }, dir) }
#[inline]
fn add_dir(a: f64, b: f64, dir: Dir) -> f64 {
let v = a + b; debug_assert!(!v.is_nan(), "add_dir({a:e}, {b:e})");
if a.is_infinite() || b.is_infinite() {
return v; }
if v.is_infinite() {
return overflow(v, dir); }
let (hi, lo) = if a.abs() >= b.abs() { (a, b) } else { (b, a) };
let (_, sigma) = fast_two_sum(hi, lo);
step(v, sigma, dir) }
#[inline]
fn mul_dir(a: f64, b: f64, dir: Dir) -> f64 {
debug_assert!(!a.is_nan() && !b.is_nan(), "mul_dir({a:e}, {b:e})");
if a == 0.0 || b == 0.0 {
return 0.0; }
let v = a * b; if a.is_infinite() || b.is_infinite() {
return v; }
if v.is_infinite() {
return overflow(v, dir); }
if v.abs() >= EXACT_RESIDUAL {
return step(v, a.mul_add(b, -v), dir); }
if v == 0.0 {
return match (dir, (a > 0.0) == (b > 0.0)) {
(Dir::Up, true) => ETA,
(Dir::Down, false) => -ETA,
_ => 0.0,
};
}
let (s, l) = if a.abs() <= b.abs() { (a, b) } else { (b, a) };
let (w, delta) = two_prod(s * UPSCALE, l);
descale(w, delta, dir)
}
#[inline]
fn div_dir(a: f64, b: f64, dir: Dir) -> f64 {
debug_assert!(
!a.is_nan() && !b.is_nan() && b != 0.0,
"div_dir({a:e}, {b:e})"
);
debug_assert!(a.is_finite() || b.is_finite(), "div_dir: ∞ / ∞");
if a == 0.0 || b.is_infinite() {
return 0.0; }
let v = a / b; if a.is_infinite() {
return v; }
if v.is_infinite() {
return overflow(v, dir); }
let sigma = |rho: f64| if b > 0.0 { rho } else { -rho };
if a.abs() >= EXACT_RESIDUAL {
return step(v, sigma((-v).mul_add(b, a)), dir); }
let a2 = a * UPSCALE;
let w = a2 / b;
descale(w, sigma((-w).mul_add(b, a2)), dir)
}
#[inline]
fn sqrt_dir(a: f64, dir: Dir) -> f64 {
debug_assert!(a >= 0.0, "sqrt_dir({a:e})");
if a == 0.0 {
return 0.0; }
if a.is_infinite() {
return a; }
let (x, back) = if a < EXACT_SQRT_RESIDUAL {
(a * UPSCALE, DOWNSCALE_SQRT)
} else {
(a, 1.0)
};
let v = x.sqrt(); step(v, (-v).mul_add(v, x), dir) * back }
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Interval {
lo: f64,
hi: f64,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct InvalidInterval;
impl Interval {
pub const ENTIRE: Self = Self {
lo: f64::NEG_INFINITY,
hi: f64::INFINITY,
};
pub const EMPTY: Self = Self {
lo: f64::INFINITY,
hi: f64::NEG_INFINITY,
};
pub const ZERO: Self = Self { lo: 0.0, hi: 0.0 };
#[inline]
fn raw(lo: f64, hi: f64) -> Self {
let x = Self { lo, hi };
debug_assert!(
x.check_invariants().is_ok() && !x.is_empty(),
"[{lo:e}, {hi:e}]: {:?}",
x.check_invariants()
);
x
}
pub fn new(lo: f64, hi: f64) -> Result<Self, InvalidInterval> {
if lo <= hi && lo < f64::INFINITY && hi > f64::NEG_INFINITY {
Ok(Self { lo, hi })
} else {
Err(InvalidInterval)
}
}
#[must_use]
pub fn point(x: f64) -> Self {
assert!(x.is_finite(), "Interval::point({x}): not a real number");
Self { lo: x, hi: x }
}
#[must_use]
pub fn mid_rad(m: f64, r: f64) -> Self {
assert!(
!m.is_nan() && r >= 0.0,
"Interval::mid_rad({m}, {r}): NaN or a negative radius"
);
if m.is_infinite() || r.is_infinite() {
return Self::ENTIRE;
}
Self::raw(add_dir(m, -r, Dir::Down), add_dir(m, r, Dir::Up))
}
#[must_use]
pub fn enclose(x: DoubleDouble) -> Self {
let (h, l) = (x.hi(), x.lo());
if !h.is_finite() || !l.is_finite() {
return Self::ENTIRE;
}
if l > 0.0 {
Self::raw(h, h.next_up())
} else if l < 0.0 {
Self::raw(h.next_down(), h)
} else {
Self::raw(h, h)
}
}
#[must_use]
pub const fn inf(self) -> f64 {
self.lo
}
#[must_use]
pub const fn sup(self) -> f64 {
self.hi
}
#[inline]
#[must_use]
pub fn is_empty(self) -> bool {
self.lo > self.hi
}
#[must_use]
pub fn mid(self) -> f64 {
if self.is_empty() {
return f64::NAN;
}
match (self.lo.is_finite(), self.hi.is_finite()) {
(false, false) => 0.0,
(false, true) => f64::MIN,
(true, false) => f64::MAX,
(true, true) => f64::midpoint(self.lo, self.hi),
}
}
#[must_use]
pub fn width(self) -> f64 {
if self.is_empty() {
return f64::NAN;
}
add_dir(self.hi, -self.lo, Dir::Up)
}
#[must_use]
pub fn mag(self) -> f64 {
if self.is_empty() {
return f64::NAN;
}
self.lo.abs().max(self.hi.abs())
}
#[must_use]
pub fn mig(self) -> f64 {
if self.is_empty() {
f64::NAN
} else if self.lo > 0.0 {
self.lo
} else if self.hi < 0.0 {
-self.hi
} else {
0.0
}
}
#[must_use]
pub fn contains(self, x: f64) -> bool {
x.is_finite() && self.lo <= x && x <= self.hi
}
#[must_use]
pub fn is_subset_of(self, other: Self) -> bool {
self.is_empty() || (other.lo <= self.lo && self.hi <= other.hi)
}
#[must_use]
pub fn certainly_le(self, b: f64) -> bool {
!self.is_empty() && self.hi <= b
}
#[must_use]
pub fn certainly_ge(self, a: f64) -> bool {
!self.is_empty() && self.lo >= a
}
#[must_use]
pub fn certainly_within(self, t: f64) -> bool {
!self.is_empty() && -t <= self.lo && self.hi <= t
}
#[must_use]
pub fn hull(self, other: Self) -> Self {
Self {
lo: self.lo.min(other.lo),
hi: self.hi.max(other.hi),
}
}
#[must_use]
pub fn intersection(self, other: Self) -> Self {
let (lo, hi) = (self.lo.max(other.lo), self.hi.min(other.hi));
if lo <= hi {
Self { lo, hi }
} else {
Self::EMPTY
}
}
#[must_use]
pub fn abs(self) -> Self {
if self.is_empty() || self.lo >= 0.0 {
self
} else if self.hi <= 0.0 {
-self
} else {
Self::raw(0.0, (-self.lo).max(self.hi))
}
}
#[must_use]
pub fn square(self) -> Self {
if self.is_empty() {
return self;
}
let (a, b) = (self.lo, self.hi);
if a >= 0.0 {
Self::raw(mul_dir(a, a, Dir::Down), mul_dir(b, b, Dir::Up))
} else if b <= 0.0 {
Self::raw(mul_dir(b, b, Dir::Down), mul_dir(a, a, Dir::Up))
} else {
let m = (-a).max(b);
Self::raw(0.0, mul_dir(m, m, Dir::Up))
}
}
#[must_use]
pub fn sqrt(self) -> Self {
if self.is_empty() || self.hi < 0.0 {
return Self::EMPTY;
}
Self::raw(
sqrt_dir(self.lo.max(0.0), Dir::Down),
sqrt_dir(self.hi, Dir::Up),
)
}
pub fn check_invariants(self) -> Result<(), &'static str> {
if self.lo.is_nan() || self.hi.is_nan() {
return Err("I2: an endpoint is NaN");
}
if self.lo == f64::INFINITY && self.hi == f64::NEG_INFINITY {
return Ok(()); }
if self.lo > self.hi {
return Err("I2: lo > hi in an interval that is not the stored empty set");
}
if self.lo == f64::INFINITY {
return Err("I2: the lower endpoint is +∞");
}
if self.hi == f64::NEG_INFINITY {
return Err("I2: the upper endpoint is −∞");
}
Ok(())
}
}
impl Add for Interval {
type Output = Self;
fn add(self, rhs: Self) -> Self {
if self.is_empty() || rhs.is_empty() {
return Self::EMPTY;
}
Self::raw(
add_dir(self.lo, rhs.lo, Dir::Down),
add_dir(self.hi, rhs.hi, Dir::Up),
)
}
}
impl Sub for Interval {
type Output = Self;
fn sub(self, rhs: Self) -> Self {
if self.is_empty() || rhs.is_empty() {
return Self::EMPTY;
}
Self::raw(
add_dir(self.lo, -rhs.hi, Dir::Down),
add_dir(self.hi, -rhs.lo, Dir::Up),
)
}
}
impl Mul for Interval {
type Output = Self;
fn mul(self, rhs: Self) -> Self {
if self.is_empty() || rhs.is_empty() {
return Self::EMPTY;
}
let (a, b, c, d) = (self.lo, self.hi, rhs.lo, rhs.hi);
let dn = |x, y| mul_dir(x, y, Dir::Down);
let up = |x, y| mul_dir(x, y, Dir::Up);
let (lo, hi) = if a >= 0.0 {
if c >= 0.0 {
(dn(a, c), up(b, d))
} else if d <= 0.0 {
(dn(b, c), up(a, d))
} else {
(dn(b, c), up(b, d))
}
} else if b <= 0.0 {
if c >= 0.0 {
(dn(a, d), up(b, c))
} else if d <= 0.0 {
(dn(b, d), up(a, c))
} else {
(dn(a, d), up(a, c))
}
} else if c >= 0.0 {
(dn(a, d), up(b, d))
} else if d <= 0.0 {
(dn(b, c), up(a, c))
} else {
(dn(a, d).min(dn(b, c)), up(a, c).max(up(b, d)))
};
Self::raw(lo, hi)
}
}
impl Div for Interval {
type Output = Self;
fn div(self, rhs: Self) -> Self {
if self.is_empty() || rhs.is_empty() {
return Self::EMPTY;
}
let (a, b, c, d) = (self.lo, self.hi, rhs.lo, rhs.hi);
let dn = |x, y| div_dir(x, y, Dir::Down);
let up = |x, y| div_dir(x, y, Dir::Up);
if c == 0.0 && d == 0.0 {
return Self::ENTIRE; }
if a == 0.0 && b == 0.0 {
return Self::ZERO;
}
if c > 0.0 {
if a >= 0.0 {
Self::raw(dn(a, d), up(b, c))
} else if b <= 0.0 {
Self::raw(dn(a, c), up(b, d))
} else {
Self::raw(dn(a, c), up(b, c))
}
} else if d < 0.0 {
if a >= 0.0 {
Self::raw(dn(b, d), up(a, c))
} else if b <= 0.0 {
Self::raw(dn(b, c), up(a, d))
} else {
Self::raw(dn(b, d), up(a, d))
}
} else if c == 0.0 {
if a >= 0.0 {
Self::raw(dn(a, d), f64::INFINITY)
} else if b <= 0.0 {
Self::raw(f64::NEG_INFINITY, up(b, d))
} else {
Self::ENTIRE
}
} else if d == 0.0 {
if a >= 0.0 {
Self::raw(f64::NEG_INFINITY, up(a, c))
} else if b <= 0.0 {
Self::raw(dn(b, c), f64::INFINITY)
} else {
Self::ENTIRE
}
} else {
Self::ENTIRE
}
}
}
impl Add<f64> for Interval {
type Output = Self;
fn add(self, rhs: f64) -> Self {
if self.is_empty() {
return self;
}
if !rhs.is_finite() {
return Self::ENTIRE;
}
Self::raw(
add_dir(self.lo, rhs, Dir::Down),
add_dir(self.hi, rhs, Dir::Up),
)
}
}
impl Sub<f64> for Interval {
type Output = Self;
fn sub(self, rhs: f64) -> Self {
self + (-rhs)
}
}
impl Mul<f64> for Interval {
type Output = Self;
fn mul(self, rhs: f64) -> Self {
if self.is_empty() {
return self;
}
if !rhs.is_finite() {
return Self::ENTIRE;
}
let (a, b) = if rhs >= 0.0 {
(self.lo, self.hi)
} else {
(self.hi, self.lo)
};
Self::raw(mul_dir(a, rhs, Dir::Down), mul_dir(b, rhs, Dir::Up))
}
}
impl Div<f64> for Interval {
type Output = Self;
fn div(self, rhs: f64) -> Self {
if self.is_empty() {
return self;
}
if !rhs.is_finite() || rhs == 0.0 {
return Self::ENTIRE;
}
let (a, b) = if rhs > 0.0 {
(self.lo, self.hi)
} else {
(self.hi, self.lo)
};
Self::raw(div_dir(a, rhs, Dir::Down), div_dir(b, rhs, Dir::Up))
}
}
macro_rules! assign_ops {
($($tr:ident, $f:ident, $op:tt;)*) => {$(
impl $tr for Interval {
fn $f(&mut self, rhs: Self) {
*self = *self $op rhs;
}
}
impl $tr<f64> for Interval {
fn $f(&mut self, rhs: f64) {
*self = *self $op rhs;
}
}
)*};
}
assign_ops! {
AddAssign, add_assign, +;
SubAssign, sub_assign, -;
MulAssign, mul_assign, *;
DivAssign, div_assign, /;
}
#[inline]
fn left_point(y: f64, x: Interval) -> Result<Interval, Interval> {
if x.is_empty() {
Err(Interval::EMPTY)
} else if y.is_finite() {
Ok(Interval { lo: y, hi: y })
} else {
Err(Interval::ENTIRE)
}
}
impl Add<Interval> for f64 {
type Output = Interval;
fn add(self, rhs: Interval) -> Interval {
left_point(self, rhs).map_or_else(|r| r, |p| p + rhs)
}
}
impl Sub<Interval> for f64 {
type Output = Interval;
fn sub(self, rhs: Interval) -> Interval {
left_point(self, rhs).map_or_else(|r| r, |p| p - rhs)
}
}
impl Mul<Interval> for f64 {
type Output = Interval;
fn mul(self, rhs: Interval) -> Interval {
left_point(self, rhs).map_or_else(|r| r, |p| p * rhs)
}
}
impl Div<Interval> for f64 {
type Output = Interval;
fn div(self, rhs: Interval) -> Interval {
left_point(self, rhs).map_or_else(|r| r, |p| p / rhs)
}
}
impl Neg for Interval {
type Output = Self;
fn neg(self) -> Self {
Self {
lo: -self.hi,
hi: -self.lo,
}
}
}
impl From<f64> for Interval {
fn from(x: f64) -> Self {
if x.is_finite() {
Self { lo: x, hi: x }
} else {
Self::ENTIRE
}
}
}
impl fmt::Display for InvalidInterval {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str("invalid interval: the endpoints are not lo <= hi with lo < +inf and hi > -inf")
}
}
impl core::error::Error for InvalidInterval {}
const EXACT_FRACTION_DIGITS: usize = 1074;
const EXACT_MANTISSA_DIGITS: usize = 800;
fn increment(digits: &mut [u8]) -> bool {
for d in digits.iter_mut().rev() {
if *d == b'9' {
*d = b'0';
} else {
*d += 1;
return false;
}
}
true
}
fn away(x: f64, discarded: &[u8], dir: Dir) -> bool {
discarded.iter().any(|&d| d != b'0') && ((x > 0.0) == (dir == Dir::Up))
}
fn write_fixed(f: &mut fmt::Formatter<'_>, x: f64, p: usize, dir: Dir) -> fmt::Result {
if !x.is_finite() || p >= EXACT_FRACTION_DIGITS {
return fmt::Display::fmt(&x, f);
}
let exact = format!("{:.*}", EXACT_FRACTION_DIGITS, x.abs()); let (int, frac) = exact.split_once('.').expect("a fractional part");
let mut kept: Vec<u8> = int.bytes().chain(frac.bytes().take(p)).collect();
let carry = away(x, &frac.as_bytes()[p..], dir) && increment(&mut kept); let (int, frac) = kept.split_at(int.len());
if x.is_sign_negative() {
f.write_str("-")?;
} else if f.sign_plus() {
f.write_str("+")?;
}
if carry {
f.write_str("1")?;
}
f.write_str(core::str::from_utf8(int).expect("ASCII digits"))?;
if p > 0 {
f.write_str(".")?;
f.write_str(core::str::from_utf8(frac).expect("ASCII digits"))?;
}
Ok(())
}
fn write_exp(f: &mut fmt::Formatter<'_>, x: f64, p: usize, dir: Dir) -> fmt::Result {
if !x.is_finite() || p >= EXACT_MANTISSA_DIGITS {
return fmt::LowerExp::fmt(&x, f);
}
let exact = format!("{:.*e}", EXACT_MANTISSA_DIGITS, x.abs()); let (mantissa, exponent) = exact.split_once('e').expect("an exponent");
let mut exponent: i32 = exponent.parse().expect("a decimal exponent");
let digits: Vec<u8> = mantissa.bytes().filter(|&c| c != b'.').collect();
let (kept, discarded) = digits.split_at(1 + p);
let mut kept = kept.to_vec();
if away(x, discarded, dir) && increment(&mut kept) {
kept[0] = b'1';
exponent += 1;
}
if x.is_sign_negative() {
f.write_str("-")?;
} else if f.sign_plus() {
f.write_str("+")?;
}
f.write_str(core::str::from_utf8(&kept[..1]).expect("ASCII digits"))?;
if p > 0 {
f.write_str(".")?;
f.write_str(core::str::from_utf8(&kept[1..]).expect("ASCII digits"))?;
}
write!(f, "e{exponent}")
}
impl fmt::Display for Interval {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
if self.is_empty() {
return f.write_str("∅");
}
let p = f.precision();
f.write_str("[")?;
match p {
None => fmt::Display::fmt(&self.lo, f)?,
Some(p) => write_fixed(f, self.lo, p, Dir::Down)?,
}
f.write_str(", ")?;
match p {
None => fmt::Display::fmt(&self.hi, f)?,
Some(p) => write_fixed(f, self.hi, p, Dir::Up)?,
}
f.write_str("]")
}
}
impl fmt::LowerExp for Interval {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
if self.is_empty() {
return f.write_str("∅");
}
let p = f.precision();
f.write_str("[")?;
match p {
None => fmt::LowerExp::fmt(&self.lo, f)?,
Some(p) => write_exp(f, self.lo, p, Dir::Down)?,
}
f.write_str(", ")?;
match p {
None => fmt::LowerExp::fmt(&self.hi, f)?,
Some(p) => write_exp(f, self.hi, p, Dir::Up)?,
}
f.write_str("]")
}
}
#[cfg(test)]
#[allow(clippy::disallowed_methods)] mod tests {
use super::*;
const MAX: f64 = f64::MAX;
const INF: f64 = f64::INFINITY;
fn iv(lo: f64, hi: f64) -> Interval {
Interval::new(lo, hi).expect("a valid interval")
}
#[test]
fn constructors_enforce_i2() {
assert_eq!(
Interval::new(1.0, 2.0).map(|x| (x.inf(), x.sup())),
Ok((1.0, 2.0))
);
for (lo, hi) in [
(2.0, 1.0),
(f64::NAN, 1.0),
(1.0, f64::NAN),
(INF, INF),
(-INF, -INF),
(INF, -INF),
] {
assert_eq!(Interval::new(lo, hi), Err(InvalidInterval), "[{lo}, {hi}]");
}
assert_eq!(Interval::new(-INF, INF), Ok(Interval::ENTIRE));
for x in [
Interval::ENTIRE,
Interval::EMPTY,
Interval::ZERO,
iv(-INF, 3.0),
] {
assert_eq!(x.check_invariants(), Ok(()));
}
for (lo, hi) in [
(2.0, 1.0),
(f64::NAN, 1.0),
(INF, INF),
(-INF, -INF),
(INF, 0.0),
] {
assert!(
Interval { lo, hi }.check_invariants().is_err(),
"[{lo}, {hi}]"
);
}
assert!(Interval::EMPTY.is_empty() && !Interval::ZERO.is_empty());
assert_eq!(Interval::point(-0.0), Interval::ZERO);
}
#[test]
#[should_panic(expected = "not a real number")]
fn point_rejects_nan() {
let _ = Interval::point(f64::NAN);
}
#[test]
#[should_panic(expected = "not a real number")]
fn point_rejects_infinity() {
let _ = Interval::point(INF);
}
#[test]
#[should_panic(expected = "negative radius")]
fn mid_rad_rejects_a_negative_radius() {
let _ = Interval::mid_rad(0.0, -1.0);
}
#[test]
fn mid_rad_rounds_outward() {
assert_eq!(Interval::mid_rad(1.0, 0.0), Interval::point(1.0));
assert_eq!(Interval::mid_rad(1.0, 0.5), iv(0.5, 1.5));
let x = Interval::mid_rad(1.0, 2f64.powi(-60));
assert_eq!((x.inf(), x.sup()), (1.0_f64.next_down(), 1.0_f64.next_up()));
assert_eq!(Interval::mid_rad(1.0, INF), Interval::ENTIRE);
assert_eq!(Interval::mid_rad(-INF, 1.0), Interval::ENTIRE);
assert_eq!(Interval::mid_rad(MAX, MAX), iv(0.0, INF));
}
#[test]
fn enclose_is_the_two_neighbours() {
let u = 2f64.powi(-53);
assert_eq!(
Interval::enclose(DoubleDouble::from_f64(3.0)),
Interval::point(3.0)
);
let up = Interval::enclose(DoubleDouble::from_sum(1.0, u * u));
assert_eq!((up.inf(), up.sup()), (1.0, 1.0_f64.next_up()));
let down = Interval::enclose(DoubleDouble::from_sum(1.0, -u * u));
assert_eq!((down.inf(), down.sup()), (1.0_f64.next_down(), 1.0));
let top = Interval::enclose(DoubleDouble::from_sum(MAX, 1.0));
assert_eq!((top.inf(), top.sup()), (MAX, INF));
assert_eq!(Interval::enclose(DoubleDouble::NAN), Interval::ENTIRE);
assert_eq!(Interval::enclose(DoubleDouble::INFINITY), Interval::ENTIRE);
assert_eq!(Interval::enclose(-DoubleDouble::INFINITY), Interval::ENTIRE);
}
#[test]
fn sums_round_outward_by_one_step() {
let u = 2f64.powi(-53);
let s = Interval::point(1.0) + u;
assert_eq!((s.inf(), s.sup()), (1.0, 1.0_f64.next_up()));
assert_eq!(
Interval::point(1.0) - u,
Interval::point(1.0_f64.next_down())
);
let s = Interval::point(1.0) - 0.5 * u;
assert_eq!((s.inf(), s.sup()), (1.0_f64.next_down(), 1.0));
assert_eq!(
Interval::point(3.0) + Interval::point(4.0),
Interval::point(7.0)
);
assert_eq!(Interval::point(ETA) + ETA, Interval::point(2.0 * ETA));
assert_eq!(Interval::point(ETA) - ETA, Interval::ZERO);
assert_eq!(iv(1.0, 2.0) - iv(1.0, 2.0), iv(-1.0, 1.0));
}
#[test]
fn overflow_saturates_the_inner_endpoint() {
let s = Interval::point(MAX) + MAX;
assert_eq!((s.inf(), s.sup()), (MAX, INF));
let s = Interval::point(-MAX) - MAX;
assert_eq!((s.inf(), s.sup()), (-INF, -MAX));
let p = Interval::point(MAX) * 2.0;
assert_eq!((p.inf(), p.sup()), (MAX, INF));
let p = Interval::point(MAX) * Interval::point(-2.0);
assert_eq!((p.inf(), p.sup()), (-INF, -MAX));
let q = Interval::point(MAX) / 0.5;
assert_eq!((q.inf(), q.sup()), (MAX, INF));
let q = Interval::point(1.0) / Interval::point(-ETA);
assert_eq!((q.inf(), q.sup()), (-INF, -MAX));
let s = Interval::point(MAX) + 2f64.powi(969);
assert_eq!((s.inf(), s.sup()), (MAX, INF));
assert_eq!(Interval::point(MAX).square().sup(), INF);
assert_eq!(Interval::point(MAX).square().inf(), MAX);
}
#[test]
fn products_in_the_underflow_range_are_still_tight() {
let x = 1.0 + f64::EPSILON;
let p = Interval::point(1e-200) * 1e-200;
assert_eq!((p.inf(), p.sup()), (0.0, ETA));
let p = Interval::point(1e-200) * -1e-200;
assert_eq!((p.inf(), p.sup()), (-ETA, 0.0));
let p = Interval::point(ETA) * 0.5;
assert_eq!((p.inf(), p.sup()), (0.0, ETA));
assert_eq!(
Interval::point(2f64.powi(-500)) * 2f64.powi(-560),
Interval::point(16384.0 * ETA)
);
assert_eq!(Interval::point(3.0 * ETA) * 1.0, Interval::point(3.0 * ETA));
let a = x * 2f64.powi(-486);
let p = Interval::point(a) * a;
let v = a * a;
assert_eq!(a.mul_add(a, -v), 0.0);
assert_eq!((p.inf(), p.sup()), (v, v.next_up()));
let p = Interval::point(3.0 * ETA) * 0.5;
assert_eq!((p.inf(), p.sup()), (ETA, 2.0 * ETA));
let p = Interval::point(5.0 * ETA) * -0.5;
assert_eq!((p.inf(), p.sup()), (-3.0 * ETA, -2.0 * ETA));
}
#[test]
fn quotients_round_outward_everywhere() {
let t = Interval::point(1.0) / 3.0;
assert_eq!(t.sup(), t.inf().next_up());
assert!(t.inf() * 3.0 <= 1.0 && t.contains(1.0 / 3.0));
assert_eq!(
Interval::point(6.0) / Interval::point(-3.0),
Interval::point(-2.0)
);
let q = Interval::point(ETA) / 3.0;
assert_eq!((q.inf(), q.sup()), (0.0, ETA));
let q = Interval::point(-ETA) / 3.0;
assert_eq!((q.inf(), q.sup()), (-ETA, 0.0));
let q = Interval::point(3.0 * ETA) / 2.0;
assert_eq!((q.inf(), q.sup()), (ETA, 2.0 * ETA));
assert_eq!(Interval::point(6.0 * ETA) / 3.0, Interval::point(2.0 * ETA));
let q = Interval::point(2f64.powi(-1000)) / (3.0 * 2f64.powi(-1000));
assert_eq!(q, Interval::point(1.0) / 3.0);
let (a, b) = (
(1.0 + 2.0 * f64::EPSILON) * 2f64.powi(-1000),
1.0 + f64::EPSILON,
);
let v = a / b;
assert_eq!(v, b * 2f64.powi(-1000));
assert_eq!((-v).mul_add(b, a), 0.0);
let q = Interval::point(a) / b;
assert_eq!((q.inf(), q.sup()), (v.next_down(), v));
let q = Interval::point(a) / Interval::point(-b);
assert_eq!((q.inf(), q.sup()), (-v, (-v).next_up()));
let q = Interval::point(2f64.powi(-1000)) / -2f64.powi(1000);
assert_eq!((q.inf(), q.sup()), (-ETA, 0.0));
}
#[test]
fn division_by_an_interval_with_zero() {
let one_two = iv(1.0, 2.0);
assert_eq!(one_two / iv(-1.0, 1.0), Interval::ENTIRE);
assert_eq!(one_two / Interval::ZERO, Interval::ENTIRE);
assert_eq!(Interval::ZERO / Interval::ZERO, Interval::ENTIRE);
assert_eq!(one_two / 0.0, Interval::ENTIRE);
assert_eq!(Interval::ZERO / iv(-1.0, 1.0), Interval::ZERO);
assert_eq!(one_two / iv(0.0, 4.0), iv(0.25, INF));
assert_eq!(-one_two / iv(0.0, 4.0), iv(-INF, -0.25));
assert_eq!(one_two / iv(-4.0, 0.0), iv(-INF, -0.25));
assert_eq!(-one_two / iv(-4.0, 0.0), iv(0.25, INF));
assert_eq!(iv(-1.0, 2.0) / iv(0.0, 4.0), Interval::ENTIRE);
assert_eq!(iv(0.0, 2.0) / iv(0.0, 4.0), iv(0.0, INF));
}
#[test]
fn infinite_endpoints_bound_sets_of_reals() {
let pos = iv(0.0, INF);
assert_eq!(pos * Interval::ZERO, Interval::ZERO);
assert_eq!(Interval::ENTIRE * 0.0, Interval::ZERO);
assert_eq!(pos * iv(2.0, 3.0), pos);
assert_eq!(pos * iv(-3.0, 2.0), Interval::ENTIRE);
assert_eq!(pos + iv(1.0, 2.0), iv(1.0, INF));
assert_eq!(pos - pos, Interval::ENTIRE);
assert_eq!(iv(1.0, INF) / iv(2.0, INF), pos);
assert_eq!(iv(-INF, -1.0) / iv(2.0, 4.0), iv(-INF, -0.25));
assert_eq!(iv(4.0, INF).sqrt(), iv(2.0, INF));
assert_eq!(iv(-INF, 3.0).square(), pos);
assert_eq!(iv(-INF, 3.0).abs(), pos);
assert_eq!(-iv(-INF, 3.0), iv(-3.0, INF));
for bad in [f64::NAN, INF, -INF] {
assert_eq!(iv(1.0, 2.0) + bad, Interval::ENTIRE);
assert_eq!(iv(1.0, 2.0) - bad, Interval::ENTIRE);
assert_eq!(iv(1.0, 2.0) * bad, Interval::ENTIRE);
assert_eq!(iv(1.0, 2.0) / bad, Interval::ENTIRE);
}
}
#[test]
fn the_empty_set_propagates_and_proves_nothing() {
let e = Interval::EMPTY;
let x = iv(1.0, 2.0);
for r in [e + x, x + e, e - x, x - e, e * x, x * e, e / x, x / e] {
assert!(r.is_empty());
}
for r in [e + 1.0, e - 1.0, e * 1.0, e / 1.0, e / 0.0, e + f64::NAN] {
assert!(r.is_empty());
}
assert!((-e).is_empty() && e.abs().is_empty() && e.square().is_empty());
assert!(e.sqrt().is_empty() && iv(-2.0, -1.0).sqrt().is_empty());
assert_eq!(e.hull(x), x);
assert_eq!(x.hull(e), x);
assert!(e.hull(e).is_empty() && e.intersection(x).is_empty());
assert!(x.intersection(iv(3.0, 4.0)).is_empty());
assert!(e.mid().is_nan() && e.width().is_nan() && e.mag().is_nan() && e.mig().is_nan());
assert!(!e.contains(0.0));
assert!(e.is_subset_of(x) && e.is_subset_of(e) && !x.is_subset_of(e));
assert!(!e.certainly_le(INF) && !e.certainly_ge(-INF) && !e.certainly_within(INF));
assert_eq!(e.check_invariants(), Ok(()));
assert_eq!(e.to_string(), "∅");
}
#[test]
fn square_roots_are_tight() {
assert_eq!(iv(4.0, 9.0).sqrt(), iv(2.0, 3.0));
assert_eq!(iv(-4.0, 9.0).sqrt(), iv(0.0, 3.0));
assert_eq!(Interval::ZERO.sqrt(), Interval::ZERO);
let r = Interval::point(2.0).sqrt();
assert_eq!(r.sup(), r.inf().next_up());
assert!(r.inf() * r.inf() < 2.0 && r.sup() * r.sup() > 2.0);
assert_eq!(
Interval::point(ETA).sqrt(),
Interval::point(2f64.powi(-537))
);
let r = Interval::point(2.0 * ETA).sqrt();
let two = Interval::point(2.0).sqrt();
assert_eq!(
(r.inf(), r.sup()),
(two.inf() * 2f64.powi(-537), two.sup() * 2f64.powi(-537))
);
let r = Interval::point(MAX).sqrt();
assert_eq!(r.sup(), r.inf().next_up());
}
#[test]
fn squares_know_about_zero() {
assert_eq!(iv(-2.0, 3.0).square(), iv(0.0, 9.0));
assert_eq!(iv(-3.0, 2.0).square(), iv(0.0, 9.0));
assert_eq!(iv(-3.0, -2.0).square(), iv(4.0, 9.0));
assert_eq!(iv(2.0, 3.0).square(), iv(4.0, 9.0));
assert_eq!(iv(-2.0, 3.0) * iv(-2.0, 3.0), iv(-6.0, 9.0));
}
#[test]
fn the_sign_table_of_the_product() {
let (p, m, n) = (iv(2.0, 3.0), iv(-2.0, 3.0), iv(-3.0, -2.0));
assert_eq!(p * p, iv(4.0, 9.0));
assert_eq!(p * m, iv(-6.0, 9.0));
assert_eq!(p * n, iv(-9.0, -4.0));
assert_eq!(m * p, iv(-6.0, 9.0));
assert_eq!(m * m, iv(-6.0, 9.0));
assert_eq!(m * n, iv(-9.0, 6.0));
assert_eq!(n * p, iv(-9.0, -4.0));
assert_eq!(n * m, iv(-9.0, 6.0));
assert_eq!(n * n, iv(4.0, 9.0));
assert_eq!(iv(-5.0, 1.0) * iv(-1.0, 7.0), iv(-35.0, 7.0));
assert_eq!(p * -2.0, iv(-6.0, -4.0));
assert_eq!(m * 2.0, iv(-4.0, 6.0));
assert_eq!(iv(4.0, 8.0) / iv(2.0, 4.0), iv(1.0, 4.0));
assert_eq!(iv(-8.0, 4.0) / iv(2.0, 4.0), iv(-4.0, 2.0));
assert_eq!(iv(-8.0, -4.0) / iv(2.0, 4.0), iv(-4.0, -1.0));
assert_eq!(iv(4.0, 8.0) / iv(-4.0, -2.0), iv(-4.0, -1.0));
assert_eq!(iv(-8.0, 4.0) / iv(-4.0, -2.0), iv(-2.0, 4.0));
assert_eq!(iv(-8.0, -4.0) / iv(-4.0, -2.0), iv(1.0, 4.0));
assert_eq!(iv(-8.0, 4.0) / -2.0, iv(-2.0, 4.0));
}
#[test]
fn queries() {
let x = iv(-1.0, 3.0);
assert_eq!((x.mid(), x.width(), x.mag(), x.mig()), (1.0, 4.0, 3.0, 0.0));
assert_eq!(iv(2.0, 3.0).mig(), 2.0);
assert_eq!(iv(-3.0, -2.0).mig(), 2.0);
assert_eq!(iv(-3.0, -2.0).mag(), 3.0);
assert_eq!(Interval::ENTIRE.mid(), 0.0);
assert_eq!(iv(1.0, INF).mid(), MAX);
assert_eq!(iv(-INF, 1.0).mid(), -MAX);
assert_eq!(iv(-MAX, MAX).mid(), 0.0);
assert_eq!(iv(MAX, MAX).mid(), MAX);
assert_eq!(iv(1.0, INF).width(), INF);
assert_eq!(iv(-MAX, MAX).width(), INF);
assert_eq!(Interval::ENTIRE.mag(), INF);
assert_eq!(iv(-2f64.powi(-60), 1.0).width(), 1.0_f64.next_up());
assert!(x.contains(-1.0) && x.contains(3.0) && !x.contains(3.5));
assert!(!x.contains(f64::NAN) && !Interval::ENTIRE.contains(INF));
assert!(iv(0.0, 1.0).is_subset_of(x) && !x.is_subset_of(iv(0.0, 1.0)));
assert!(x.is_subset_of(Interval::ENTIRE));
assert!(x.certainly_le(3.0) && !x.certainly_le(2.9));
assert!(x.certainly_ge(-1.0) && !x.certainly_ge(-0.9));
assert!(x.certainly_within(3.0) && !x.certainly_within(2.9));
assert!(!x.certainly_le(f64::NAN) && !x.certainly_ge(f64::NAN));
assert!(!x.certainly_within(f64::NAN) && !x.certainly_within(-5.0));
assert_eq!(x.hull(iv(5.0, 6.0)), iv(-1.0, 6.0));
assert_eq!(x.intersection(iv(2.0, 6.0)), iv(2.0, 3.0));
assert_eq!(x.intersection(iv(3.0, 6.0)), Interval::point(3.0));
assert_eq!(x.abs(), iv(0.0, 3.0));
assert_eq!(iv(-3.0, -1.0).abs(), iv(1.0, 3.0));
assert_eq!(iv(1.0, 3.0).abs(), iv(1.0, 3.0));
}
#[test]
fn display() {
assert_eq!(iv(-1.5, 2.0).to_string(), "[-1.5, 2]");
assert_eq!(Interval::ENTIRE.to_string(), "[-inf, inf]");
assert_eq!(Interval::point(0.1).to_string(), "[0.1, 0.1]");
assert_eq!(format!("{:e}", iv(-1.5, 2000.0)), "[-1.5e0, 2e3]");
assert_eq!(format!("{:e}", Interval::EMPTY), "∅");
assert_eq!(format!("{:.2}", Interval::EMPTY), "∅");
}
#[test]
fn display_with_a_precision_rounds_outward() {
assert_eq!(format!("{:.2}", iv(0.124, 0.126)), "[0.12, 0.13]");
assert_eq!(format!("{:.2}", iv(0.121, 0.129)), "[0.12, 0.13]");
assert_eq!(format!("{:.2}", iv(-0.129, -0.121)), "[-0.13, -0.12]");
assert_eq!(format!("{:.0}", iv(-0.5, 0.5)), "[-1, 1]");
assert_eq!(format!("{:.0}", iv(1.0, 2.0)), "[1, 2]");
assert_eq!(format!("{:.1}", Interval::point(0.1)), "[0.1, 0.2]");
assert_eq!(format!("{:.3}", Interval::point(0.125)), "[0.125, 0.125]");
assert_eq!(format!("{:.1}", iv(9.95, 9.96)), "[9.9, 10.0]");
assert_eq!(format!("{:.1}", iv(-99.99, 99.99)), "[-100.0, 100.0]");
assert_eq!(format!("{:.2}", iv(-0.0, 0.0)), "[-0.00, 0.00]");
assert_eq!(format!("{:.2}", iv(0.0, 0.0)), "[0.00, 0.00]");
assert_eq!(format!("{:+.1}", iv(-1.0, 1.0)), "[-1.0, +1.0]");
assert_eq!(format!("{:.3}", iv(-ETA, ETA)), "[-0.001, 0.001]");
assert_eq!(format!("{:.3}", iv(0.0, ETA)), "[0.000, 0.001]");
assert_eq!(format!("{:.2}", Interval::ENTIRE), "[-inf, inf]");
assert_eq!(format!("{:.1}", iv(1.0, INF)), "[1.0, inf]");
let s = format!("{:.1100}", Interval::point(ETA));
assert_eq!(s, format!("[{ETA:.1100}, {ETA:.1100}]"));
assert_eq!(format!("{:.2e}", iv(1234.0, 5678.0)), "[1.23e3, 5.68e3]");
assert_eq!(
format!("{:.2e}", iv(-5678.0, -1234.0)),
"[-5.68e3, -1.23e3]"
);
assert_eq!(format!("{:.0e}", iv(1.5, 2.5)), "[1e0, 3e0]");
assert_eq!(format!("{:.1e}", iv(0.0996, 9.96)), "[9.9e-2, 1.0e1]");
assert_eq!(format!("{:.1e}", iv(-9.96, -0.0)), "[-1.0e1, -0.0e0]");
assert_eq!(format!("{:.3e}", iv(0.0, 0.0)), "[0.000e0, 0.000e0]");
assert_eq!(format!("{:.2e}", iv(-ETA, ETA)), "[-4.95e-324, 4.95e-324]");
assert_eq!(format!("{:.2e}", iv(-MAX, MAX)), "[-1.80e308, 1.80e308]");
assert_eq!(format!("{:.1e}", Interval::ENTIRE), "[-inf, inf]");
assert_eq!(
format!("{:.3e}", Interval::point(1.0)),
"[1.000e0, 1.000e0]"
);
}
#[test]
fn from_f64_is_total() {
for x in [
0.0,
-0.0,
0.1,
-7.5,
ETA,
-ETA,
MAX,
-MAX,
f64::MIN_POSITIVE,
] {
let (p, f) = (Interval::point(x), Interval::from(x));
assert_eq!(p.inf().to_bits(), f.inf().to_bits(), "{x:e}");
assert_eq!(p.sup().to_bits(), f.sup().to_bits(), "{x:e}");
let g: Interval = x.into();
assert_eq!(g, f);
}
for x in [f64::NAN, INF, -INF] {
assert_eq!(Interval::from(x), Interval::ENTIRE, "{x}");
assert_eq!(Interval::from(x) + iv(1.0, 2.0), x + iv(1.0, 2.0));
}
}
#[test]
fn errors_are_errors() {
let e: Box<dyn core::error::Error> = Box::new(InvalidInterval);
assert!(e.to_string().starts_with("invalid interval"));
}
#[test]
fn operator_forms_agree_bit_for_bit() {
let same = |p: Interval, q: Interval| {
p.inf().to_bits() == q.inf().to_bits() && p.sup().to_bits() == q.sup().to_bits()
};
let xs = [
iv(2.0, 3.0),
iv(-2.0, 3.0),
iv(-3.0, -2.0),
iv(0.0, 0.1),
iv(-0.1, 0.0),
Interval::ZERO,
iv(1.0, INF),
Interval::ENTIRE,
Interval::EMPTY,
];
let ys = [0.1, -0.3, 0.0, 7.0, MAX, ETA, f64::NAN, INF, -INF];
for &x in &xs {
for &z in &xs {
let mut t = x;
t += z;
assert!(same(t, x + z));
t = x;
t -= z;
assert!(same(t, x - z));
t = x;
t *= z;
assert!(same(t, x * z));
t = x;
t /= z;
assert!(same(t, x / z));
}
for &y in &ys {
let mut t = x;
t += y;
assert!(same(t, x + y));
t = x;
t -= y;
assert!(same(t, x - y));
t = x;
t *= y;
assert!(same(t, x * y));
t = x;
t /= y;
assert!(same(t, x / y));
let point = |op: fn(Interval, Interval) -> Interval| {
if x.is_empty() {
Interval::EMPTY
} else if y.is_finite() {
op(Interval::point(y), x)
} else {
Interval::ENTIRE
}
};
assert!(same(y + x, point(|p, q| p + q)), "{y} + {x:?}");
assert!(same(y - x, point(|p, q| p - q)), "{y} - {x:?}");
assert!(same(y * x, point(|p, q| p * q)), "{y} * {x:?}");
assert!(same(y / x, point(|p, q| p / q)), "{y} / {x:?}");
}
}
assert_eq!(1.0 - iv(0.25, 0.5), iv(0.5, 0.75));
assert_eq!(1.0 / iv(2.0, 4.0), iv(0.25, 0.5));
assert_eq!(1.0 / iv(0.0, 4.0), iv(0.25, INF));
assert_eq!(1.0 / iv(-1.0, 1.0), Interval::ENTIRE);
assert_eq!(0.0 / iv(-1.0, 1.0), Interval::ZERO);
}
}