# Allocating an integer sum proportionally to a set of reals

Imagine we have an integer amount (e.g. integer cents) to be allocated across a weighted set of items where the total allocated amount must sum to the original amount. For example:

``````Amount: \$1.00

Item      Weight     Allocated Amount
a         1          \$0.33
b         1          \$0.33
c         1          \$0.33
``````

Which could be brought to satisfaction by adjusting item `c` to be \$0.34.

Is there an algorithm that results in even distribution of rounding error with only earlier weights and the total weight being known?

• Are you sure that you can safely increase c (and why c, not b)? In many real life situations it is not possible, especially when dealing with money. – Vlad Jan 19 '17 at 14:18

The solution depends much on what you want to do with this data, or how you use it.

Once you divide the numbers and keep only the result, such as 0.33, then some information is lost. One way to deal with this is to preserve original numbers, for example, instead of 0.33, keep 1 and 3 and 1 for the weight. This way, no information is lost.

I know it is not the answer to your question, but my point is that you may need to rethink the solution. Something that achieves the objective, though it may be different from what you are currently seeking.

Calculate each allocation as a running sum of the weights at arbitrary precision. For example:

``````Amount: \$1.00

Running    New      Delta
Allocated  Running  From Prev.
Item      Weight     Amount     Rounded  Rounded
a         1          \$0.0000    \$0.33    \$0.33
b         1          \$0.3333    \$0.67    \$0.34
c         1          \$0.6666    \$1.00    \$0.33

Running allocated := ((decimal)Total Amount) * Sum(preceeding weights) / Sum(total weight)
New allocated     := ((decimal)Total Amount)
* (Sum(preceeding weights) + current weight)
/ Sum(total weight)
New Rounded       := Round(New Allocated)
Allocation        := New Rounded - Prev Rounded
``````

This ensures that rounding error does not accumulate as a number is never rounded after successive steps.

• Round to an arbitrary precision is real life fix? What about the party that takes advantage of this arbitrary rounding to buy at .33 and then sell back at .34 and bankrupts the company? – paparazzo Jan 18 '17 at 22:58
• @Paparazzi, the actual scenario is relating to allocation of cost across multiple users and could not be arbitraged in that manner. I've never seen an accounting system with infinite precision, at some point you are going to have to round. – Mitch Jan 19 '17 at 0:42
• Not round to arbitrary precision and round to your favor might be a better strategy. – paparazzo Jan 19 '17 at 1:13
• @Paparazzi, this is a question of allocation. The result must be zero sum - no rounding method is in my favor or detriment. Some are just more accurate than others. – Mitch Jan 19 '17 at 1:40

I have encountered this problem multiple times and came up with the following which minimizes rounding amounts (i.e. increases accuracy) with varying weights:

1. Total up the weights.
2. Divide the total by each line's weight. Keep the quotient and the remainder at each line.
3. While the total of the quotients does not equal the original amount:
1. Find the line with the greatest remainder.
2. Increase its quotient by one, decrease remainder by the weight (i.e. manually adjust the division results).
3. Increase the calculated total by one.

When this is done, everything will add up and the quotients will be as accurate as possible.

• The total weight is also known. I do recognize that was not adequately communicated in the question. – Mitch Jan 19 '17 at 0:31