How do I round a set of numbers while ensuring the total adds to 1

Question

Hi,

I'm looking for a way to round a set of numbers to the nearest rational number while still preserving the total of the set.

I want to distribute the total value of '1' amongst a variable number of fields without allowing irrational numbers.

So say I want to distribute the total across three fields. I don't want each value to be 0.33333333333333333333'. I would prefer 0.33, 0.33 & 0.34.

I would like to implement this using Jquery/javascript. I have a form where fields are added dynamically. By default the total is evenly distributed amongst each field, however my problem is further complicated because often the value will not be shared equally amongst all fields. Some values might be more heavily weighted. So if I were to change one of the three values to 0.5, the other two values would be adjusted to 0.25.

Can anyone help with a suitable algorithm?

Answer 1

Not perfect, but easy to write:

1. Round every number to the nearest acceptable value. As you go, keep track of which number you rounded upward by the largest amount and which number you rounded downward by the largest amount.
2. Sum the numbers up.
3. Subtract that sum from 1.
4. If the difference is negative, add it to the number you rounded upward the most. If the difference is positive, add it to the number you rounded downward the most.

Answer 2

You're talking about fractions. For three numbers 1/n, 1/m, 1/o, find the least common denominator x of n,m,o and make 1/x your unit. Then each of the three will automatically be n/x, m/x, and o/x (whole units of 1/x) and won't need to be rounded until final output, wherever that is.

Answer 3

I sort of doubt this will help, but I can show the problem is difficult and not going to allow for a closed form (you will have to do search).

This is easy to do with rational numbers:

a/b + c/d + ... = x/z
a*z/x/b + c*z/x/d + ... = 1

But, from your example, I don't think this is what you are asking for... If you want each number to have at most 2 decimal places this is the same as fining an integer solution for the problem *100 which is the same as finding integers j,k,l to solve this optimization:

minimize (j-a*100)^2 + (k-b*100)^2 + (l-c*100)^2
 s.t.  (j + k + l) = 100    

you can recover the real values for a,b,c as:

a = j/100.;
b = k/100.;
c = l/100.;

Trouble is, integer quadratic programs are not at all easy to solve, NP-Hard in general, and I don't think the simplicity of this problem makes it much easier. I think your best approach would be to solve this in the relaxed form (real values) and do randomized rounding or something.

Answer 4

I'm having trouble understanding your description of the problem, but I hope it is equivalent to the following:

INPUT: A list of real numbers x_1, x_2, ..., x_n summing to an integer N

OUTPUT: A list of integers y_1, y_2, ..., y_n also summing to N such that y_i is either x_i rounded down or rounded up (i.e., y_i differs from x_i by less than 1).

Here is one way to do that:

• Compute the sequence of partial sums s_0 = 0, s_1 = x_1, s_2 = x_1 + x_2, ..., s_n = x_1 + ... + x_n = N.

• Round each partial sum to the nearest integer (rounding half-integers in a consistent direction, let's say up), forming the sequence t_0 = 0, t_1 = s_1 rounded to the nearest integer, ..., t_n = N.

• Let y_1 = t_1 - t_0, ..., y_n = t_n - t_{n-1}.

Then the y_i are integers which sum to N and for each i, s_i - 0.5 < t_i <= s_i + 0.5 which implies that |y_i - x_i| = |(t_i - t_{i-1}) - (s_i - s_{i-1})| < 1.

Answer 5

I would say the easiest way to do this would be, to start out with 100. Then (I'm going to assume you have integer weights on spots) say you have weights 1 1 2 3 4, sum the weights get 11 (n), distribute 11 or (100/n) for each weight that is you'll get:

9 9 18 27 36

Then sum the new weights to get 99, do 100-99=1, then distribute the left over amount to the lowest granularity you want and distribute it across the cells with random prob distribution based on weights. You might want to shift and then do this step, regardless there will be some imprecision. You can use 1000 or higher if you want more granularity. I also think it should work if you have non-integer weights you'll just have more left over in the last step to distribute.

Answer 6

The perfect (and easier) version of Jon Rodriguez approach:

Round all numbers down, save the remainders for later use.

Sort the numbers by remainder, and add 1 unit to as many of the rounded numbers as it takes to make their sum the desired value, starting from the numbers with the highest remainders.

Answer 7

As I understand the problem, we have a bunch of nonnegative floats between 0 and 1 which total 1, and we wish to round each to two decimal places without changing the fact that they sum to 1.

First, scale the numbers by a factor of 100, so that we have x_1, ... , x_n which sum to 100. Now we need to round them to integers so that they still sum to 100.

Let's write frac(x) for the fractional part of x, which can be computed as x - int(x). Notice that 0 <= frac(x) < 1.

First, consider the sum of the fractional parts frac(x_1) + frac(x_2) + ... + frac(x_n). This value is an integer between 0 and n-1. Let's call is F. An easy way to compute F is like this: 100 - (int(x_1)+...+int(x_n)). (This may also be the easiest way to see that the sum of the fractional parts is an integer!)

A little thought should convince you that this integer F is the number of times you need to round up, and therefore n-F is the number of times you need to round down. Therefore, sort your original list from least to greatest by fractional part, then round down the first n-F numbers, and round up the last F numbers.

For example, if we have the numbers 1/7, 1/6, 8/42, 1/10, 1/11, 34/110 (yes, the sum is 1) we multiply by 100 and write in decimal: 14.2857, 16.66666, 19.047619, 10, 9.090909, 30.90909. The integer parts are: 14, 16, 19, 10, 9, 30, which sum to 98. This means F=2, n-F=4. Sorting the numbers by fractional parts yields: 10, 19.047619, 9.090909,14.2857, 16.66666, 30.90909. Since F=2 and n-F=4, We round up the last two, and round down the first four. For this example, this technique is equivalent to round-to-nearest, but of course it won't always work out that way!