Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
Given a sequence of floating numbers, $(x_1,...,x_n)$ such that $x_1+...+x_n$ is an integer, you want a sequence $(y_1,...,y_n)$ of integers such that $y_1+...+y_n=x_1+...+x_n$ and some distance function is minimized, possibly $\sum |x_i-y_i|$ or $\sum (x_i-y_i)^2$. –  Thomas Andrews Sep 10 '12 at 15:38
    
Even with division into two, you can have problems. For example, if 603 is divided into 301.5 and 301.5, you need to round one up and one down. –  Ross Millikan Sep 10 '12 at 15:45
    
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. –  Thomas Andrews Sep 10 '12 at 15:49
add comment

4 Answers

up vote 1 down vote accepted

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.

share|improve this answer
    
You can actually do better than a fixed probability by rounding up your number $r\in[0,1)$ with probability $r$. –  Thomas Andrews Sep 10 '12 at 16:12
    
@ThomasAndrews - I'd love to see that solution. care to add it as an answer? –  nbubis Sep 10 '12 at 17:44
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. –  Thomas Andrews Sep 10 '12 at 19:18
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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