Allocation Algorithms Revisited

I realised recently there is another property allocation algorithms Error-Minimising and Balinski-Young should have. Robust allocation algorithms should produce the same results reordered for reordered weights. This is not only about when we need this property to hold, but also about making sure we have the most canonical algorithms possible.

Reordered Weights Test

Using CsCheck it is easy enough to add this to the set of allocator tests.

Ignore for the moment the new long weight versions.

Balinski-Young passes the test but Error-Minimising does not. It has a rounding issue that produces occasional off by one differences. Investigating further we find the weight sum is causing the problem.

Error Minimising Algorithm

This can be solved by using the FSum algorithm from the previous post with an additional compression step.


We are back to being able to say these two algorithms are the best solutions to the allocation problem. I can't think of any other invariants the algorithm parameters could be required to satisfy.

If possible, prefer the long weight versions as the summation has no rounding complication and is much simpler.

The only possible way to get to the correct algorithm is by using random testing. The edge cases are just too infrequent with numeric algorithms to catch with example-based testing. CsCheck 3 was recently released with improved floating-point number generation and testing.

In the next post we will investigate recommendations on which data types to use for numeric data.

Compression Algorithm