Take the 2-minute tour ×

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?

share|improve this question
There is no irrational number in a computer. The 3s in 0.3333333333 floating point value does not extend indefinitely. I think you need to redefine you requirements. –  Lie Ryan Oct 17 '10 at 0:58
Btw, 0.333... is a rational number: it's fraction-of-2-integers equivalent is 1/3. –  Ani Oct 17 '10 at 0:58
I don't think you actually mean "round a set of numbers to the nearest rational number" ==> en.wikipedia.org/wiki/Rational_number –  Peter Ajtai Oct 17 '10 at 1:39
@Ani @Peter Thank you for pointing that out. Its quite some time since I studied maths. –  poleposters Oct 26 '10 at 7:11

7 Answers 7

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.
share|improve this answer
The sum in step 2 can actually differ from 1 by more than one digit-in-the-last-place, in which case the right thing to do would be to correct each of the top n misrounded values by one digit-in-the-last-place, not put it all on the top 1. –  hobbs Oct 17 '10 at 3:29
@hobbs You're absolutely right, and that's why I prefaced with "not perfect". But note that for fewer than 10 elements that situation is impossible, and beyond 10 it's a random walk that determines whether it happens. So depending on how many elements the OP is dealing with, that situation might be unlikely enough to not merit the extra code. –  AlcubierreDrive Oct 17 '10 at 4:03
@Jon In this case you're right because all the numbers sum to 1. If you use the same thing on a sum of arbitrary numbers, though, you only need four elements to get a two-digit error, or three if they're exactly the right values to mess with your rounding policy (e.g. round-to-even, round-half-up, etc.) –  hobbs Oct 17 '10 at 7:56
(and, totally understood that you advertised this as a quick and dirty solution -- it works great! I was just trying to shed a little more light on it.) –  hobbs Oct 17 '10 at 7:57
Thank you. This is a good approach. –  poleposters Oct 26 '10 at 7:12

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.

share|improve this answer

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.

share|improve this answer
The problem space here isn't all that large, so this should be solvable in a reasonable amount of time. +1 for formulating it as an optimization. –  Mark Elliot Oct 17 '10 at 3:38
The *100 approach does seem to simplify the problem. Thank you for pointing out the difficutly in solving this problem. I thought this might be the case.Its a fairly trivial application, which it seems are often the most difficult to comppute. –  poleposters Oct 26 '10 at 7:14

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.

share|improve this answer
Great idea! I can immediately see how I could code this.(My skills are limited) –  poleposters Oct 26 '10 at 7:15

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!

share|improve this answer
Wow. I'm very intrigued by this method. It seems to work out very elegantly. Thank you for the thorough explanation. –  poleposters Oct 26 '10 at 7:19

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.

share|improve this answer
If n, m and o are all 1, then their least common denominator x is 1, and 1/1 cannot be the unit. Hence this won't work. –  Pedery Oct 17 '10 at 1:16

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.

share|improve this answer

Your Answer


