Accurate sums and (dot) products for Python.
Sums
Summing up values in a list can get tricky if the values are floating point numbers; digit cancellation can occur and the result may come out wrong. A classical example is the sum
1.0e16 + 1.0  1.0e16
The actual result is 1.0
, but in double precision, this will result in 0.0
.
While in this example the failure is quite obvious, it can get a lot more
tricky than that. accupy provides
p, exact, cond = accupy.generate_ill_conditioned_sum(100, 1.0e20)
which, given a length and a target condition number, will produce an array of floating point numbers that is hard to sum up.
Given one or two vectors, accupy can compute the condition of the sum or dot product via
accupy.cond(x)
accupy.cond(x, y)
accupy has the following methods for summation:

accupy.kahan_sum(p)
: Kahan summation 
accupy.fsum(p)
: A vectorization wrapper around math.fsum (which uses Shewchuck's algorithm [1] (see also here)). 
accupy.ksum(p, K=2)
: Summation in Kfold precision (from [2])
All summation methods sum the first dimension of a multidimensional NumPy array.
Let's compare them.
Accuracy comparison (sum)
As expected, the naive
sum performs very badly
with illconditioned sums; likewise for
numpy.sum
which uses pairwise summation. Kahan summation not significantly better; this,
too, is
expected.
Computing the sum with 2fold accuracy in accupy.ksum
gives the correct
result if the condition is at most in the range of machine precision; further
increasing K
helps with worse conditions.
Shewchuck's algorithm in math.fsum
always gives the correct result to full
floating point precision.
Runtime comparison (sum)
We compare more and more sums of fixed size (above) and larger and larger sums,
but a fixed number of them (below). In both cases, the least accurate method is
the fastest (numpy.sum
), and the most accurate the slowest (accupy.fsum
).
Dot products
accupy has the following methods for dot products:

accupy.fdot(p)
: A transformation of the dot product of length n into a sum of length 2n, computed with math.fsum 
accupy.kdot(p, K=2)
: Dot product in Kfold precision (from [2])
Let's compare them.
Accuracy comparison (dot)
accupy can construct illconditioned dot products with
x, y, exact, cond = accupy.generate_ill_conditioned_dot_product(100, 1.0e20)
With this, the accuracy of the different methods is compared.
As for sums, numpy.dot
is the least accurate, followed by instanced of kdot
.
fdot
is provably accurate up into the last digit
Runtime comparison (dot)
NumPy's numpy.dot
is much faster than all alternatives provided by accupy.
This is because the bookkeeping of truncation errors takes more steps, but
mostly because of NumPy's highly optimized dot implementation.
References
Dependencies
accupy needs the C++ Eigen
library, provided in
Debian/Ubuntu by
libeigen3dev
.
Installation
accupy is available from the Python Package Index, so with
pip install accupy
you can install.
Testing
To run the tests, just check out this repository and type
MPLBACKEND=Agg pytest