Understanding CEILING macro use cases

Question

I've found the following macro in a utility header in our codebase:

#define CEILING(x,y) (((x) + (y) - 1) / (y))

Which (with help from this answer) I've parsed as:

// Return the smallest multiple N of y such that:
//   x <= y * N

But, no matter how much I stare at how this macro is used in our codebase, I can't understand the value of such an operation. None of the usages are commented, which seems to indicate it is something obvious.

Can anyone offer an English explanation of a use-case for this macro? It's probably blindingly obvious, I just can't see it...

Answer 1

Say you want to allocate memory in chunks (think: cache lines, disk sectors); how much memory will it take to hold an integral number of chunks that will contain the X bytes? If the chuck size is Y, then the answer is: CEILING(X,Y)

Answer 2

When you use an integer division in C like this

y = a / b

you get a result of division rounded towards zero, i.e. 5 / 2 == 2, -5 / 2 == -2. Sometimes it's desirable to round it another way so that 5 / 2 == 3, for example, if you want to take minimal integer array size to hold n bytes, you would want n / sizeof(int) rounded up, because you want space to hold that extra bytes.

So this macro does exactly this: CEILING(5,2) == 3, but note that it works for positive y only, so be careful.

Answer 3

Hmm... English example... You can only buy bananas in bunches of 5. You have 47 people who want a banana. How many bunches do you need? Answer = CEILING(47,5) = ((47 + 5) - 1) / 5 = 51 / 5 = 10 (dropping the remainder - integer division).

Answer 4

Let's try some test values

CEILING(6, 3) = (6 + 3 -1) / 3 = 8 / 3 = 2 // integer division
CEILING(7, 3) = (7 + 3 -1) / 3 = 9 / 3 = 3
CEILING(8, 3) = (8 + 3 -1) / 3 = 10 / 3 = 3
CEILING(9, 3) = (9 + 3 -1) / 3 = 11 / 3 = 3
CEILING(10, 3) = (9 + 3 -1) / 3 = 12 / 3 = 4

As you see, the result of the macro is an integer, the smallest possible z which satisfies: z * y >= x.

We can try with symbolics, as well:

CEILING(k*y, y) = (k*y + y -1) / y = ((k+1)*y - 1) / y = k
CEILING(k*y + 1, y) = ((k*y + 1) + y -1) / y = ((k+1)*y) / y = k + 1
CEILING(k*y + 2, y) = ((k*y + 2) + y -1) / y = ((k+1)*y + 1) / y = k + 1
....
CEILING(k*y + y - 1, y) = ((k*y + y - 1) + y -1) / y = ((k+1)*y + y - 2) / y = k + 1
CEILING(k*y + y, y) = ((k*y + y) + y -1) / y = ((k+1)*y + y - 1) / y = k + 1
CEILING(k*y + y + 1, y) = ((k*y + y + 1) + y -1) / y = ((k+2)*y) / y = k + 2

You canuse this to allocate memory with a size multiple of a constant, to determine how many tiles are needed to fill a screen, etc.

Watch out, though. This works only for positive y.

Hope it helps.

Answer 5

CEILING(x,y) gives you, assuming y > 0, the ceiling of x/y (mathematical division). One use case for that would be a prime sieve starting at an offset x, where you'd mark all multiples of the prime y in the sieve range as composites.