Once again, while reviewing some source code, I’ve come across two new solutions to the Pizza Box Problem. For those who don’t remember, the Pizza Box Problem is about finding an answer to the question how many pizza bags you need to ship a certain quantity of pizza boxes. This problem pops up frequently in systems programming, albeit in different guises. The solution I gave then was:

where N is the number of pizza boxes that fit into a pizza bag and ‘/’ is the integer division operator that rounds towards zero.

Here is the first alternative I’ve seen. Someone wants to chop-up a larger message into smaller packets and in order to find out how many packets are to be sent:

What this code does is add one to the result of the division, except for cases where the remainder of the division is zero. This code seems to work fine, but is it also efficient?

At first glance, you might think that it is way less efficient than my official solution on the grounds that it uses the modulo operator and this requires yet another expensive integer division operation.

As usual, the real answer is: “it depends”. Some architectures (like Intel x86) have DIV instructions that return the division result and the remainder at the same time, while others do not. If the former is the case, you get the modulo operation for free. If not, you will have to pay the price. For instance, the PowerPC architecture requires you to calculate the remainder in three steps “by hand”:

Another downside is the fact that the code is not branch-free. Depending on the platform you are on, you might get a penalty if the branch is taken (“pipeline flush”). Yet, the likelihood that the branch is taken is actually low, as it happens only if size is not evenly divisible by MAX_PACKET_SIZE.

By and large, I don’t like this approach. It requires more typing and is likely to have an efficiency issue.

But I’ve come across another promising solution:

Compared to my original solution, this version has a clear advantage: it doesn’t suffer from overflow issues. Consider the original pizza box formula:

Depending on the number of pizza boxes and N it is possible that their sum overflows the value range of their underlying types, which would result in a wrong value of pizza_bags.

Alas, this advantage comes at the cost of another disadvantage: if the number of pizza boxes is zero, pizza_bags will not compute to zero but to an insanely large number.

So depending on the constraints of your context, you now have two efficient possibilities to choose from. Regardless of your decision, I advise you to use explicit assertions to state and check your assumptions. Either:

or