2
$\begingroup$

The following problem comes from a piece of software I am currently working on, but since it's partially a mathematical problem, I'll ask the question here.

In my application I have a fixed value (e.g. 1000) which needs to be divided into multiple different values. The problem is that the algorithm (in another application) that divides the value returns non-integer values, and the nature of my current application requires integer values.

If the starting value is divided in two values, this shouldn't be a problem in most cases. E.g. if 1000 is divided in 600.6 and 399.4, then I can safely round this and get 601 and 399, which still sum up to 1000.

However, if the value is divided in more than 2 values, I cannot simply round the results, as this may cause an overflow or a slack. E.g. if 1000 is divided in:

  • 300.6
  • 300.6
  • 398.8

Then rounding these values give me: 301, 301 and 399, which sums up to 1001.

In my application I could decide to round down everything, which would give me 300, 300 and 398. Although the sum is not 1000 anymore, in my case a smaller value (slack) is more acceptible than a larger value (overflow).

Are there any known tricks in number theory that provide better rouding mechanisms so this problem can be minimized? E.g. by using information about statistical distribution of numbers/digits?

Notice that:

  • I can't change the original division algorithm
  • I can't try to sum up the values myself and manually change one of the input values (in my situation the starting value could be divided in hundreds, thousands or even millions of different values)
  • I can only change the rounding method

Thanks in advance

  • 0
    The other thing you might prefer to do is minimize the percentage changes. For example, if you have four numbers $0.25,1.25,3.25,99.25$ you might prefer to "round" these as $0,1,3,100$ because the change from $99.25$ to $100$ is a smaller percentage change than it would be to choose, say, $1,2,3,99$. It really depends on what your data represents which sort of algorithm you want.2012-09-10

4 Answers 4

0

I can't try to sum up the values myself and manually change one of the input values (in my situation the starting value could be divided in hundreds, thousands or even millions of different values)

That's what the computer is for: just program it to do what you would do if you were doing things manually.

You could even code up several different approaches to see which one gives results most suitable for your application.

2

It sounds like you would like to find a rounding cutoff that ensures the total of the rounded values is no more than the sum of the unrounded values. As you say, the simplest is to always round down. You could use the techniques of selection algorithms to find the breakpoint, I believe in $O(n)$ time. Another choice would be to keep a tally of the total of the changes due to rounding. For each number, round correctly unless it would make the total change positive, in which case round down.

1

To restate the problem:

You have $N$ numbers $r_i \in [0,1]$ whose sum is is some integer $M$. you want a function $f(r) \in [0,1]\rightarrow \{0,1\}$, such that: $\sum{f(r_i)}=M$ I would suggest using a random procedure whereas you map $p = M/N$ percent of the values to $1$, and the rest to $0$. Since the numbers are distributed evenly, I think this is the best you can get.

Edit: Thomas Andrews has suggested rounding up with probability $r_i$, The expected value in this case is indeed $M$, but you may get an overflow in some cases.

  • 1
    It's really no more than your solution, with a tweak to the probability. Basically, if each probability is $r_i$ of being rounded up to $1$, then the expected value of the sum is $\sum r_i$, which is the sum you wanted, with the added advantage that the higher $r_i's$ are more likely to be rounded up.2012-09-10
1

You can use any method used for the distribution of seats among parties based on votes in countries with PR. For example the largest remainder method: http://en.wikipedia.org/wiki/Largest_remainder_method