use super::sign::Sign;
const SPLITTER: f64 = 134_217_729.0;
const SPLIT_OVERFLOW_THRESHOLD: f64 = f64::MAX / SPLITTER;
#[inline]
pub(crate) fn two_sum(a: f64, b: f64) -> (f64, f64) {
let hi = a + b;
let b_virtual = hi - a;
let a_virtual = hi - b_virtual;
let b_round = b - b_virtual;
let a_round = a - a_virtual;
let lo = a_round + b_round;
(hi, lo)
}
#[inline]
fn split(a: f64) -> (f64, f64) {
if a.is_finite() && a.abs() > SPLIT_OVERFLOW_THRESHOLD {
let scale_down = 2f64.powi(-100);
let scale_up = 2f64.powi(100);
let (hi, lo) = split(a * scale_down);
return (hi * scale_up, lo * scale_up);
}
let c = SPLITTER * a;
let a_big = c - a;
let hi = c - a_big;
let lo = a - hi;
(hi, lo)
}
#[inline]
pub(crate) fn two_product(a: f64, b: f64) -> (f64, f64) {
let hi = a * b;
let (a_hi, a_lo) = split(a);
let (b_hi, b_lo) = split(b);
let err1 = hi - (a_hi * b_hi);
let err2 = err1 - (a_lo * b_hi);
let err3 = err2 - (a_hi * b_lo);
let lo = (a_lo * b_lo) - err3;
(hi, lo)
}
pub(crate) fn product_expansion(a: f64, b: f64) -> [f64; 2] {
let (hi, lo) = two_product(a, b);
[lo, hi]
}
pub(crate) fn diff_expansion(a: f64, b: f64) -> [f64; 2] {
let (hi, lo) = two_sum(a, -b);
[lo, hi]
}
const SIGN_ONLY_RESCALE_THRESHOLD: f64 = f64::MAX / 4.0;
const SIGN_ONLY_RESCALE_FACTOR: f64 = 0.25;
pub(crate) fn rescale_for_sign_only<const N: usize>(coords: [f64; N]) -> [f64; N] {
let max_coord = coords.iter().fold(0.0_f64, |acc, &v| acc.max(v.abs()));
if max_coord <= SIGN_ONLY_RESCALE_THRESHOLD {
return coords;
}
coords.map(|v| v * SIGN_ONLY_RESCALE_FACTOR)
}
pub(crate) fn expansion_sum(base: &[f64], addend: &[f64]) -> Vec<f64> {
if base.is_empty() {
return addend.to_vec();
}
if addend.is_empty() {
return base.to_vec();
}
let mut merged = Vec::with_capacity(base.len() + addend.len());
let (mut i, mut j) = (0, 0);
while i < base.len() && j < addend.len() {
if base[i].abs() <= addend[j].abs() {
merged.push(base[i]);
i += 1;
} else {
merged.push(addend[j]);
j += 1;
}
}
merged.extend_from_slice(&base[i..]);
merged.extend_from_slice(&addend[j..]);
let mut result = Vec::with_capacity(merged.len());
let mut q = merged[0];
for &g in &merged[1..] {
let (sum, err) = two_sum(q, g);
result.push(err);
q = sum;
}
result.push(q);
result
}
pub(crate) fn merge_all(mut parts: Vec<Vec<f64>>) -> Vec<f64> {
if parts.is_empty() {
return vec![];
}
while parts.len() > 1 {
let mut next = Vec::with_capacity(parts.len().div_ceil(2));
let mut it = parts.into_iter();
while let Some(a) = it.next() {
match it.next() {
Some(b) => next.push(expansion_sum(&a, &b)),
None => next.push(a),
}
}
parts = next;
}
parts.into_iter().next().unwrap_or_default()
}
pub(crate) fn scale_expansion(e: &[f64], s: f64) -> Vec<f64> {
merge_all(
e.iter()
.map(|&e_i| product_expansion(e_i, s).to_vec())
.collect(),
)
}
pub(crate) fn product_of_expansions(e: &[f64], f: &[f64]) -> Vec<f64> {
merge_all(f.iter().map(|&f_i| scale_expansion(e, f_i)).collect())
}
pub(crate) fn expansion_sign(e: &[f64]) -> Sign {
for &value in e.iter().rev() {
if value != 0.0 {
return Sign::of(value);
}
}
Sign::Zero
}
pub(crate) fn sign_only_expansion_sign(e: &[f64]) -> Sign {
debug_assert!(
e.iter().all(|v| !v.is_nan()),
"sign_only_expansion_sign: NaN component in {e:?}"
);
expansion_sign(e)
}
pub(crate) fn negate(e: &[f64]) -> Vec<f64> {
e.iter().map(|v| -v).collect()
}
pub(crate) fn det3_with_precancel_bound(
p: (f64, f64, f64),
q: (f64, f64, f64),
r: (f64, f64, f64),
) -> (f64, f64) {
let qr_12 = q.1 * r.2;
let qr_21 = q.2 * r.1;
let qr_02 = q.0 * r.2;
let qr_20 = q.2 * r.0;
let qr_01 = q.0 * r.1;
let qr_10 = q.1 * r.0;
let value = p.0 * (qr_12 - qr_21) - p.1 * (qr_02 - qr_20) + p.2 * (qr_01 - qr_10);
let precancel_bound = p.0.abs() * (qr_12.abs() + qr_21.abs())
+ p.1.abs() * (qr_02.abs() + qr_20.abs())
+ p.2.abs() * (qr_01.abs() + qr_10.abs());
(value, precancel_bound)
}
pub(crate) fn det3_exact(
p: (&[f64], &[f64], &[f64]),
q: (&[f64], &[f64], &[f64]),
r: (&[f64], &[f64], &[f64]),
) -> Vec<f64> {
let qr_12 = product_of_expansions(q.1, r.2);
let qr_21 = product_of_expansions(q.2, r.1);
let qr_02 = product_of_expansions(q.0, r.2);
let qr_20 = product_of_expansions(q.2, r.0);
let qr_01 = product_of_expansions(q.0, r.1);
let qr_10 = product_of_expansions(q.1, r.0);
let term0 = product_of_expansions(p.0, &expansion_sum(&qr_12, &negate(&qr_21)));
let term1 = product_of_expansions(p.1, &expansion_sum(&qr_02, &negate(&qr_20)));
let term2 = product_of_expansions(p.2, &expansion_sum(&qr_01, &negate(&qr_10)));
expansion_sum(&expansion_sum(&term0, &negate(&term1)), &term2)
}
#[cfg(test)]
mod tests {
use super::*;
use num_bigint::BigInt;
use num_rational::BigRational;
use num_traits::{Signed, Zero};
fn exact(x: f64) -> BigRational {
assert!(x.is_finite());
if x == 0.0 {
return BigRational::zero();
}
let bits = x.to_bits();
let sign = if (bits >> 63) & 1 == 1 { -1 } else { 1 };
let exponent_bits = ((bits >> 52) & 0x7ff) as i64;
let mantissa_bits = bits & 0xf_ffff_ffff_ffff;
let (mantissa, exponent) = if exponent_bits == 0 {
(mantissa_bits, -1074i64)
} else {
(mantissa_bits | (1 << 52), exponent_bits - 1075)
};
let mantissa = BigInt::from(mantissa) * BigInt::from(sign);
let mant_rat = BigRational::from_integer(mantissa);
if exponent >= 0 {
mant_rat * BigRational::from_integer(BigInt::from(2).pow(exponent as u32))
} else {
mant_rat / BigRational::from_integer(BigInt::from(2).pow((-exponent) as u32))
}
}
fn expansion_exact_sum(e: &[f64]) -> BigRational {
e.iter().fold(BigRational::zero(), |acc, &v| acc + exact(v))
}
fn sample_values() -> Vec<f64> {
vec![
0.0,
-0.0,
1.0,
-1.0,
0.1,
1e-300,
1e300,
1e-16,
core::f64::consts::PI,
123456789.123456,
f64::MIN_POSITIVE,
f64::MIN_POSITIVE * 2.0,
2.0_f64.powi(-1070), -2.0_f64.powi(-1070),
]
}
fn two_product_safe_values() -> Vec<f64> {
vec![
0.0,
-0.0,
1.0,
-1.0,
0.1,
-0.1,
1e-100,
1e100,
-1e-100,
1e-16,
core::f64::consts::PI,
123456789.123456,
]
}
fn two_product_near_subnormal_pairs() -> Vec<(f64, f64)> {
let mut pairs = vec![];
for &s in &[1e-140_f64, -1e-140, 1e-120, -1e-120] {
for &n in &[1.0, -1.0, 0.1, -0.1, core::f64::consts::PI, 2.0, 1e-10] {
pairs.push((s, n));
}
}
pairs
}
#[test]
fn two_sum_is_exact() {
let values = sample_values();
for &a in &values {
for &b in &values {
let (hi, lo) = two_sum(a, b);
let got = exact(hi) + exact(lo);
let want = exact(a) + exact(b);
assert_eq!(got, want, "two_sum({a}, {b}) exactness");
}
}
}
#[test]
fn two_product_is_exact() {
let values = two_product_safe_values();
for &a in &values {
for &b in &values {
let (hi, lo) = two_product(a, b);
let got = exact(hi) + exact(lo);
let want = exact(a) * exact(b);
assert_eq!(got, want, "two_product({a}, {b}) exactness");
}
}
}
#[test]
fn two_product_near_subnormal_operands_stay_exact() {
for (a, b) in two_product_near_subnormal_pairs() {
let (hi, lo) = two_product(a, b);
let got = exact(hi) + exact(lo);
let want = exact(a) * exact(b);
assert_eq!(got, want, "two_product({a}, {b}) exactness");
}
}
#[test]
fn two_product_true_subnormal_operand_does_not_panic() {
for &a in &[
f64::MIN_POSITIVE,
-f64::MIN_POSITIVE,
2.0_f64.powi(-1030),
-2.0_f64.powi(-1030),
] {
for &b in &[1.0_f64, -1.0, 0.1, core::f64::consts::PI] {
let (hi, lo) = two_product(a, b);
assert!(
hi.is_finite() && lo.is_finite(),
"two_product({a}, {b}) produced non-finite output"
);
}
}
}
fn two_product_extreme_ceiling_pairs() -> Vec<(f64, f64)> {
let mut pairs = vec![];
for &huge in &[
2e300_f64,
-2e300,
5e300,
-5e300,
1e304,
-1e304,
4.251746146807175e304,
1e307,
-1e307,
] {
for &ordinary in &[
1.0,
-1.0,
0.1,
-0.1,
core::f64::consts::PI,
2.0,
1e-10,
1e-100,
] {
pairs.push((huge, ordinary));
}
}
pairs
}
#[test]
fn two_product_extreme_ceiling_is_exact() {
for (a, b) in two_product_extreme_ceiling_pairs() {
let (hi, lo) = two_product(a, b);
let got = exact(hi) + exact(lo);
let want = exact(a) * exact(b);
assert_eq!(got, want, "two_product({a}, {b}) exactness");
}
}
#[test]
fn split_near_f64_max_does_not_panic() {
for &a in &[
f64::MAX,
-f64::MAX,
f64::MAX * 0.9999999,
-f64::MAX * 0.9999999,
] {
let (hi, lo) = split(a);
assert!(
!hi.is_nan() && !lo.is_nan(),
"split({a}) produced NaN -- expected at most the documented residual Infinity"
);
for &b in &[1.0_f64, -1.0, 0.1] {
let _ = two_product(a, b);
}
}
}
#[test]
fn rescale_for_sign_only_is_noop_below_threshold() {
let coords = [1.0_f64, -2.5, 1e100, -1e100, 0.0, 42.0];
assert_eq!(rescale_for_sign_only(coords), coords);
}
#[test]
fn rescale_for_sign_only_prevents_two_sum_overflow_above_threshold() {
let coords = [f64::MAX, 0.0, -f64::MAX, 1e-10, 0.0, 1e-10];
let rescaled = rescale_for_sign_only(coords);
for (orig, scaled) in coords.iter().zip(rescaled.iter()) {
assert_eq!(*scaled, orig * SIGN_ONLY_RESCALE_FACTOR);
}
for &x in &rescaled {
for &y in &rescaled {
let (hi, lo) = two_sum(x, -y);
assert!(
hi.is_finite() && lo.is_finite(),
"two_sum({x}, {}) overflowed even after rescale_for_sign_only",
-y
);
}
}
}
#[test]
fn expansion_sum_single_element_injection_preserves_sum() {
let values = sample_values();
let mut e: Vec<f64> = vec![];
for (i, &b) in values.iter().enumerate() {
e = expansion_sum(&e, &[b]);
assert_eq!(e.len(), i + 1);
}
let expected: BigRational = values
.iter()
.fold(BigRational::zero(), |acc, &v| acc + exact(v));
assert_eq!(expansion_exact_sum(&e), expected);
}
#[test]
fn expansion_sum_merges_two_expansions() {
let a = product_expansion(123.456, 789.012);
let b = product_expansion(-0.001, 999999.999);
let merged = expansion_sum(&a, &b);
let expected = exact(123.456) * exact(789.012) + exact(-0.001) * exact(999999.999);
assert_eq!(expansion_exact_sum(&merged), expected);
}
#[test]
fn scale_expansion_is_exact() {
let pair = product_expansion(123.456, -789.012);
let pair_exact = exact(123.456) * exact(-789.012);
for &s in &[2.0_f64, -3.5, 0.001, 1e10, 1e-10, core::f64::consts::PI] {
let scaled = scale_expansion(&pair, s);
let expected = pair_exact.clone() * exact(s);
assert_eq!(
expansion_exact_sum(&scaled),
expected,
"scale_expansion(pair, {s})"
);
}
}
#[test]
fn diff_expansion_is_exact() {
let pairs = [
(123.456, -789.012),
(2.0_f64.powi(60), 1.0),
(2.0_f64.powi(60), 3.0),
(-2.0_f64.powi(55), 7.0),
(0.0, 0.0),
(5.0, 5.0),
];
for (a, b) in pairs {
let diff = diff_expansion(a, b);
let expected = exact(a) - exact(b);
assert_eq!(
expansion_exact_sum(&diff),
expected,
"diff_expansion({a}, {b})"
);
}
}
#[test]
fn product_of_expansions_is_exact() {
let e = diff_expansion(2.0_f64.powi(60), 1.0); let f = diff_expansion(3.0, 2.0_f64.powi(55)); let product = product_of_expansions(&e, &f);
let expected =
(exact(2.0_f64.powi(60)) - exact(1.0)) * (exact(3.0) - exact(2.0_f64.powi(55)));
assert_eq!(expansion_exact_sum(&product), expected);
}
#[test]
fn sign_matches_leading_term() {
let pairs = [
(1.0, 1.0),
(-1.0, 1.0),
(1e16, 1.0),
(1e-16, 1.0),
(123456789.123456, 0.1),
(-123456789.123456, 0.1),
];
let mut e: Vec<f64> = vec![];
for &(a, b) in &pairs {
e = expansion_sum(&e, &product_expansion(a, b));
let exact_sum = expansion_exact_sum(&e);
let want = if exact_sum.is_positive() {
Sign::Positive
} else if exact_sum.is_negative() {
Sign::Negative
} else {
Sign::Zero
};
assert_eq!(
expansion_sign(&e),
want,
"expansion {e:?} exact_sum {exact_sum}"
);
}
}
}