#[derive(Copy, Clone, Debug, Default)]
pub struct KahanSum {
sum: f64,
c: f64,
}
impl KahanSum {
pub fn new() -> Self {
Self { sum: 0.0, c: 0.0 }
}
#[inline]
pub fn add(&mut self, x: f64) {
let y = x - self.c;
let t = self.sum + y;
self.c = (t - self.sum) - y;
self.sum = t;
}
#[inline]
pub fn finish(self) -> f64 {
self.sum
}
#[inline]
pub fn value(&self) -> f64 {
self.sum
}
}
#[derive(Copy, Clone, Debug, Default)]
pub struct NeumaierSum {
sum: f64,
c: f64,
}
impl NeumaierSum {
pub fn new() -> Self {
Self { sum: 0.0, c: 0.0 }
}
#[inline]
pub fn add(&mut self, x: f64) {
let t = self.sum + x;
if self.sum.abs() >= x.abs() {
self.c += (self.sum - t) + x;
} else {
self.c += (x - t) + self.sum;
}
self.sum = t;
}
#[inline]
pub fn finish(self) -> f64 {
self.sum + self.c
}
#[inline]
pub fn value(&self) -> f64 {
self.sum + self.c
}
}
pub fn kahan_sum<I: IntoIterator<Item = f64>>(iter: I) -> f64 {
let mut k = KahanSum::new();
for x in iter {
k.add(x);
}
k.finish()
}
pub fn neumaier_sum<I: IntoIterator<Item = f64>>(iter: I) -> f64 {
let mut n = NeumaierSum::new();
for x in iter {
n.add(x);
}
n.finish()
}
pub fn compensated_mean<I: IntoIterator<Item = f64>>(iter: I) -> f64 {
let mut n = 0usize;
let mut acc = NeumaierSum::new();
for x in iter {
acc.add(x);
n += 1;
}
if n == 0 {
return f64::NAN;
}
acc.finish() / n as f64
}
pub fn compensated_dot(x: &[f64], y: &[f64]) -> f64 {
assert_eq!(
x.len(),
y.len(),
"compensated_dot: shape mismatch ({} vs {})",
x.len(),
y.len()
);
let mut acc = NeumaierSum::new();
for i in 0..x.len() {
acc.add(x[i] * y[i]);
}
acc.finish()
}
pub fn compensated_mean_and_var<I: IntoIterator<Item = f64>>(iter: I) -> (f64, f64) {
let mut n = 0usize;
let mut mean = 0.0_f64;
let mut m2 = 0.0_f64;
for x in iter {
n += 1;
let delta = x - mean;
mean += delta / n as f64;
let delta2 = x - mean;
m2 += delta * delta2;
}
match n {
0 => (f64::NAN, f64::NAN),
1 => (mean, 0.0),
_ => (mean, m2 / (n as f64 - 1.0)),
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn neumaier_beats_naive_on_the_kahan_torture_sequence() {
let terms = [1.0_f64, 1e100, 1.0, -1e100];
let naive: f64 = terms.iter().sum();
assert!((naive - 2.0).abs() > 0.5, "naive sum should be badly wrong");
assert_eq!(neumaier_sum(terms), 2.0);
}
#[test]
fn compensated_mean_matches_naive_on_well_scaled_data() {
let xs: Vec<f64> = (1..=1000).map(|i| i as f64).collect();
let naive_mean: f64 = xs.iter().sum::<f64>() / xs.len() as f64;
assert_eq!(compensated_mean(xs.iter().copied()), naive_mean);
}
#[test]
fn welford_matches_two_pass_variance() {
let xs = [4.0_f64, 7.0, 13.0, 16.0];
let (mean, var) = compensated_mean_and_var(xs.iter().copied());
assert!((mean - 10.0).abs() < 1e-12);
let mu: f64 = xs.iter().sum::<f64>() / xs.len() as f64;
let ref_var: f64 = xs.iter().map(|v| (v - mu).powi(2)).sum::<f64>() / 3.0;
assert!((var - ref_var).abs() < 1e-12);
}
#[test]
fn compensated_dot_reduces_to_the_expected_scalar() {
let a = [1.0, 2.0, 3.0, 4.0];
let b = [10.0, 20.0, 30.0, 40.0];
assert_eq!(compensated_dot(&a, &b), 300.0);
}
#[test]
fn compensated_mean_returns_nan_on_empty_input() {
assert!(compensated_mean(std::iter::empty::<f64>()).is_nan());
let (m, v) = compensated_mean_and_var(std::iter::empty::<f64>());
assert!(m.is_nan() && v.is_nan());
}
}