ceil() and int values

[Eric Sosman]

I need to get a ceil value from two integers
[...]
What is the "cleanest" but most compatible way? My program in this instance
always uses integers greater than zero and less than 128. Is there another
(speedier?) way other than using ceil()?

i = (i5 + i2 - 1) / i2;

Now there's a trick .... I learned it in a long-ago PPOE and think
it's kind of a clever hack.

It never struck me as either clever or hackish, but only as a
fairly obvious transformation. (Decades ago I thought it up myself,
so it can't be *that* abstruse!)

But I don't know that I've observed
anyone other than the long-ago colleague (and myself) using it.

Essentially the same thing is often done with multiples
of powers of two:

unsigned int nextEven = (value + 1u) & ~1u;
unsigned int nextSixteen = (value + 15u) & ~15u;
unsigned int nextK = (value + 1023u) & ~1023u;
// ... etc.

(`unsigned' because bit-twiddling's safer that way).

But apparently some others in this thread know about it, and also
know that it *can* run up against problems with overflow. "Hm!" ?

If it encounters overflow with "integers greater than zero
and less than 128" it's being run on a non-conforming or non-C
implementation.

 

[Phil Carmody]

Now there's a trick .... I learned it in a long-ago PPOE and think
it's kind of a clever hack. But I don't know that I've observed
anyone other than the long-ago colleague (and myself) using it.
But apparently some others in this thread know about it, and also
know that it *can* run up against problems with overflow. "Hm!" ?

When i2's big, the risk of overflow is certainly possible. However,
there's an alternative which shrinks the overflow window to be at
the other end of the range, shrinking it into all but non-existence:

i = (i5-1)/i2 + 1;

Phil

 

[blmblm]

When i2's big, the risk of overflow is certainly possible. However,
there's an alternative which shrinks the overflow window to be at
the other end of the range, shrinking it into all but non-existence:

i = (i5-1)/i2 + 1;

Um. If i5 = 0 and i2 = 2 ....

((i5 + i2 - 1) / i2) == ( (0+2-1)/2 ) == ( 1/2 ) == 0

but

((i5 - 1) / i2 + 1) == ( (0-1)/2 + 1 ) == ( (-1/2) + 1 ) == 1

no?

 

[Phil Carmody]

Um. If i5 = 0 and i2 = 2 ....

((i5 + i2 - 1) / i2) == ( (0+2-1)/2 ) == ( 1/2 ) == 0

but

((i5 - 1) / i2 + 1) == ( (0-1)/2 + 1 ) == ( (-1/2) + 1 ) == 1

no?

Good catch, due to infernal truncation towards zero. (Not a fan, it's
practical, rather than being mathematically pure, which is far more
important than being practical!)

I generally use this in contexts where I know I have a strictly
positive number. (Chunking work for cache friendlyness, for example.)

Thanks for pointing this out, it's a rather vital case.

Phil

 

[Tim Rentsch]

I need to get a ceil value from two integers

When I use as follows:
int i5,i2;
i5=5;i2=2;
i=ceil(i5/i2);
I get 2 for obvious reasons.

However when I use as follows:
int i5,i2;
i5=5;i2=2;
i=ceil((double)i5/i2);
I get 3 but from past experience I doubt some compilers will return 2.

Safest way to get 3 appears to be lengthy
int i5,i2;
i5=5;i2=2;
i=ceil((double)((double)i5/(double)i2));

What is the "cleanest" but most compatible way? My program in this instance
always uses integers greater than zero and less than 128. Is there another
(speedier?) way other than using ceil()?

Considering the quotient a/b

to divide rounding up: a/b + (a%b > 0)
to divide rounding down: a/b - (a%b < 0)

These expressions work for all signed (or unsigned) values of {a,b}
when the result is defined and representable, under both C90 and
C99/C11 operation rules.

Note also, on x86 I believe both quotient and remainder are
produced by a single instruction, so the speed should be okay
on those targets.

 

[Albert van der Horst]

int x = i5/i2;
if(x * i2 < i5)
x++;

I do this kind of thing all the time for math problems. http:/projecteuler.net/

Much faster is
i = (i5-1)/i2 + 1;

Or in stack pseudo code :
( i5 i2 -- ceil )
SWAP 1- SWAP / 1+

This works for all problems of this type.

 

[Ben Bacarisse]

I do this kind of thing all the time for math
problems. http:/projecteuler.net/

Much faster is
i = (i5-1)/i2 + 1;

Or in stack pseudo code :
( i5 i2 -- ceil )
SWAP 1- SWAP / 1+

This works for all problems of this type.

Except for negative numbers. I don't know if that matters to the OP,
but it might trip someone up using it as a general solution.

<snip>