Implement a ceil() function

In this post I will explain a less intuitive approach of implementing a ceil() function in Java, that is faster than known comparison approaches.

A few known facts
Fact 1
Dividing two integers a and b in Java will always floor the result:

well almost. Actually Math.floor(a/b) rounds towards negative infinity, where as a/b rounds towards zero:

Fact 2
\lfloor x \rfloor = m if m \le x \textless m+1
\lceil x \rceil = n if n - 1 \textless x \le n

Fact 3
\lfloor x \rfloor \le \lceil x \rceil

What we need is \lfloor (x + s) \rfloor == \lceil x \rceil
Since dividing two integers a and b in Java will always floor the result, we need to find some s such that \lfloor (x + s) \rfloor == \lceil x \rceil.

How do we find s?
Think about it this way: \lceil \frac{a}{b} \rceil \textgreater \lfloor \frac{a}{b} \rfloor, except when \frac{a}{b} is a whole number. So, we want to bump \frac{a}{b} to (or past) the next whole number, unless \frac{a}{b} is a whole number, by adding s. This way \lfloor \frac{a}{b} + s \rfloor == \lceil \frac{a}{b} \rceil. We want to find s so that for whole numbers, it won’t quite push them up to the next whole number, but for non-whole numbers it will.

For instance, assume a=6, b=3 and s=1 then \lfloor \frac{a}{b} + s \rfloor = \lfloor \frac{6}{3} + 1 \rfloor = 3 \ne \lceil \frac{a}{b} \rceil = \lceil \frac{6}{3} \rceil = 2, which is not the desired result. As you can see, by using s=1 we bumped \frac{a}{b} to far. So s must definitely be less than 1.

So how much s is just enough?

Assume a=7, b=3. Then \frac{a}{b} = \frac{7}{3}, which can be re-written as:
\frac{7}{3} = \frac{1}{b} + \frac{1}{b} + \frac{1}{b} + \frac{1}{b} + \frac{1}{b} + \frac{1}{b} + \frac{1}{b} = (\frac{1}{3} + \frac{1}{3} + \frac{1}{3}) + (\frac{1}{3} + \frac{1}{3} + \frac{1}{3}) + \frac{1}{3} = 2  + \frac{1}{3}
In other words, we get an integer part (2) and a left over (\frac{1}{3}). The left over part is always in the form of k\frac{1}{b}, with 0 \le k \textless b. Thus, the smallest non-whole number we can get from \frac{a}{b} is qb + \frac{1}{b} with qb being the integer part with q \in \mathbb{N}_0.

So assuming \frac{a}{b} is not a whole number, the smallest left over we can have is \frac{1}{b}. So in-order to bump \frac{a}{b} to the next whole number, it suffices to add s = 1 - \frac{1}{b}. This is \textless 1, which will not bump \frac{a}{b} to the next whole number in case \frac{a}{b} is a whole number, but still enough to bump \frac{a}{b} to the next whole number in case \frac{a}{b} is not a whole number.

Summing it up
So we know adding s = 1 - \frac{1}{b} to \frac{a}{b} will fulfill the equality: \lfloor (\frac{a}{b} + s) \rfloor = \lceil \frac{a}{b} \rceil. Thus we get:

 \lceil \frac{a}{b} \rceil = \lfloor (\frac{a}{b} + s) \rfloor = \lfloor (\frac{a}{b} + 1 - \frac{1}{b}) \rfloor = \lfloor \frac{a + b - 1}{b} \rfloor

 

lucas