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 and in Java will always floor the result:

1 2 |
int a, b; int ans = a/b; // is the same as Math.floor(a/b) |

well almost. Actually `Math.floor(a/b)`

rounds towards negative infinity, where as `a/b`

rounds towards zero:

1 2 |
System.out.println(Math.floor(-1.5)); // -2 System.out.println(-3/2); // -1 |

Fact 2

if

if

Fact 3

**What we need is**

Since dividing two integers and in Java will always floor the result, we need to find some such that .

How do we find ?

Think about it this way: , except when is a whole number. So, we want to bump to (or past) the next whole number, unless is a whole number, by adding . This way . We want to find 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 and then , which is not the desired result. As you can see, by using we bumped to far. So must definitely be less than .

So how much is just enough?

Assume . Then , which can be re-written as:

In other words, we get an integer part () and a left over (). The left over part is always in the form of , with . Thus, the smallest non-whole number we can get from is with being the integer part with .

So assuming is not a whole number, the smallest left over we can have is . So in-order to bump to the next whole number, it suffices to add . This is , which will not bump to the next whole number in case is a whole number, but still enough to bump to the next whole number in case is not a whole number.

**Summing it up**

So we know adding to will fulfill the equality: . Thus we get:

1 2 |
int a,b; int myceil = (a + b - 1)/b; |