Re: Signed division with rounding towards -infinity (and floating point rounding)

[Jim Wilson <wilson at specifix dot com>]

Christopher Key wrote:
> The most concise form that I've found so far is:
> const int d = 8; // 16, 32 etc
> x = y / d - ((y % d < 0) ? 1 : 0)
> although this still produces rather longer code (see example below).

Any integer divide by constant can be replaced by a sequence of 
multiply, shift, and add instructions that produces the same result for 
all inputs.  There is a proof in a paper by Peter Montgomery and 
Torbjorn Granlund.  Because integer divide instructions are slow on most 
hardware, this is often a profitable optimization.  The same is true for 
the modulo operation.  So what you are seeing here are two sequences of 
instructions to compute divide/modulo results using multiply/shift/add.

Gcc is not able to simplify the two sequences further.  We would have to 
add code to recognize this sequence and handle it specially, and that 
isn't what you are asking for.

> On a similar point, is there a good way get floats rounded to the
> nearest integer value rather than truncated.  The following give the
> correct rounding behaviour (I'm only interested in +ve values),
> x = (int) (f + 0.5)
> although gets compiled as an addition of 0.5 followed by a truncation
> (again, see example).

Gcc has some builtin support for the lrint library function, however, 
only x86 supports this, and you have to use -ffast-math to get this 
optimization.

On an x86_64-linux system, compiling this testcase
long int lrint (double d);
long int sub (double d) { return lrint (d); }
with -O2 -ffast-math -S gives me
sub:
        cvtsd2siq       %xmm0, %rax
        ret
--
Jim Wilson, GNU Tools Support, http://www.specifix.com