1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
use crate::moonblade::types::DynamicNumber;
// NOTE: None means the sum means integer overflow
// NOTE: this sum implementation is using the Kahan-Babuska routine for precision
// Ref: https://en.wikipedia.org/wiki/Kahan_summation_algorithm
// Ref: https://github.com/simple-statistics/simple-statistics/blob/main/src/sum.js
#[derive(Debug, Clone)]
pub struct Sum {
current: Option<DynamicNumber>,
correction: f64,
}
impl Sum {
pub fn new() -> Self {
Self {
current: Some(DynamicNumber::Integer(0)),
correction: 0.0,
}
}
pub fn clear(&mut self) {
self.current = Some(DynamicNumber::Integer(0));
self.correction = 0.0;
}
pub fn add(&mut self, value: DynamicNumber) {
if let Some(current_sum) = self.current.as_mut() {
match current_sum {
DynamicNumber::Float(a) => match value {
DynamicNumber::Float(b) => {
let transition = *a + b;
if a.abs() > b.abs() {
self.correction += *a - transition + b;
} else {
self.correction += b - transition + *a;
}
*a = transition;
}
DynamicNumber::Integer(b) => {
let b = b as f64;
let transition = *a + b;
if a.abs() > b.abs() {
self.correction += *a - transition + b;
} else {
self.correction += b - transition + *a;
}
*a = transition;
}
},
DynamicNumber::Integer(a) => match value {
DynamicNumber::Float(b) => {
let a = *a as f64;
let transition = a + b;
if a.abs() > b.abs() {
self.correction += a - transition + b;
} else {
self.correction += b - transition + a;
}
self.current = Some(DynamicNumber::Float(transition));
}
DynamicNumber::Integer(b) => {
self.current = a.checked_add(b).map(DynamicNumber::Integer)
}
},
};
}
}
pub fn get(&self) -> Option<DynamicNumber> {
// NOTE: f64 overflow is a little bit more subtle
match self.current {
None => None,
Some(sum) => match sum {
DynamicNumber::Float(mut f) => {
f += self.correction;
if f == f64::MAX || f == f64::MIN || f.is_infinite() {
None
} else {
Some(DynamicNumber::Float(f))
}
}
_ => self.current,
},
}
}
pub fn merge(&mut self, other: Self) {
if let Some(other_sum) = other.get() {
self.add(other_sum);
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_kahan_babuska_summation() {
let a = 10000.0;
let b = 3.14159;
let c = 2.71828;
assert_eq!(a + b + c, 10005.859869999998);
let mut sum = Sum::new();
sum.add(DynamicNumber::Float(a));
sum.add(DynamicNumber::Float(b));
sum.add(DynamicNumber::Float(c));
assert_eq!(sum.get(), Some(DynamicNumber::Float(10005.85987)));
}
}