What is the simplest way to compute the lowest integer greater or equal than a / b?

Tag: algorithm Author: kayllentJun Date: 2009-08-04

r, a and b are integers.

I need the cheapest computation since in a critical part of the code. I found :

r = (a / b) + (((a % b) != 0) ? 1 : 0);

if b is a power of 2, then a / b can be replaced with a >> log2(b)

and a % b with a & (b-1) which should save a lot of computation time.

Do you know any better solution ?

Is this really a bottle-neck?
Why not take him at his word? He says it's a bottleneck. He bothered to write up a question about it.
This is pretty ugly, but relatively straightforward when you understand what it's doing, and probably not all that slow. Any efforts to optimize by bit shifting when b is a power of 2, etc...unless you have a good reason to believe that's really going to be the case a lot of the time, I think you're going to slow things down with tests that aren't going to be true most of the time, and you'll have to do the "long" work anyway.
What's the relevance of it being a bottleneck or not? Are you going to answer only if it's a bottleneck? That's silly.
But for the sake of other people who might learn from the responses, it makes sense to answer as if it were a bottleneck so everyone can learn. This question is a great example of how a messy expression is actually doing something so simple that it can be made clear and efficient simultaneously, as Daniel showed.

Best Answer

val r = (a + b - 1) / b

For example:

scala> for(a <- 1 to 10; b <- 1 to a) println("a: "+a+"\tb: "+b+"\tr: "+((a+b-1)/b))
a: 1    b: 1    r: 1
a: 2    b: 1    r: 2
a: 2    b: 2    r: 1
a: 3    b: 1    r: 3
a: 3    b: 2    r: 2
a: 3    b: 3    r: 1
a: 4    b: 1    r: 4
a: 4    b: 2    r: 2
a: 4    b: 3    r: 2
a: 4    b: 4    r: 1
a: 5    b: 1    r: 5
a: 5    b: 2    r: 3
a: 5    b: 3    r: 2
a: 5    b: 4    r: 2
a: 5    b: 5    r: 1
a: 6    b: 1    r: 6
a: 6    b: 2    r: 3
a: 6    b: 3    r: 2
a: 6    b: 4    r: 2
a: 6    b: 5    r: 2
a: 6    b: 6    r: 1
a: 7    b: 1    r: 7
a: 7    b: 2    r: 4
a: 7    b: 3    r: 3
a: 7    b: 4    r: 2
a: 7    b: 5    r: 2
a: 7    b: 6    r: 2
a: 7    b: 7    r: 1
a: 8    b: 1    r: 8
a: 8    b: 2    r: 4
a: 8    b: 3    r: 3
a: 8    b: 4    r: 2
a: 8    b: 5    r: 2
a: 8    b: 6    r: 2
a: 8    b: 7    r: 2
a: 8    b: 8    r: 1
a: 9    b: 1    r: 9
a: 9    b: 2    r: 5
a: 9    b: 3    r: 3
a: 9    b: 4    r: 3
a: 9    b: 5    r: 2
a: 9    b: 6    r: 2
a: 9    b: 7    r: 2
a: 9    b: 8    r: 2
a: 9    b: 9    r: 1
a: 10   b: 1    r: 10
a: 10   b: 2    r: 5
a: 10   b: 3    r: 4
a: 10   b: 4    r: 3
a: 10   b: 5    r: 2
a: 10   b: 6    r: 2
a: 10   b: 7    r: 2
a: 10   b: 8    r: 2
a: 10   b: 9    r: 2
a: 10   b: 10   r: 1

This does assume a and b are positive. If either are negative, it depends on whether the division is symmetric or floored (modern languages and platforms are symmetric), and the signal of a and b.

If a*b >= 0, then the formula works as given. If the division is symmetric and a*b < 0, then a / b gives the correct answer.

comments:

Good call, wouldn't have thought of doing it that way
For some reason, I have written this code many, many times. The trick is that (b - 1) / b is equal to 0, so it won't change the result unless a % b > 0.
Fantastic. Very elegant. I'm impressed.
and a great demonstration over why improving the algorithm wins over optimising what is there provides such huge wins :)
To me that's the essence of optimization. You look at the inputs and the outputs and try to find the best way (whatever best may mean in the situation) from here to there.

Other Answer1

In the title you ask about the "simplest" - yet the question alludes to the most "effective". Which one do you need? In practice the simplest doesn't always equate to the most effective.

So if you need the simplest method, you should probably be using your language's ceiling function (usually called ceil), if you need the most efficient - that really depends a lot on the processor you're using (whether it implements division in hardware and other such factors)

Also, I'm a little skeptical about the performance of log2 - but I may be wrong.. However one thing is pretty clear: optimizing for the sake of optimizing is almost always not a good idea.

comments:

In this case the optimization (as Daniel showed) is also clearer code.
Indeed, the most effective is not always the simplest, and log2 is definitely NOT an efficient function (actually b is a constant in my specific case) But you did not play this little game ;-)
BTW, "effective" does not mean "efficient". It only means something that works (something that produces a notable effect).

Other Answer2

What about:

(a - 1) / b + 1;

Obviously you have to watch yourself if a might be 0 or less. Negative numbers don't necessarily divide the way you expect, it depends on language and implementation.

Other Answer3

modulo can be implemented a % n = a - (n * (a / n);

So taking that into account you could re-write as

const int div = a / b;
r = div + (((a - (n * div)) != 0) ? 1 : 0 );

which will be marginally faster as you only do one div instead of 2.

Edit: If b is a constant then you can actually remove the divide completely and replace it with a multiply by a "magic number" (relevant to the constant divisor) that will be a small amount faster again. Then again the compiler WILL make this optimisation anyway with a constant divisor.

comments:

It might be marginally faster. With a decent compiler, on a processor with an integer division op that calculates quotient and remainder, only one div will be done either way.
Man...better have a good comment in your code when you drop those lines in!
I was thinking something similar. Some algorithms compute both "/" and "%" at the same time.
Come to think of it, in cases with a "good" division op, this might end up slower than the questioner's code, because it introduces a multiply.
What are you talking about dilig0?

Other Answer4

This may or may not be suitable for what you're looking for, but most (if not all) languages provide access to a mathematical ceiling function. For example, in C#, writing Math.Ceiling(5/2) yields 3.

comments:

well, the function is Math.Ceiling for one... My guess is he's trying to keep it to integer division, but who knows...
even javascript has it :-) "Math.ceil(5/2)"
Floating point math is usually slower than integer, especially if the parameters are integers and need to be converted.

Other Answer5

Since no language was specified, I'm going to write a solution in ANS Forth as well...

: div ( a b -- r)
  FM/MOD     \ a b -- q rest
  IF 1+ THEN \ q rest -- r
;

Other Answer6

If you are on a desktop, try floating point numbers and round them. But I doubt that you can find anything that is more cheap than two int devisions plus an add.

The only other option is the DIVMOD operator which some CPUs support. It will give you both the division and the rest in a single call.