Accurate sums and dot products for Python

## Project description

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.

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  (see also here)).

• `accupy.ksum(p, K=2)`: Summation in K-fold precision (from )

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 ill-conditioned sums; likewise for `numpy.sum` which uses pairwise summation. Kahan summation not significantly better; this, too, is expected.

Computing the sum with 2-fold 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 K-fold precision (from )

Let's compare them.

#### Accuracy comparison (dot)

accupy can construct ill-conditioned 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.

### Dependencies

accupy needs the C++ Eigen library, provided in Debian/Ubuntu by `libeigen3-dev`.

### 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
``````

accupy is published under the GPLv3+ license.

## Project details

This version 0.3.4 0.3.3 0.3.2 0.3.1 0.3.0 0.2.0 0.1.4 0.1.3 0.1.2 0.1.1 0.1.0