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
Dividing two integers and in Java will always floor the result:
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:
System.out.println(Math.floor(-1.5)); // -2 System.out.println(-3/2); // -1
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:
int a,b; int myceil = (a + b - 1)/b;