use crate::domain::real::RealScalar;
const RANK_PIVOT_DENOMINATOR: f64 = 1_000_000_000_000.0;
#[inline]
pub(crate) fn rank_pivot_ratio<T: RealScalar>() -> T {
T::ONE.div(T::from_f64(RANK_PIVOT_DENOMINATOR))
}
pub(crate) fn machine_epsilon<T: RealScalar>() -> T {
let half = T::ONE.div(T::from_count(2));
let mut epsilon = T::ONE;
while T::ONE.add(epsilon.mul(half)) > T::ONE {
epsilon = epsilon.mul(half);
}
epsilon
}
pub(crate) fn safe_min<T: RealScalar>() -> T {
let eps = machine_epsilon::<T>();
let two = T::from_count(2);
let mut candidate = T::ONE;
loop {
let halved = candidate.div(two);
if halved == T::ZERO || halved.add(halved.mul(eps)) == halved {
return candidate;
}
candidate = halved;
}
}
pub(crate) fn overflow_threshold<T: RealScalar>() -> T {
let two = T::from_count(2);
let mut power = T::ONE;
loop {
let next = power.mul(two);
if !next.is_finite() {
return power.mul(two.sub(machine_epsilon::<T>()));
}
power = next;
}
}
#[derive(Clone, Copy)]
enum RootRounding {
NotAbove,
NotBelow,
}
fn root<T: RealScalar>(y: T, degree: u32, rounding: RootRounding) -> T {
debug_assert!(
degree == 1 || degree == 2 || degree == 4,
"root: degree must be 1, 2, or 4"
);
let mut value = y;
let mut remaining = degree;
while remaining > 1 {
value = value.sqrt();
remaining /= 2;
}
if degree == 1 {
return value;
}
let step = value.mul(machine_epsilon::<T>());
match rounding {
RootRounding::NotAbove => value.sub(step),
RootRounding::NotBelow => value.add(step),
}
}
pub(crate) fn homogeneous_safe_range<T: RealScalar>(
degree: u32,
factor_log2: i32,
floor_log2: i32,
) -> Result<(T, T), EmptyRange> {
let smlnum = safe_min::<T>().div(machine_epsilon::<T>());
let root_end = root(smlnum, degree, RootRounding::NotBelow);
let upper = root(
overflow_threshold::<T>().scale_binary(-factor_log2),
degree,
RootRounding::NotAbove,
);
if root_end > upper {
return Err(EmptyRange::Intermediates);
}
let floor_end = smlnum.scale_binary(floor_log2);
if floor_end > upper {
return Err(EmptyRange::DeflationFloor);
}
let lower = if floor_end > root_end {
floor_end
} else {
root_end
};
Ok((lower, upper))
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum EmptyRange {
Intermediates,
DeflationFloor,
}
pub(crate) fn kernel_window<T: RealScalar>(
lower_degree: u32,
upper_degree: u32,
factor_log2: i32,
) -> (T, T) {
(
root(safe_min::<T>(), lower_degree, RootRounding::NotBelow),
root(
overflow_threshold::<T>().scale_binary(-factor_log2),
upper_degree,
RootRounding::NotAbove,
),
)
}
pub(crate) fn ceil_log2<T: RealScalar>(x: T) -> i32 {
let exponent = x.binary_exponent().unwrap_or(0);
if T::ONE.scale_binary(exponent) == x {
exponent
} else {
exponent + 1
}
}
pub(crate) fn deflation_count_log2(k: usize) -> i32 {
(ceil_log2_count(k) + 1) / 2
}
pub(crate) fn ceil_log2_count(n: usize) -> i32 {
let n = n.max(1);
let floor = usize::BITS - 1 - n.leading_zeros();
let floor = i32::try_from(floor).expect("invariant: a bit index fits in i32");
if n.is_power_of_two() {
floor
} else {
floor + 1
}
}
#[cfg(test)]
pub(crate) fn safe_range<T: RealScalar>() -> (T, T) {
homogeneous_safe_range::<T>(2, 0, 0).expect("invariant: degree 2, no bound factor")
}
pub(crate) fn scaled_frobenius<T: RealScalar>(values: &[T]) -> T {
let largest = values.iter().fold(T::ZERO, |acc, &v| {
let magnitude = v.abs();
if magnitude > acc {
magnitude
} else {
acc
}
});
if largest == T::ZERO {
return T::ZERO;
}
let sum = values.iter().fold(T::ZERO, |acc, &v| {
let ratio = v.div(largest);
acc.add(ratio.mul(ratio))
});
largest.mul(sum.sqrt())
}
#[cfg(test)]
mod tests {
use super::{
ceil_log2, ceil_log2_count, homogeneous_safe_range, kernel_window, machine_epsilon,
rank_pivot_ratio, safe_min, safe_range, scaled_frobenius, EmptyRange,
};
use eunomia::{Bf16, F16};
#[test]
fn machine_epsilon_matches_each_format() {
assert_eq!(machine_epsilon::<f64>(), f64::EPSILON);
assert_eq!(machine_epsilon::<f32>(), f32::EPSILON);
assert_eq!(machine_epsilon::<F16>().to_f32(), 2.0_f32.powi(-10));
assert_eq!(machine_epsilon::<Bf16>().to_f32(), 2.0_f32.powi(-7));
}
#[test]
fn safe_min_matches_each_format_smallest_normal() {
assert_eq!(safe_min::<f64>(), f64::MIN_POSITIVE);
assert_eq!(safe_min::<f32>(), f32::MIN_POSITIVE);
assert_eq!(safe_min::<F16>().to_f32(), F16::MIN_POSITIVE.to_f32());
assert_eq!(safe_min::<Bf16>().to_f32(), Bf16::MIN_POSITIVE.to_f32());
}
#[test]
fn safe_range_ends_bound_the_intermediate_on_the_safe_side() {
let (rmin, rmax) = safe_range::<f64>();
let smlnum = f64::MIN_POSITIVE / f64::EPSILON;
assert!(rmin * rmin >= smlnum && rmin * rmin <= smlnum * (1.0 + 4.0 * f64::EPSILON));
assert!(rmax * rmax <= f64::MAX && rmax * rmax >= f64::MAX * (1.0 - 4.0 * f64::EPSILON));
let (rmin, rmax) = safe_range::<F16>();
let (rmin, rmax) = (f64::from(rmin.to_f32()), f64::from(rmax.to_f32()));
let eps = f64::from(2.0_f32.powi(-10));
assert!((0.25..=0.25 * (1.0 + 2.0 * eps)).contains(&rmin), "{rmin}");
assert!(
rmax * rmax <= 65504.0 && rmax >= 255.94 * (1.0 - 2.0 * eps),
"{rmax}"
);
let (rmin4, rmax4) = homogeneous_safe_range::<F16>(2, 4, 0).expect("non-empty");
assert_eq!(f64::from(rmin4.to_f32()), rmin);
assert!(f64::from(rmax4.to_f32()) * f64::from(rmax4.to_f32()) <= 65504.0 / 16.0);
assert_eq!(
homogeneous_safe_range::<F16>(1, 20, 0),
Err(EmptyRange::Intermediates)
);
let (lower, upper) = homogeneous_safe_range::<F16>(1, 19, 0).expect("non-empty");
assert!(lower <= upper);
let (lower, upper) = homogeneous_safe_range::<F16>(1, 12, 7).expect("non-empty");
assert_eq!(lower.to_f32(), 2.0_f32.powi(3));
assert!(lower <= upper);
assert_eq!(
homogeneous_safe_range::<F16>(1, 12, 8),
Err(EmptyRange::DeflationFloor)
);
}
#[test]
fn kernel_window_matches_the_dlartg_thresholds() {
let (low, high) = kernel_window::<f64>(2, 2, 1);
assert!(
low >= 2.0_f64.powi(-511) && low <= 2.0_f64.powi(-511) * (1.0 + 2.0 * f64::EPSILON)
);
assert!(high * high * 2.0 <= f64::MAX);
assert!(high >= (f64::MAX / 2.0).sqrt() * (1.0 - 2.0 * f64::EPSILON));
}
#[test]
fn ceil_log2_rounds_up_to_the_next_power_of_two() {
assert_eq!(ceil_log2(1.0_f64), 0);
assert_eq!(ceil_log2(4.0_f64), 2);
assert_eq!(ceil_log2(4.5_f64), 3);
assert_eq!(ceil_log2_count(1), 0);
assert_eq!(ceil_log2_count(3), 2);
assert_eq!(ceil_log2_count(4), 2);
assert_eq!(ceil_log2_count(5), 3);
}
#[test]
fn scaled_frobenius_survives_the_range_ends() {
let large = [1e30_f32, 1e30, 1e30];
let small = [1e-30_f32, 1e-30, 1e-30];
let root3 = 3.0_f32.sqrt();
assert!((scaled_frobenius(&large) / 1e30 - root3).abs() <= 4.0 * f32::EPSILON);
assert!((scaled_frobenius(&small) / 1e-30 - root3).abs() <= 4.0 * f32::EPSILON);
assert_eq!(scaled_frobenius(&[0.0_f64; 4]), 0.0);
}
#[test]
fn rank_pivot_ratio_matches_floating_point_contract() {
assert_eq!(rank_pivot_ratio::<f64>(), 1.0e-12);
assert_eq!(rank_pivot_ratio::<f32>(), 1.0e-12_f32);
}
}