#![allow(clippy::float_cmp)]
use core::iter::Sum;
use core::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign};
use crate::eft::{fast_two_sum, two_prod, two_sum};
#[derive(Clone, Copy, Debug, Default, PartialEq, PartialOrd)]
#[repr(C)]
pub struct DoubleDouble {
hi: f64,
lo: f64,
}
#[derive(Clone, Copy, Debug, PartialEq)]
#[non_exhaustive]
pub struct ErrorBound {
pub operation: &'static str,
pub units_of_u2: f64,
}
#[inline]
fn finish(zh: f64, zl: f64, g: f64) -> DoubleDouble {
if zh.is_finite() {
DoubleDouble {
hi: zh,
lo: if zl.is_finite() { zl } else { 0.0 },
}
} else if zh.is_nan() || !g.is_finite() {
DoubleDouble { hi: g, lo: 0.0 }
} else {
DoubleDouble { hi: zh, lo: 0.0 }
}
}
#[inline]
fn times_fp1(x: DoubleDouble, y: f64) -> (f64, f64) {
let (ch, cl1) = two_prod(x.hi, y);
let cl2 = x.lo * y;
let (th, tl1) = fast_two_sum(ch, cl2);
let tl2 = tl1 + cl1;
fast_two_sum(th, tl2)
}
#[inline]
fn scale_f64(mut x: f64, k: i32) -> f64 {
const UP: f64 = f64::from_bits((1023 + 1000) << 52);
const DOWN: f64 = f64::from_bits((1023 - 1000) << 52);
let mut k = k.clamp(-2200, 2200);
while k > 1000 {
x *= UP;
k -= 1000;
}
while k < -1000 {
x *= DOWN;
k += 1000;
}
let biased = u64::try_from(1023 + k).expect("|k| <= 1000");
x * f64::from_bits(biased << 52)
}
impl DoubleDouble {
pub const ZERO: Self = Self { hi: 0.0, lo: 0.0 };
pub const ONE: Self = Self { hi: 1.0, lo: 0.0 };
pub const EPSILON: Self = Self {
hi: 4.930_380_657_631_324e-32,
lo: 0.0,
};
pub const INFINITY: Self = Self {
hi: f64::INFINITY,
lo: 0.0,
};
pub const NAN: Self = Self {
hi: f64::NAN,
lo: 0.0,
};
pub const PI: Self = Self {
hi: f64::from_bits(0x4009_21fb_5444_2d18),
lo: f64::from_bits(0x3ca1_a626_3314_5c07),
};
pub const TAU: Self = Self {
hi: f64::from_bits(0x4019_21fb_5444_2d18),
lo: f64::from_bits(0x3cb1_a626_3314_5c07),
};
pub const FRAC_PI_2: Self = Self {
hi: f64::from_bits(0x3ff9_21fb_5444_2d18),
lo: f64::from_bits(0x3c91_a626_3314_5c07),
};
pub const FRAC_PI_3: Self = Self {
hi: f64::from_bits(0x3ff0_c152_382d_7366),
lo: f64::from_bits(0xbc9e_e691_3347_c2a6),
};
pub const FRAC_PI_4: Self = Self {
hi: f64::from_bits(0x3fe9_21fb_5444_2d18),
lo: f64::from_bits(0x3c81_a626_3314_5c07),
};
pub const FRAC_PI_6: Self = Self {
hi: f64::from_bits(0x3fe0_c152_382d_7366),
lo: f64::from_bits(0xbc8e_e691_3347_c2a6),
};
pub const FRAC_PI_8: Self = Self {
hi: f64::from_bits(0x3fd9_21fb_5444_2d18),
lo: f64::from_bits(0x3c71_a626_3314_5c07),
};
pub const FRAC_1_PI: Self = Self {
hi: f64::from_bits(0x3fd4_5f30_6dc9_c883),
lo: f64::from_bits(0xbc76_b01e_c541_7056),
};
pub const FRAC_2_PI: Self = Self {
hi: f64::from_bits(0x3fe4_5f30_6dc9_c883),
lo: f64::from_bits(0xbc86_b01e_c541_7056),
};
pub const FRAC_2_SQRT_PI: Self = Self {
hi: f64::from_bits(0x3ff2_0dd7_5042_9b6d),
lo: f64::from_bits(0x3c71_ae3a_914f_ed80),
};
pub const SQRT_2: Self = Self {
hi: f64::from_bits(0x3ff6_a09e_667f_3bcd),
lo: f64::from_bits(0xbc9b_dd34_13b2_6456),
};
pub const FRAC_1_SQRT_2: Self = Self {
hi: f64::from_bits(0x3fe6_a09e_667f_3bcd),
lo: f64::from_bits(0xbc8b_dd34_13b2_6456),
};
pub const E: Self = Self {
hi: f64::from_bits(0x4005_bf0a_8b14_5769),
lo: f64::from_bits(0x3ca4_d57e_e2b1_013a),
};
pub const LOG2_E: Self = Self {
hi: f64::from_bits(0x3ff7_1547_652b_82fe),
lo: f64::from_bits(0x3c77_77d0_ffda_0d24),
};
pub const LOG2_10: Self = Self {
hi: f64::from_bits(0x400a_934f_0979_a371),
lo: f64::from_bits(0x3ca7_f249_5fb7_fa6d),
};
pub const LOG10_E: Self = Self {
hi: f64::from_bits(0x3fdb_cb7b_1526_e50e),
lo: f64::from_bits(0x3c69_5355_baaa_fad3),
};
pub const LOG10_2: Self = Self {
hi: f64::from_bits(0x3fd3_4413_509f_79ff),
lo: f64::from_bits(0xbc49_dc1d_a994_fd21),
};
pub const LN_2: Self = Self {
hi: f64::from_bits(0x3fe6_2e42_fefa_39ef),
lo: f64::from_bits(0x3c7a_bc9e_3b39_803f),
};
pub const LN_10: Self = Self {
hi: f64::from_bits(0x4002_6bb1_bbb5_5516),
lo: f64::from_bits(0xbcaf_48ad_494e_a3e9),
};
pub const ERROR_BOUNDS: &'static [ErrorBound] = &[
ErrorBound {
operation: "dd + f64",
units_of_u2: f64::from_bits(0x4000_0000_0000_0002),
},
ErrorBound {
operation: "dd + dd",
units_of_u2: f64::from_bits(0x4008_0000_0000_0004),
},
ErrorBound {
operation: "dd · f64",
units_of_u2: 2.0,
},
ErrorBound {
operation: "dd · dd",
units_of_u2: 4.0,
},
ErrorBound {
operation: "dd²",
units_of_u2: 3.0,
},
ErrorBound {
operation: "dd / f64",
units_of_u2: 3.0,
},
ErrorBound {
operation: "dd / dd",
units_of_u2: f64::from_bits(0x402e_0000_0000_0004),
},
ErrorBound {
operation: "√dd",
units_of_u2: 3.125,
},
];
#[must_use]
pub const fn from_f64(x: f64) -> Self {
Self { hi: x, lo: 0.0 }
}
#[inline]
#[must_use]
pub fn from_sum(a: f64, b: f64) -> Self {
let (s, e) = two_sum(a, b);
finish(s, e, s)
}
#[inline]
#[must_use]
pub fn from_product(a: f64, b: f64) -> Self {
let (p, e) = two_prod(a, b);
let (zh, zl) = fast_two_sum(p, e);
finish(zh, zl, p)
}
#[inline]
#[must_use]
pub fn from_parts(hi: f64, lo: f64) -> Self {
let x = Self { hi, lo };
debug_assert!(
x.check_invariants().is_ok(),
"from_parts({hi:e}, {lo:e}): {:?}",
x.check_invariants()
);
x
}
#[inline]
pub(crate) const fn from_raw(hi: f64, lo: f64) -> Self {
Self { hi, lo }
}
#[must_use]
pub const fn hi(self) -> f64 {
self.hi
}
#[must_use]
pub const fn lo(self) -> f64 {
self.lo
}
#[must_use]
pub const fn to_f64(self) -> f64 {
self.hi
}
#[inline]
#[must_use]
pub fn abs(self) -> Self {
if self.hi.is_sign_negative() {
-self
} else {
self
}
}
#[inline]
#[must_use]
pub fn sqrt(self) -> Self {
if self.hi == 0.0 {
return self;
}
let sh = self.hi.sqrt();
let rho1 = (-sh).mul_add(sh, self.hi);
let rho2 = self.lo + rho1;
let sl = rho2 / (2.0 * sh);
let (zh, zl) = fast_two_sum(sh, sl);
finish(zh, zl, sh)
}
#[inline]
#[must_use]
pub fn recip(self) -> Self {
Self::ONE / self
}
#[inline]
#[must_use]
pub fn square(self) -> Self {
let (ch, cl1) = two_prod(self.hi, self.hi);
let c = (2.0 * self.hi).mul_add(self.lo, cl1);
let (zh, zl) = fast_two_sum(ch, c);
finish(zh, zl, ch)
}
#[inline]
#[must_use]
pub fn ldexp(self, k: i32) -> Self {
let h = scale_f64(self.hi, k);
let l = scale_f64(self.lo, k);
let (zh, zl) = fast_two_sum(h, l);
finish(zh, zl, h)
}
#[inline]
#[must_use]
pub fn is_finite(self) -> bool {
self.hi.is_finite()
}
#[inline]
#[must_use]
pub fn is_nan(self) -> bool {
self.hi.is_nan()
}
#[inline]
#[must_use]
pub fn max(self, other: Self) -> Self {
if self.is_nan() || self < other {
other
} else {
self
}
}
#[inline]
#[must_use]
pub fn min(self, other: Self) -> Self {
if self.is_nan() || other < self {
other
} else {
self
}
}
pub fn check_invariants(self) -> Result<(), &'static str> {
if self.hi.is_nan() {
return Ok(());
}
if self.hi.is_infinite() {
return if self.lo == 0.0 {
Ok(())
} else {
Err("D2: an infinite value has a nonzero trailing component")
};
}
if !self.lo.is_finite() {
return Err("D1: a finite value has a non-finite trailing component");
}
if self.hi == 0.0 && self.lo != 0.0 {
return Err("D1: a zero leading component with a nonzero trailing one");
}
if self.hi + self.lo != self.hi {
return Err("D1: the pair is not normalized, hi != fl(hi + lo)");
}
Ok(())
}
}
impl Add for DoubleDouble {
type Output = Self;
#[inline]
fn add(self, rhs: Self) -> Self {
let (sh, sl) = two_sum(self.hi, rhs.hi);
let (th, tl) = two_sum(self.lo, rhs.lo);
let c = sl + th;
let (vh, vl) = fast_two_sum(sh, c);
let w = tl + vl;
let (zh, zl) = fast_two_sum(vh, w);
finish(zh, zl, sh)
}
}
impl Add<f64> for DoubleDouble {
type Output = Self;
#[inline]
fn add(self, rhs: f64) -> Self {
let (sh, sl) = two_sum(self.hi, rhs);
let v = self.lo + sl;
let (zh, zl) = fast_two_sum(sh, v);
finish(zh, zl, sh)
}
}
impl Sub for DoubleDouble {
type Output = Self;
#[inline]
fn sub(self, rhs: Self) -> Self {
self + (-rhs)
}
}
impl Sub<f64> for DoubleDouble {
type Output = Self;
#[inline]
fn sub(self, rhs: f64) -> Self {
self + (-rhs)
}
}
impl Mul for DoubleDouble {
type Output = Self;
#[inline]
fn mul(self, rhs: Self) -> Self {
let (ch, cl1) = two_prod(self.hi, rhs.hi);
let tl0 = self.lo * rhs.lo;
let tl1 = self.hi.mul_add(rhs.lo, tl0);
let cl2 = self.lo.mul_add(rhs.hi, tl1);
let cl3 = cl1 + cl2;
let (zh, zl) = fast_two_sum(ch, cl3);
finish(zh, zl, ch)
}
}
impl Mul<f64> for DoubleDouble {
type Output = Self;
#[inline]
fn mul(self, rhs: f64) -> Self {
let (ch, cl1) = two_prod(self.hi, rhs);
let cl3 = self.lo.mul_add(rhs, cl1);
let (zh, zl) = fast_two_sum(ch, cl3);
finish(zh, zl, ch)
}
}
impl Div for DoubleDouble {
type Output = Self;
#[inline]
fn div(self, rhs: Self) -> Self {
let th = self.hi / rhs.hi;
let (rh, rl) = times_fp1(rhs, th);
let pih = self.hi - rh;
let dl = self.lo - rl;
let d = pih + dl;
let tl = d / rhs.hi;
let (zh, zl) = fast_two_sum(th, tl);
finish(zh, zl, th)
}
}
impl Div<f64> for DoubleDouble {
type Output = Self;
#[inline]
fn div(self, rhs: f64) -> Self {
let th = self.hi / rhs;
let (pih, pil) = two_prod(th, rhs);
let dh = self.hi - pih;
let dt = dh - pil;
let d = dt + self.lo;
let tl = d / rhs;
let (zh, zl) = fast_two_sum(th, tl);
finish(zh, zl, th)
}
}
macro_rules! assign {
($tra:ident, $fa:ident, $op:tt) => {
impl $tra for DoubleDouble {
#[inline]
fn $fa(&mut self, rhs: Self) {
*self = *self $op rhs;
}
}
};
}
assign!(AddAssign, add_assign, +);
assign!(SubAssign, sub_assign, -);
assign!(MulAssign, mul_assign, *);
assign!(DivAssign, div_assign, /);
impl Neg for DoubleDouble {
type Output = Self;
#[inline]
fn neg(self) -> Self {
Self {
hi: -self.hi,
lo: -self.lo,
}
}
}
impl Sum for DoubleDouble {
fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
iter.fold(Self::ZERO, |acc, x| acc + x)
}
}
impl From<f64> for DoubleDouble {
fn from(x: f64) -> Self {
Self::from_f64(x)
}
}
#[cfg(feature = "sparse")]
impl xingo_sparse::Real for DoubleDouble {
const ZERO: Self = Self::ZERO;
const ONE: Self = Self::ONE;
const EPSILON: Self = Self::EPSILON;
#[inline]
fn from_f64(x: f64) -> Self {
Self::from_f64(x)
}
#[inline]
fn to_f64(self) -> f64 {
self.hi
}
#[inline]
fn abs(self) -> Self {
Self::abs(self)
}
#[inline]
fn sqrt(self) -> Self {
Self::sqrt(self)
}
#[inline]
fn recip(self) -> Self {
Self::recip(self)
}
#[inline]
fn mul_add(self, a: Self, b: Self) -> Self {
self * a + b
}
#[inline]
fn is_finite(self) -> bool {
Self::is_finite(self)
}
#[inline]
fn max(self, other: Self) -> Self {
Self::max(self, other)
}
#[inline]
fn min(self, other: Self) -> Self {
Self::min(self, other)
}
}
#[cfg(test)]
#[allow(clippy::disallowed_methods)] mod tests {
use super::*;
const U: f64 = 1.110_223_024_625_156_5e-16; type Dd = DoubleDouble;
fn dd(hi: f64, lo: f64) -> Dd {
Dd::from_parts(hi, lo)
}
#[test]
fn constants() {
assert_eq!(Dd::EPSILON.hi(), 2f64.powi(-104));
assert_eq!(Dd::ZERO + Dd::ONE, Dd::ONE);
assert!(Dd::NAN.is_nan() && !Dd::INFINITY.is_finite());
assert_eq!(Dd::default(), Dd::ZERO);
assert_eq!(Dd::ERROR_BOUNDS.len(), 8);
}
#[test]
fn textbook_cases() {
let tiny = 2f64.powi(-80);
let x = Dd::ONE + tiny;
assert_eq!((x.hi(), x.lo()), (1.0, tiny));
assert_eq!(x - Dd::ONE, Dd::from_f64(tiny));
assert_eq!(x - 1.0, Dd::from_f64(tiny));
let e = 2f64.powi(-30);
assert_eq!(
Dd::from_f64(1.0 + e) * Dd::from_f64(1.0 - e),
dd(1.0, -2f64.powi(-60))
);
assert_eq!(Dd::from_f64(1.0 + e) * (1.0 - e), dd(1.0, -2f64.powi(-60)));
let six = Dd::from_f64(2.0) * Dd::from_f64(3.0);
assert_eq!(six, Dd::from_f64(6.0));
assert_eq!(six / 3.0, Dd::from_f64(2.0));
assert_eq!(six / Dd::from_f64(3.0), Dd::from_f64(2.0));
assert_eq!(Dd::from_f64(9.0).sqrt(), Dd::from_f64(3.0));
assert_eq!(Dd::from_f64(3.0).square(), Dd::from_f64(9.0));
assert_eq!(Dd::from_f64(4.0).recip(), Dd::from_f64(0.25));
let third = Dd::ONE / 3.0;
assert_eq!(third.hi(), 1.0 / 3.0);
assert_eq!(third.lo(), (1.0 / 3.0) * U / 2.0);
assert_eq!(Dd::ONE / Dd::from_f64(3.0), third);
assert_eq!(Dd::from_f64(53.0) / Dd::from_f64(53.0), Dd::ONE);
assert_eq!(third / third, Dd::ONE);
let r = Dd::from_f64(2.0).sqrt();
let err = (r.square() - 2.0).abs();
assert!(err <= Dd::EPSILON * 8.0, "{err:?}");
}
#[test]
fn exact_constructors() {
assert_eq!(Dd::from_sum(1.0, U), dd(1.0, U));
let x = 1.0 + f64::EPSILON;
assert_eq!(
Dd::from_product(x, x),
dd(1.0 + 2.0 * f64::EPSILON, f64::EPSILON * f64::EPSILON)
);
assert_eq!(Dd::from(0.5), Dd::from_f64(0.5));
assert_eq!(Dd::from_f64(0.1).to_f64().to_bits(), 0.1_f64.to_bits());
assert!(Dd::from_sum(f64::MAX, f64::MAX).check_invariants().is_ok());
let b = -3.0 * 2f64.powi(970);
assert!(!two_sum(f64::MAX, b).1.is_finite());
assert_eq!(Dd::from_sum(f64::MAX, b), Dd::from_f64(f64::MAX + b));
assert_eq!(Dd::from_f64(f64::MAX) + b, Dd::from_f64(f64::MAX + b));
assert_eq!(Dd::from_sum(f64::MAX, f64::MAX), Dd::INFINITY);
assert_eq!(Dd::from_product(f64::MAX, -2.0), -Dd::INFINITY);
}
#[test]
fn assignments_and_sum() {
let mut x = Dd::from_f64(1.5);
x += Dd::ONE;
x -= Dd::from_f64(0.5);
x *= Dd::from_f64(4.0);
x /= Dd::from_f64(2.0);
assert_eq!(x, Dd::from_f64(4.0));
let tiny = 2f64.powi(-70);
let s: Dd = [1.0, tiny, -1.0].into_iter().map(Dd::from_f64).sum();
assert_eq!(s, Dd::from_f64(tiny));
assert_eq!(core::iter::empty::<Dd>().sum::<Dd>(), Dd::ZERO);
}
#[test]
fn order_abs_max_min() {
let tiny = 2f64.powi(-80);
let a = Dd::ONE - tiny;
let b = Dd::ONE;
let c = Dd::ONE + tiny;
assert!(a < b && b < c && a < c);
assert!(c > a);
assert_eq!((-c).abs(), c);
assert_eq!(Dd::from_f64(-0.0).abs().hi().to_bits(), 0.0_f64.to_bits());
assert_eq!(a.max(c), c);
assert_eq!(a.min(c), a);
assert_eq!(Dd::NAN.max(a), a);
assert_eq!(a.max(Dd::NAN), a);
assert_eq!(Dd::NAN.min(a), a);
assert_eq!(a.min(Dd::NAN), a);
assert!(Dd::NAN.partial_cmp(&a).is_none());
assert!(-Dd::INFINITY < a && a < Dd::INFINITY);
}
#[test]
fn non_finite_values_follow_ieee() {
let inf = Dd::INFINITY;
let one = Dd::ONE;
assert_eq!(inf + one, inf);
assert_eq!(inf + 1.0, inf);
assert_eq!(one - inf, -inf);
assert!((inf - inf).is_nan());
assert_eq!(inf * one, inf);
assert_eq!(inf * -2.0, -inf);
assert!((inf * Dd::ZERO).is_nan());
assert_eq!(one / Dd::ZERO, inf);
assert_eq!(-one / 0.0, -inf);
assert!((Dd::ZERO / Dd::ZERO).is_nan());
assert_eq!(one / inf, Dd::ZERO);
assert_eq!(one / f64::INFINITY, Dd::ZERO);
assert!((inf / inf).is_nan());
assert_eq!(inf.sqrt(), inf);
assert!((-one).sqrt().is_nan());
assert_eq!(inf.square(), inf);
assert_eq!(Dd::ZERO.recip(), inf);
assert!((Dd::NAN + one).is_nan() && (one * Dd::NAN).is_nan());
assert!((Dd::NAN / one).is_nan() && Dd::NAN.sqrt().is_nan());
let big = Dd::from_f64(f64::MAX);
for z in [
big + big,
big * big,
big / Dd::from_f64(1e-300),
big.square(),
] {
assert_eq!(z, inf);
assert!(z.check_invariants().is_ok());
}
assert_eq!(inf.ldexp(-5), inf);
assert_eq!(big.ldexp(1), inf);
}
#[test]
fn signed_zero_square_roots() {
assert_eq!(Dd::ZERO.sqrt().hi().to_bits(), 0.0_f64.to_bits());
assert_eq!(
Dd::from_f64(-0.0).sqrt().hi().to_bits(),
(-0.0_f64).to_bits()
);
}
#[test]
fn ldexp_is_exact() {
let x = Dd::ONE / 3.0;
let y = x.ldexp(700);
assert_eq!(
(y.hi(), y.lo()),
(x.hi() * 2f64.powi(700), x.lo() * 2f64.powi(700))
);
assert_eq!(y.ldexp(-700), x);
assert_eq!(x.ldexp(1500).ldexp(-1500), Dd::INFINITY);
assert_eq!(x.ldexp(-900).ldexp(900), x);
assert_eq!(x.ldexp(i32::MIN), Dd::ZERO);
assert_eq!(x.ldexp(i32::MAX), Dd::INFINITY);
assert_eq!(Dd::ZERO.ldexp(i32::MAX), Dd::ZERO);
assert!(x.ldexp(-1060).check_invariants().is_ok());
}
#[test]
fn check_invariants_rejects_bad_pairs() {
let bad = |hi, lo| Dd { hi, lo }.check_invariants().is_err();
assert!(bad(1.0, 1.0)); assert!(bad(1.0, f64::EPSILON)); assert!(bad(0.0, 1e-300));
assert!(bad(f64::INFINITY, 1.0));
assert!(bad(1.0, f64::NAN));
assert!(Dd { hi: 1.0, lo: U }.check_invariants().is_ok()); assert!(
Dd {
hi: f64::NAN,
lo: 3.0
}
.check_invariants()
.is_ok()
);
}
#[test]
#[cfg(debug_assertions)]
#[should_panic(expected = "from_parts")]
fn from_parts_asserts_normalization() {
let _ = Dd::from_parts(1.0, 1.0);
}
#[cfg(feature = "sparse")]
#[test]
fn real_is_implemented() {
use xingo_sparse::Real;
fn third<T: Real>() -> T {
T::ONE / T::from_f64(3.0)
}
let t = third::<Dd>();
assert_eq!(t, Dd::ONE / 3.0);
assert_eq!(Real::to_f64(t).to_bits(), (1.0_f64 / 3.0).to_bits());
assert_eq!(<Dd as Real>::EPSILON, Dd::EPSILON);
assert_eq!(
Real::mul_add(t, Dd::from_f64(3.0), Dd::ONE),
t * Dd::from_f64(3.0) + Dd::ONE
);
assert_eq!(Real::abs(-t), t);
assert_eq!(Real::recip(Dd::from_f64(8.0)), Dd::from_f64(0.125));
assert_eq!(Real::sqrt(Dd::from_f64(16.0)), Dd::from_f64(4.0));
assert!(Real::is_finite(t) && !Real::is_finite(Dd::INFINITY));
assert_eq!(Real::max(t, Dd::ONE), Dd::ONE);
assert_eq!(Real::min(t, Dd::ONE), t);
}
}