How to divide an amount into a large number of pieces

If somebody asked you to divide $10 among 3 people, how will you divide the money? 3.33, 3.33 and 3.33? The three amounts do not add back to $10. To accurately (but not necessary fairly) distribute $10 you will have to give $3.34 to one person. Thus when you add $3.33, $3.33 and $3.34 it adds up to $10.

How will you do this programatically in java? We faced this problem few months ago. It wasn't a trivial problem to solve. But Martin Fowler came to our rescue. His Money class does the magic. Let's look at it's divide method:

public Money[] divide(int denominator) {
   BigInteger bigDenominator = BigInteger.valueOf(denominator);
   Money[] result = new Money[denominator];
   BigInteger simpleResult = amount.divide(bigDenominator);
   for (int i = 0; i < denominator ; i++) {
 result[i] = new Money(simpleResult, currency, true);
   }
   int remainder = amount.subtract(simpleResult.multiply(bigDenominator)).intValue();
   for (int i=0; i < remainder; i++) {
 result[i] = result[i].add(new Money(BigInteger.valueOf(1), currency, true));
   }
   return result;
}

The method above divides the given amount ($10) by a denominator - 3. All it's doing is dividing 10 / 3 and storing the result into an array - {3.33, 3.33, 3.33}. Then it finds out how many pennies are remaining by doing 10 - (3.33 * 3) = 0.01 - that is 1 penny. It starts distributing remaining pennies to the elements of the previously resulted array. As only one penny is remaining we just add this penny to the first element. Thus now we have {3.34, 3.33, 3.33}.

The algorithm ensures the if you add the distributed amount back, you will get the original amount back - 3.34 + 3.33 + 3.33 = 10. But the algorithm hogs memory if your denominator is a very big number. In our case, we had to divide an amount into 12 million pieces. It's very inefficient as it created array of 12 million elements! I changed the method in the following way to make the division memory efficient:

def divideEfficiently(int denominator) {
   BigInteger bigDenominator = BigInteger.valueOf(denominator);
   BigInteger simpleResult = amount.divide(bigDenominator);

   def map = [:]
   def dividedMoney = new Money(simpleResult)
   for (int i = 0; i < denominator ; i++) {
       map[dividedMoney] = map.get(dividedMoney, 0) + 1
   }
   int remainder = amount.subtract(simpleResult.multiply(bigDenominator)).intValue();
   def Money one = new Money(BigInteger.valueOf(1))
   def addedMoney = dividedMoney.add(one)
   for (int i=0; i < remainder; i++) {
       map[dividedMoney] = map.get(dividedMoney) - 1
       map[addedMoney] = map.get(addedMoney, 0) + 1
   }
   return map;
}

The above method is similar but instead of giving an array of 3 elements, it gives a map of two elements [3.34 : 1, 3.33 : 2]. The map indicates that you have two shares of 3.33 and 1 share of 3.33. Your 12 million shares can be simply mentioned by two elements in a map!

Let me explain this with one more example. If you are trying to divide 11 in 13 pieces the original algorithm will give you following array : {0.85, 0.85, 0.85, .85, 0.85, 0.85, 0.85, .85, 0.84, 0.84, 0.84, .84, .84}. You can notice that there are only two unique elements in above array - .85 and .84. Thus the array can be expressed in the following map - [0.85 : 8, 0.84 : 5]. Even if your denominator is 12 million, you will always get two unique elements by Fowler's algorithm and hence the result can always be expressed as a map of two simple elements there by saving huge amount of memory.