3
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ Round some of them to the floor and some of them to the ceiling in a way which minimizes the distance to the original sum. $\endgroup$ Apr 27, 2022 at 14:31
  • 1
    $\begingroup$ Are you doing this "on the fly" in a streaming manner (where you receive each float one at a time and have to make a rounding decision for it as soon as you receive it), or in a batch manner (where you receive all floats, before you have to make rounding decisions for any of them)? Please update your question to clarify. $\endgroup$
    – D.W.
    Apr 27, 2022 at 20:20
  • 1
    $\begingroup$ @D.W. the title seems to indicate "batch". $\endgroup$ Apr 27, 2022 at 22:38
  • $\begingroup$ stackoverflow.com/q/792460/781723 $\endgroup$
    – D.W.
    Feb 5, 2023 at 21:15

4 Answers 4

8
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ All the "round half *" methods are basically the same for all values except the exact .5 values, which obviously doesn't work in our case. Not sure what's the point of listing them all. $\endgroup$ Apr 27, 2022 at 22:41
  • $\begingroup$ @PaŭloEbermann Thanks for the feedback. That list is removed. $\endgroup$
    – John L.
    Apr 27, 2022 at 22:52
  • $\begingroup$ There can be many variations. For example, we can add a tolerance level. Round down when the fractional part is at most 1/8 or the gap is at most -1, and round up when the factional part is larger than 7/8 or the gap is at least 1. For example, we may use neighboring numbers to help determine the rounding direction of the current number. For example, we can let the block size in the mixed method be the first time beyond 100 numbers such that the absolute value of the gap is smaller than 0.1 unless that means more than 1000 numbers, at which time, 1000 numbers will be used as a block. $\endgroup$
    – John L.
    Apr 27, 2022 at 23:25
  • 2
    $\begingroup$ "To be fair, sort $a_i$ before rounding", you mean sorting based on $\{a_i\}$? So that those numbers will smaller fractional parts will be rounded down and those larger will be rounded up. $\endgroup$
    – justhalf
    Apr 28, 2022 at 3:36
  • $\begingroup$ @justhalf Thanks very much. Of course, sorting should be based on $\{a_i\}$. Updated. $\endgroup$
    – John L.
    Apr 28, 2022 at 4:02
6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ Welcome to Computer Science Stack Exchange! The solution seems to have a proper interface documentation. But as this is a computer science site, we need some paragraphs of explanation about the algorithm you chose. Additionally, clarify whether it is different from the other answers, or is it similar to John L's offline method, John L's online method, John L's buffered method, user16034's error propagation, or A Scheneider's stochastic rounding, or others. This is so we can peer review the answers on an equal footing, and a link alone is not a sufficient answer. Thank you for the contribution! $\endgroup$ Feb 17 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.