mod quantile;
mod rng;
pub(crate) use quantile::{QuantileRule, quantile_sorted, sort_for_quantiles};
#[expect(
unused_imports,
reason = "weighted binning is the first consumer; it removes this"
)]
pub(crate) use quantile::{
WeightedQuantileRule, sort_weighted_for_quantiles, weighted_quantile_sorted,
};
pub(crate) use rng::{OwnedRng, derive_repetition_seed, derive_tree_seed};
pub(crate) fn sigmoid_f64(value: f64) -> f64 {
if value >= 0.0 {
1.0 / (1.0 + (-value).exp())
} else {
let exp = value.exp();
exp / (1.0 + exp)
}
}
pub(crate) fn sigmoid_f32(value: f32) -> f32 {
if value >= 0.0 {
1.0 / (1.0 + (-value).exp())
} else {
let exp = value.exp();
exp / (1.0 + exp)
}
}
#[inline]
pub(crate) fn sum_in_order(terms: impl IntoIterator<Item = f64>) -> f64 {
terms
.into_iter()
.fold(-0.0, |total, term: f64| total + term)
}
pub(crate) fn log_sum_exp(values: &[f64]) -> f64 {
let mut max = f64::NEG_INFINITY;
for &value in values {
if value.is_nan() {
return f64::NAN;
}
if value > max {
max = value;
}
}
if !max.is_finite() {
return max;
}
let mut total = 0.0_f64;
for &value in values {
total += (value - max).exp();
}
max + total.ln()
}
pub(crate) fn softmax_in_place(row: &mut [f64]) {
if row.is_empty() {
return;
}
let mut max = f64::NEG_INFINITY;
for &value in row.iter() {
if value.is_nan() {
row.fill(f64::NAN);
return;
}
if value > max {
max = value;
}
}
if !max.is_finite() {
let winners = if max == f64::INFINITY {
row.iter().filter(|value| **value == f64::INFINITY).count()
} else {
row.len()
};
let share = 1.0 / winners as f64;
for value in row.iter_mut() {
*value = if max == f64::INFINITY && *value != f64::INFINITY {
0.0
} else {
share
};
}
return;
}
let mut total = 0.0_f64;
for value in row.iter_mut() {
*value = (*value - max).exp();
total += *value;
}
for value in row {
*value /= total;
}
}
pub(crate) fn softmax_in_place_f32(row: &mut [f32]) {
if row.is_empty() {
return;
}
let mut max = f32::NEG_INFINITY;
for &value in row.iter() {
if value.is_nan() {
row.fill(f32::NAN);
return;
}
if value > max {
max = value;
}
}
if !max.is_finite() {
let winners = if max == f32::INFINITY {
row.iter().filter(|value| **value == f32::INFINITY).count()
} else {
row.len()
};
let share = 1.0 / winners as f32;
for value in row.iter_mut() {
*value = if max == f32::INFINITY && *value != f32::INFINITY {
0.0
} else {
share
};
}
return;
}
let mut total = 0.0_f32;
for value in row.iter_mut() {
*value = (*value - max).exp();
total += *value;
}
for value in row {
*value /= total;
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn sigmoid_saturates_exactly_at_extreme_magnitudes_in_both_signs() {
for &value in &[1.0e3_f64, 1.0e30, 1.0e300, f64::MAX] {
assert_eq!(sigmoid_f64(value), 1.0);
assert_eq!(sigmoid_f64(-value), 0.0);
}
for &value in &[1.0e3_f32, 1.0e30, f32::MAX] {
assert_eq!(sigmoid_f32(value), 1.0);
assert_eq!(sigmoid_f32(-value), 0.0);
}
assert_eq!(sigmoid_f64(0.0), 0.5);
assert_eq!(sigmoid_f32(0.0), 0.5);
}
#[test]
fn sigmoid_is_finite_in_range_and_monotone_non_decreasing() {
let mut previous_f64 = 0.0_f64;
let mut previous_f32 = 0.0_f32;
for step in -2_000..=2_000 {
let value = f64::from(step) / 20.0;
let probability = sigmoid_f64(value);
assert!((0.0..=1.0).contains(&probability), "f64 range at {value}");
assert!(probability >= previous_f64, "f64 monotonicity at {value}");
previous_f64 = probability;
let value = value as f32;
let probability = sigmoid_f32(value);
assert!((0.0..=1.0).contains(&probability), "f32 range at {value}");
assert!(probability >= previous_f32, "f32 monotonicity at {value}");
previous_f32 = probability;
}
assert_eq!(previous_f64, 1.0);
assert_eq!(previous_f32, 1.0);
}
#[test]
fn sigmoid_reflects_around_one_half_and_agrees_across_widths() {
for step in -400..=400 {
let value = f64::from(step) / 8.0;
let wide = sigmoid_f64(value);
assert!(
(wide + sigmoid_f64(-value) - 1.0).abs() <= 1.0e-15,
"f64 reflection at {value}"
);
let narrow = sigmoid_f32(value as f32);
assert!(
(f64::from(narrow) - wide).abs() <= 1.0e-6,
"width agreement at {value}: {narrow} vs {wide}"
);
}
}
#[test]
fn sigmoid_reaches_exact_zero_and_one_only_past_the_representable_boundary() {
assert!(sigmoid_f64(36.7) < 1.0, "f64 saturates to one too early");
assert_eq!(sigmoid_f64(36.8), 1.0, "f64 saturates to one too late");
assert!(sigmoid_f64(-745.1) > 0.0, "f64 saturates to zero too early");
assert_eq!(sigmoid_f64(-745.2), 0.0, "f64 saturates to zero too late");
assert!(sigmoid_f32(16.6) < 1.0, "f32 saturates to one too early");
assert_eq!(sigmoid_f32(16.7), 1.0, "f32 saturates to one too late");
assert!(sigmoid_f32(-103.9) > 0.0, "f32 saturates to zero too early");
assert_eq!(sigmoid_f32(-104.0), 0.0, "f32 saturates to zero too late");
assert_eq!(1.0 - sigmoid_f64(36.8), 0.0);
assert_eq!(1.0 - sigmoid_f32(16.7), 0.0);
}
#[test]
fn sum_in_order_matches_a_sequential_fold_at_every_iterator_shape() {
let mut terms = vec![1.0e16_f64];
terms.extend((0..1_000).map(|step| f64::from(step) * 0.1 - 37.5));
let expected = terms
.iter()
.copied()
.fold(-0.0_f64, |total, term| total + term);
let mut draining = terms.iter().copied();
let shapes: [(&str, f64); 4] = [
("borrowed", sum_in_order(terms.iter().copied())),
("owned", sum_in_order(terms.clone())),
(
"chained",
sum_in_order(terms[..377].iter().chain(&terms[377..]).copied()),
),
(
"unhinted",
sum_in_order(std::iter::from_fn(move || draining.next())),
),
];
for (shape, total) in shapes {
assert_eq!(
total.to_bits(),
expected.to_bits(),
"the {shape} iterator did not reduce as a sequential fold"
);
}
}
#[test]
fn sum_in_order_is_a_bit_for_bit_substitute_for_the_standard_sum() {
let cases: [Vec<f64>; 7] = [
vec![],
vec![-0.0],
vec![-0.0; 8],
vec![0.0; 8],
vec![0.0, -0.0],
vec![-0.0, 0.0],
vec![1.0, -1.0, 2.5, -2.5],
];
for terms in &cases {
assert_eq!(
sum_in_order(terms.iter().copied()).to_bits(),
terms.iter().copied().sum::<f64>().to_bits(),
"sum of {terms:?}"
);
}
assert!(sum_in_order(std::iter::empty()).is_sign_negative());
assert_eq!(sum_in_order(std::iter::empty()), 0.0);
}
#[test]
fn sum_in_order_is_order_sensitive_rather_than_reassociating() {
let ascending = [1.0_f64, 1.0e16, -1.0e16];
let descending = [1.0e16_f64, -1.0e16, 1.0];
assert_eq!(sum_in_order(ascending), 0.0);
assert_eq!(sum_in_order(descending), 1.0);
}
#[test]
fn sum_in_order_accumulates_in_f64_rather_than_the_term_width() {
let terms = [1.0_f32, f32::EPSILON / 2.0, f32::EPSILON / 2.0];
let widened = sum_in_order(terms.iter().map(|&term| f64::from(term)));
assert_eq!(
widened.to_bits(),
(1.0 + f64::from(f32::EPSILON)).to_bits(),
"both half-epsilon terms have to survive the accumulation, exactly"
);
let narrow = terms.iter().fold(0.0_f32, |total, &term| total + term);
assert_eq!(narrow, 1.0, "an f32 accumulation drops both of them");
assert_ne!(
widened as f32, narrow,
"the widening has to still be visible after narrowing back, or the \
fitted value it feeds would be the f32 one"
);
}
fn naive_log_sum_exp(values: &[f64]) -> f64 {
values.iter().map(|value| value.exp()).sum::<f64>().ln()
}
#[test]
fn log_sum_exp_agrees_with_the_naive_formulation_in_its_safe_range() {
for left in -30..=30 {
for right in -30..=30 {
let values = [f64::from(left) / 2.0, f64::from(right) / 2.0];
let stable = log_sum_exp(&values);
let naive = naive_log_sum_exp(&values);
assert!(
(stable - naive).abs() <= 1.0e-12 * naive.abs().max(1.0),
"log_sum_exp{values:?}: {stable} vs {naive}"
);
}
}
}
#[test]
fn log_sum_exp_survives_extreme_magnitudes_in_both_signs() {
for &magnitude in &[300.0_f64, 750.0, 1.0e5, 1.0e300] {
for &value in &[magnitude, -magnitude] {
let doubled = log_sum_exp(&[value, value]);
assert!(
(doubled - (value + std::f64::consts::LN_2)).abs()
<= 1.0e-12 * value.abs().max(1.0),
"log_sum_exp of a repeated {value}: {doubled}"
);
}
if magnitude > 750.0 {
assert!(
!naive_log_sum_exp(&[magnitude, magnitude]).is_finite(),
"naive formulation unexpectedly survived +{magnitude}"
);
assert!(
!naive_log_sum_exp(&[-magnitude, -magnitude]).is_finite(),
"naive formulation unexpectedly survived -{magnitude}"
);
}
}
assert!(!naive_log_sum_exp(&[710.0, 710.0]).is_finite());
assert!(!naive_log_sum_exp(&[-746.0, -746.0]).is_finite());
assert!((log_sum_exp(&[710.0, 710.0]) - (710.0 + std::f64::consts::LN_2)).abs() <= 1.0e-9);
assert!(
(log_sum_exp(&[-746.0, -746.0]) - (-746.0 + std::f64::consts::LN_2)).abs() <= 1.0e-9
);
}
#[test]
fn log_sum_exp_dominated_by_one_term_returns_that_term() {
for &value in &[0.0_f64, 50.0, -50.0, 1.0e6, -1.0e6] {
assert_eq!(log_sum_exp(&[value]), value);
assert_eq!(log_sum_exp(&[value, value - 1.0e6]), value);
}
assert_eq!(log_sum_exp(&[0.0, 0.0]), std::f64::consts::LN_2);
}
#[test]
fn log_sum_exp_boundary_inputs_are_exact() {
assert_eq!(log_sum_exp(&[]), f64::NEG_INFINITY);
assert_eq!(
log_sum_exp(&[f64::NEG_INFINITY, f64::NEG_INFINITY]),
f64::NEG_INFINITY
);
assert_eq!(log_sum_exp(&[f64::NEG_INFINITY, 2.0]), 2.0);
assert_eq!(log_sum_exp(&[f64::INFINITY, 0.0]), f64::INFINITY);
assert!(log_sum_exp(&[f64::NAN, 0.0]).is_nan());
assert!(log_sum_exp(&[0.0, f64::NAN]).is_nan());
}
fn naive_softmax(values: &[f64]) -> Vec<f64> {
let total = values.iter().map(|value| value.exp()).sum::<f64>();
values.iter().map(|value| value.exp() / total).collect()
}
fn softmax(values: &[f64]) -> Vec<f64> {
let mut row = values.to_vec();
softmax_in_place(&mut row);
row
}
#[test]
fn softmax_agrees_with_the_naive_formulation_where_the_naive_one_is_safe() {
for left in -30..=30 {
for right in -30..=30 {
for third in [-4, 0, 7] {
let values = [
f64::from(left) / 2.0,
f64::from(right) / 2.0,
f64::from(third),
];
let stable = softmax(&values);
let naive = naive_softmax(&values);
for (index, (stable, naive)) in stable.iter().zip(&naive).enumerate() {
assert!(
(stable - naive).abs() <= 1.0e-14,
"softmax{values:?}[{index}]: {stable} vs {naive}"
);
}
}
}
}
}
#[test]
fn softmax_survives_extreme_magnitudes_in_both_signs() {
for &magnitude in &[300.0_f64, 750.0, 1.0e5, 1.0e300] {
for &sign in &[1.0_f64, -1.0] {
let base = sign * magnitude;
let uniform = softmax(&[base, base, base]);
for value in &uniform {
assert!(
(value - 1.0 / 3.0).abs() <= 1.0e-15,
"equal scores at {base} must be uniform, got {uniform:?}"
);
}
let gap = 1.0e4_f64.max(base.abs() * 1.0e-6);
let dominated = softmax(&[base, base - gap]);
assert_eq!(dominated, vec![1.0, 0.0], "dominant entry at {base}");
}
if magnitude > 750.0 {
let naive = naive_softmax(&[magnitude, magnitude, magnitude]);
assert!(
naive.iter().any(|value| !value.is_finite()),
"naive formulation unexpectedly survived +{magnitude}"
);
let naive = naive_softmax(&[-magnitude, -magnitude, -magnitude]);
assert!(
naive.iter().any(|value| !value.is_finite()),
"naive formulation unexpectedly survived -{magnitude}"
);
}
}
assert!(naive_softmax(&[710.0, 710.0])[0].is_nan());
assert!(naive_softmax(&[-746.0, -746.0])[0].is_nan());
assert_eq!(softmax(&[710.0, 710.0]), vec![0.5, 0.5]);
assert_eq!(softmax(&[-746.0, -746.0]), vec![0.5, 0.5]);
}
#[test]
fn softmax_stays_in_range_and_is_shift_invariant() {
let base = [-2.5_f64, 0.0, 1.25, 7.0, -13.0];
let reference = softmax(&base);
assert!(reference.iter().all(|value| (0.0..=1.0).contains(value)));
for shift in [-500.0_f64, -1.0, 0.0, 1.0, 500.0] {
let shifted = base.iter().map(|value| value + shift).collect::<Vec<_>>();
for (index, (shifted, reference)) in
softmax(&shifted).iter().zip(&reference).enumerate()
{
assert!(
(shifted - reference).abs() <= 1.0e-15,
"shift {shift} changed column {index}: {shifted} vs {reference}"
);
}
}
for width in 1..=8 {
let uniform = softmax(&vec![3.5_f64; width]);
assert!(uniform.iter().all(|&value| value == 1.0 / width as f64));
}
}
#[test]
fn softmax_rows_are_not_renormalized_and_may_miss_one_by_rounding() {
let mut worst = 0.0_f64;
let mut inexact = 0_usize;
for step in -400..=400 {
let value = f64::from(step) / 7.0;
let row = softmax(&[value, -value, value / 3.0, 0.0, 1.0 - value]);
let deviation = (row.iter().sum::<f64>() - 1.0).abs();
worst = worst.max(deviation);
inexact += usize::from(row.iter().sum::<f64>() != 1.0);
}
assert!(worst <= 8.0 * f64::EPSILON, "row-sum deviation {worst}");
assert!(inexact > 0, "the residual is real, not hypothetical");
}
#[test]
fn softmax_boundary_inputs_are_exact() {
let mut empty: [f64; 0] = [];
softmax_in_place(&mut empty);
assert_eq!(softmax(&[7.5]), vec![1.0]);
assert!(softmax(&[f64::NAN, 0.0]).iter().all(|value| value.is_nan()));
assert!(softmax(&[0.0, f64::NAN]).iter().all(|value| value.is_nan()));
assert_eq!(
softmax(&[f64::INFINITY, 0.0, f64::INFINITY]),
vec![0.5, 0.0, 0.5]
);
assert_eq!(softmax(&[f64::INFINITY, 3.0]), vec![1.0, 0.0]);
assert_eq!(
softmax(&[f64::NEG_INFINITY, f64::NEG_INFINITY]),
vec![0.5, 0.5]
);
assert_eq!(softmax(&[f64::NEG_INFINITY, 2.0]), vec![0.0, 1.0]);
}
#[test]
fn softmax_agrees_with_the_sigmoid_on_two_centred_scores() {
for step in -600..=600 {
let raw = f64::from(step) / 20.0;
let row = softmax(&[-raw / 2.0, raw / 2.0]);
assert!(
(row[1] - sigmoid_f64(raw)).abs() <= 1.0e-15,
"centred pair at {raw}: {} vs {}",
row[1],
sigmoid_f64(raw)
);
}
}
fn softmax_f32(values: &[f32]) -> Vec<f32> {
let mut row = values.to_vec();
softmax_in_place_f32(&mut row);
row
}
#[test]
fn softmax_agrees_across_widths_and_keeps_its_boundaries_at_f32() {
for step in -600..=600 {
let raw = f64::from(step) / 20.0;
let wide = softmax(&[raw, -raw / 3.0, 0.5]);
let narrow = softmax_f32(&[raw as f32, (-raw / 3.0) as f32, 0.5]);
for (index, (narrow, wide)) in narrow.iter().zip(&wide).enumerate() {
assert!(
(f64::from(*narrow) - wide).abs() <= 1.0e-6,
"width agreement at {raw} column {index}: {narrow} vs {wide}"
);
}
}
for &magnitude in &[50.0_f32, 100.0, 1.0e10, f32::MAX] {
for &sign in &[1.0_f32, -1.0] {
let base = sign * magnitude;
let uniform = softmax_f32(&[base, base, base]);
assert!(
uniform
.iter()
.all(|value| (value - 1.0 / 3.0).abs() <= 1.0e-7),
"equal scores at {base} must be uniform, got {uniform:?}"
);
}
}
assert!(
(f32::MAX.exp() / (f32::MAX.exp() + f32::MAX.exp())).is_nan(),
"the naive f32 quotient really does fail at this magnitude"
);
assert_eq!(softmax_f32(&[90.0, 90.0]), vec![0.5, 0.5]);
assert_eq!(softmax_f32(&[-110.0, -110.0]), vec![0.5, 0.5]);
assert!(softmax_f32(&[f32::NAN, 0.0]).iter().all(|v| v.is_nan()));
assert_eq!(softmax_f32(&[f32::INFINITY, 0.0]), vec![1.0, 0.0]);
assert!(
softmax_f32(&[1.0, 2.0, 3.0])
.iter()
.all(|&value| (0.0..=1.0).contains(&value))
);
}
#[test]
fn softmax_f32_boundary_inputs_are_exact() {
let mut empty: [f32; 0] = [];
softmax_in_place_f32(&mut empty);
assert_eq!(softmax_f32(&[7.5]), vec![1.0]);
assert!(
softmax_f32(&[f32::NAN, 0.0])
.iter()
.all(|value| value.is_nan())
);
assert!(
softmax_f32(&[0.0, f32::NAN])
.iter()
.all(|value| value.is_nan())
);
assert_eq!(
softmax_f32(&[f32::INFINITY, 0.0, f32::INFINITY]),
vec![0.5, 0.0, 0.5]
);
assert_eq!(softmax_f32(&[f32::INFINITY, 3.0]), vec![1.0, 0.0]);
assert_eq!(
softmax_f32(&[f32::NEG_INFINITY, f32::NEG_INFINITY]),
vec![0.5, 0.5]
);
assert_eq!(softmax_f32(&[f32::NEG_INFINITY, 2.0]), vec![0.0, 1.0]);
let third = 1.0_f32 / 3.0;
assert_eq!(
softmax_f32(&[f32::INFINITY, 0.0, f32::INFINITY, f32::INFINITY]),
vec![third, 0.0, third, third]
);
assert_eq!(
softmax_f32(&[f32::NEG_INFINITY; 4]),
vec![0.25, 0.25, 0.25, 0.25]
);
}
#[test]
fn softmax_f32_rows_are_not_renormalized_and_may_miss_one_by_rounding() {
let mut rows = Vec::new();
for divisor in [7.0_f32, 50.0] {
for step in -400..=400 {
let value = step as f32 / divisor;
rows.push([value, -value, value / 3.0, 0.0, 1.0 - value]);
}
}
let mut worst = 0.0_f32;
let mut inexact = 0_usize;
for scores in &rows {
let row = softmax_f32(scores);
let sum = row.iter().sum::<f32>();
worst = worst.max((sum - 1.0).abs());
inexact += usize::from(sum != 1.0);
}
assert!(worst <= 8.0 * f32::EPSILON, "row-sum deviation {worst}");
assert!(
inexact * 8 >= rows.len(),
"only {inexact} of {} rows kept a division residual; a renormalized \
row sums to exactly one, so a low rate is the shape of a second pass",
rows.len()
);
fn fix_up_last(row: &[f32]) -> Vec<f32> {
let mut row = row.to_vec();
let last = row.len() - 1;
let residual = 1.0 - row.iter().sum::<f32>();
row[last] += residual;
row
}
let mut residual_pairs = 0_usize;
let mut fixup_asymmetries = 0_usize;
for step in -400..=400 {
let scores = [step as f32 / 50.0, 1.0 - step as f32 / 150.0];
let forward = softmax_f32(&scores);
let swapped = softmax_f32(&[scores[1], scores[0]]);
let reversed = swapped.iter().rev().copied().collect::<Vec<_>>();
assert_eq!(
forward, reversed,
"reversing the scores {scores:?} did not reverse the row"
);
residual_pairs += usize::from(forward.iter().sum::<f32>() != 1.0);
let fixed_reversed = fix_up_last(&swapped)
.iter()
.rev()
.copied()
.collect::<Vec<_>>();
fixup_asymmetries += usize::from(fix_up_last(&forward) != fixed_reversed);
}
assert!(
residual_pairs > 0,
"no two-element row missed one, so the symmetry above was free"
);
assert!(
fixup_asymmetries > 0,
"fixing up the last element left every reversed pair equal, so the \
symmetry above does not discriminate against renormalization"
);
}
#[test]
fn log_sum_exp_is_monotone_in_each_argument() {
let mut previous = f64::NEG_INFINITY;
let mut ascents = 0_usize;
for step in -1_000..=1_000 {
let value = log_sum_exp(&[0.0, f64::from(step) / 10.0]);
assert!(value >= previous, "monotonicity at step {step}");
assert!(value >= 0.0, "softplus stays non-negative at step {step}");
ascents += usize::from(previous.is_finite() && value > previous);
previous = value;
}
assert!(
ascents > 0,
"the sweep never rose, so monotonicity was free"
);
assert_eq!(log_sum_exp(&[0.0, -100.0]), 0.0);
assert_eq!(previous, 100.0);
}
}