Is there any better way to calculate (n * 8 + 3) / 5?

Question

I need to take a size_t volume and calculate this result in a size_t:

size_t next = (volume * 8 + 3) / 5

If this result would overflow a size_t then next should be zero. The problem is of course that volume * 8 + 3 can overflow while the entire result fits in a size_t.

At the moment I am splitting out the last 4 bits of volume and performing the multiplication, addition, and division separately. My question is: Can I do better than what I have so far if there is no type larger than size_t?

size_t next_volume(size_t volume) {
  // check if the numerator will overflow size_t
  if (volume > (SIZE_MAX - 3) / 8) {
    size_t lower, upper;

    // multiply lower 4 bits by 8 and add 3
    lower = ((volume & 0xF) * 8) + 3;
    // downshift the rest and multiply by 8
    upper = (volume >> 4) * 8;

    // divide upper remainder and lower by 5
    lower = ((upper % 5 << 4) + lower) / 5;

    // divide upper by 5
    upper = upper / 5;

    // ensure the sum will not overflow size_t
    if (upper + (lower >> 4) > SIZE_MAX >> 4)
      return 0;

    return (upper << 4) + lower;
  } else return (volume * 8 + 3) / 5;
}

There might be some errors in that code. I haven't put it through extensive testing yet but I believe all the main ideas are there.

Answer 1

Let vol1 = volume % 5, vol2 = volume - vol1. vol2 is divisible by 5, therefore mathematically (vol2 * 8) / 5 = (vol2 / 5) * 8, so you get the correct result as

size_t vol1 = volume % 5;
size_t vol2 = volume - vol1;
size_t result = (vol2 / 5) * 8 + (vol1 * 8 + 3) / 5

Obviously you will get an overflow if the result doesn't fit into size_t, but not if there is an overflow anywhere in the calculation. Since you multiply by 8/5, in case of an overflow the result will be about 0.6 * volume < volume, so you can return

return result < volume ? (size_t) -1 : result;

which is surely better than returning 0.