Batch rounding with preservation of a sum

Question

I have a sequence of floating point numbers. I want to map each of them to one of their closest integers. There is one rule:

Sum of integers must be as close to the sum of original numbers as possible (ideally sum of integers is a rounded sum of originals).

You can think about it as of snapping to grid some bar plot with preserving its total area.

Answer 1

There are many rounding methods that round an integer to the nearest integer, all of which are the same except on the half-integers. The sum of integers returned will be close to the sum of the original numbers on average when the distribution of the fraction parts of the numbers are roughly symmetric to $0.5$. One of those methods might be good enough for you in practice.

However, none of them will ensure the rule for sum, "the sum of output integers must be as close to the sum of original numbers as possible". For example, the nearest integer to $0.6$ and $0.7$ is $1$ but the nearest integer to their sum $0.6+0.7=1.3$ is $1$ instead of $1+1 =2$. Hence to satisfy the rule of sum, we cannot guarantee that each integer is mapped to its nearest integer.

Let us pick one of the rounding methods as $\mathcal R$, which will specify the exact meaning of "as close as possible". For methods below, we will ensure that $$\mathcal R(\text{sum of input numbers})=\text{sum of output integers}$$ while trying to round integers to their respective nearest integers fairly.

Offline Method

Suppose numbers $a_1, a_2, \cdots, a_n$ are given.
Let $\{a_i\}=a_i-\lfloor a_i\rfloor$ be the fractional part of $a_i$ and $s = \{a_1\} + \{a_2\} + \cdots + \{a_n\}$.

• Round down $a_i$ to $\lfloor a_i\rfloor$ for $i\le n-\mathcal R(s)$,
• Round up $a_i$ to $\lfloor a_i\rfloor + 1$ otherwise.

To be fair, sort $a_i$ by $\{a_i\}$ before rounding so that, for example, $4.8$ will be rounded up instead of $7.6$ if one of them should be rounded up.

Online Method

Input: a source that produces numbers
Output: numbers rounded to integers
Procedure:

1. Let number $gap$ be $0$
2. For each number $num$ in the source:
   1. Let $num{\_}rounded=\mathcal R(gap + num)$. Output $num{\_}rounded$.
   2. Add $num - num{\_}rounded$ to $gap$.

Buffered Method

We can mix the offline method and the online method by repeating the following procedure after initializing $gap=0$.

1. Apply the offline method to the next block of numbers, including $gap$ as a summand for $s$ as well.
2. Add the difference between the sum of the numbers returned in step 1 and the sum of the original numbers to $gap$.

The size of each block of numbers is up to your choice.

Answer 2

A "stateless" approach (i.e. the same value always rounding the same way) cannot work. To see why, consider a sum of always the same number. After n terms, the error will equal n times the error between the original and rounded value, and this grows unboundedly.

A simple solution is to use "error propagation", as done in the image dithering algorithms. You just keep the fractional part of the sum, and update it with the fractional part of the next number. If the new fractional part exceeds 1, transfer this unit to the rounded value.

E.g.

2.3 + 4.4 + 6.4 + 3.1 ->

2, error = 0.3;

4, error = 0.7;

6, error = 1.1, which becomes 7, error 0.1

3, error = 0.2

---

Note that this gives the same output as the simple method of effectively computing the partial sums, rounding to integer and taking the difference with the previous sum (but for accumulation of floating-point errors in the long run).

2.3 + 4.4 + 6.4 + 3.1 -> 0, 2.3, 6.7, 13.1, 16.2 -> 0, 2, 6, 13, 16 -> 2 + 4 + 7 + 3

---

Note that I used truncation, but rounding also works.

---

Update:

If the distribution of the fractional parts is uniform, rounding to the nearest integer will work on average. In practice, this is rarely the case, because of Benford's law, so a bias can be expected. You can determine it experimentally, hoping that your data sets are homogeneous. In the long run, drifts are to be feared anyway.

Answer 3

Yves's answer will give you exactly the answer you are looking for.

An alternative is to use stochastic rounding which will give you the rounded sum in expectation, and may have nicer properties for the individual numbers, although you say that is not important.

The idea is to round the number up to the next integer with probability equal to the fractional part of the number, otherwise round down.

Answer 4

I had this problem in several projects and generalized a solution: https://github.com/cgdeboer/iteround