use crate::application::linalg::thresholds;
use crate::domain::real::RealScalar;
pub(crate) fn norm_ratio_log2<T: RealScalar>(values: &[T], largest: T) -> i32 {
let dimension_bound = (thresholds::ceil_log2_count(values.len()) + 1) / 2;
let Some(sum) = RatioSum::of(values, largest) else {
return dimension_bound;
};
let mut k = thresholds::ceil_log2(sum.mantissa);
let power = T::ONE.scale_binary(k);
if sum.mantissa < power && sum.mantissa > power.mul(T::ONE.sub(sum.slack)) {
k += 1;
}
((k + sum.exponent + 1) / 2).min(dimension_bound)
}
pub(crate) fn norm_ratio_floor_log2<T: RealScalar>(values: &[T], largest: T) -> i32 {
RatioSum::of(values, largest).map_or(0, |sum| {
let lower = sum.mantissa.mul(T::ONE.sub(sum.slack.scale_binary(1)));
let bits = lower.binary_exponent().unwrap_or(0) + sum.exponent;
bits.max(0) / 2
})
}
struct RatioSum<T> {
mantissa: T,
exponent: i32,
slack: T,
}
impl<T: RealScalar> RatioSum<T> {
fn of(values: &[T], largest: T) -> Option<Self> {
let log2_len = thresholds::ceil_log2_count(values.len());
let roundings =
usize::try_from(log2_len + 2).expect("invariant: a bit count is non-negative");
let log2_eps = thresholds::ceil_log2(thresholds::machine_epsilon::<T>());
let rounding_log2 = log2_eps - 1 + thresholds::ceil_log2_count(4 * roundings + 4);
let underflow_log2 = thresholds::ceil_log2(thresholds::safe_min::<T>())
+ log2_eps
+ thresholds::ceil_log2_count(4 * values.len());
let slack = T::ONE.scale_binary(rounding_log2.max(underflow_log2) + 1);
if slack.scale_binary(1) >= T::ONE {
return None;
}
let (mantissa, exponent) = pairwise_squares(values, largest);
(mantissa.is_finite() && mantissa > T::ZERO).then_some(Self {
mantissa,
exponent,
slack,
})
}
}
fn pairwise_squares<T: RealScalar>(values: &[T], largest: T) -> (T, i32) {
match values {
[] => (T::ZERO, 0),
[value] => {
let ratio = value.div(largest);
(ratio.mul(ratio), 0)
}
_ => {
let (left, right) = values.split_at(values.len() / 2);
let (a, ka) = pairwise_squares(left, largest);
let (b, kb) = pairwise_squares(right, largest);
let k = ka.max(kb);
let sum = a.scale_binary(ka - k).add(b.scale_binary(kb - k));
if sum >= T::ONE.add(T::ONE) {
(sum.scale_binary(-1), k + 1)
} else {
(sum, k)
}
}
}
}