Proportionately distribute (prorate) a value across a set of values

Question

I have a need to write code that will prorate a value across a list, based on the relative weights of "basis" values in the list. Simply dividing the "basis" values by the sum of the "basis" values and then multiplying the factor by the original value to prorate works to a certain degree:

proratedValue = (basis / basisTotal) * prorationAmount; 

However, the result of this calculation must then be rounded to integer values. The effect of the rounding means that the the sum of proratedValue for all items in the list may differ from the original prorationAmount.

Can anyone explain how to apply a "lossless" proration algorithm that proportionately distributes a value across a list as accurately as possible, without suffering from rounding errors?

Answer 1

Simple algorithm sketch here...

1. Have a running total which starts at zero.
2. Do your standard "divide basis by total basis, then multiply by proportion amount" for the first item.
3. Store the original value of the running total elsewhere, then add the amount you just calculated in #2.
4. Round both the old value and the new value of the running total to integers (don't modify the existing values, round them into separate variables), and take the difference.
5. The number calculated in step 4 is the value assigned to the current basis.
6. Repeat steps #2-5 for each basis.

This is guaranteed to have the total amount prorated equal to the input prorate amount, because you never actually modify the running total itself (you only take rounded values of it for other calculations, you don't write them back). What would have been an issue with integer rounding before is now dealt with, since the rounding error will add up over time in the running total and eventually push a value across the rounding threshold in the other direction.

Basic example:

Input basis: [0.2, 0.3, 0.3, 0.2] Total prorate: 47  ----  R used to indicate running total here:  R = 0  First basis:   oldR = R [0]   R += (0.2 / 1.0 * 47) [= 9.4]   results[0] = int(R) - int(oldR) [= 9]  Second basis:   oldR = R [9.4]   R += (0.3 / 1.0 * 47) [+ 14.1, = 23.5 total]   results[1] = int(R) - int(oldR) [23-9, = 14]  Third basis:   oldR = R [23.5]   R += (0.3 / 1.0 * 47) [+ 14.1, = 37.6 total]   results[1] = int(R) - int(oldR) [38-23, = 15]  Fourth basis:   oldR = R [37.6]   R += (0.2 / 1.0 * 47) [+ 9.4, = 47 total]   results[1] = int(R) - int(oldR) [47-38, = 9]  9+14+15+9 = 47