fsum 0.1.4

The library to calculate accurate sum of floats.
Documentation 
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

`fsum` is the Rust library by Piotr Beling to calculate accurate sum of floats.

# Example

```rust
use fsum::FSum;

assert_eq!(FSum::new().add(1e100).add(1.0).add(-1e100).value(), 1.0);
assert_eq!(FSum::with_all((0..10).map(|_| 0.1)).value(), 1.0);
assert_eq!(FSum::with_all(&[1e100, 1.0, -1e100]).value(), 1.0);

let mut s = FSum::new();
assert_eq!(s.value(), 0.0);
s += 3.0;
assert_eq!(s.value(), 3.0);
s -= 1.0;
assert_eq!(s.value(), 2.0);
```

# Complexity

The complexities of summing *n* numbers are:
- time: from *O(n)* (optimistic) to *O(n²)* (pessimistic)
- memory: from *O(1)* (optimistic) to *O(n)* (pessimistic)

Usually the complexities are close to optimistic.

# References

Calculation code is based on (is mostly copied from) `sum` method
of `test::stats::Stats` implementation for `f64`
(which probably reimplements `math.fsum` from Python's library)
and source of CPython.
See also:
- <https://github.com/python/cpython/blob/2b7411df5ca0b6ef714377730fd4d94693f26abd/Lib/test/test_math.py#L647>
- <https://bugs.python.org/file10357/msum4.py>
- <http://code.activestate.com/recipes/393090/>

The method sacrifices performance at the altar of accuracy.
It depends on IEEE-754 arithmetic guarantees. See proof of the correctness in
[Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric
Predicates][paper]

[paper]: <http://www.cs.cmu.edu/~quake-papers/robust-arithmetic.ps>