Subj : Re: faster approach to division
To   : comp.programming
From : Alex Fraser
Date : Sat Jul 16 2005 02:42 am

"Peter Ammon" <gershwin@splintermac.com> wrote in message
news:G6ednUgy9aqqZUrfRVn-sQ@comcast.com...
[snip]
> I thought this sounded like a fun problem.  Here's the best I could come
> up with.  We assume two's complement signed integer representation, and
> that bit shifts are arithmetic (sign-extending).
>
> #define INT_BITS (sizeof(int) * CHAR_BIT)
>
> /* denominator in [-2, 2] excluding 0
>   * assume two's complement
>   * and sign-extending bitshifts */
> int divide(int numerator, int denominator) {
>    /*first construct mask, which is all 1s if
>     *denominator < 0 and all 0s if denominator > 0 */
>    int mask = denominator >> (INT_BITS - 1);
>
>    /*then construct isNegative, which is 1
>     * if denominator < 0 and 0 otherwise */
>    int isNegative = mask & 1;
>
>    /* flip the bits of numerator and add
>     * one if denominator is negative */
>    numerator = (numerator ^ mask) + isNegative;
>
>    /* abs(denominator) == 1 if the LSB
>     * is 1; if not, abs(denominator)==2 */
>    int absoluteValueIs2 = ~denominator & 1;
>
>    /* we need to know if the numerator is negative and odd
>     * the LSB of numeratorIsNegativeAndOdd will tell us */
>    int numeratorIsNegativeAndOdd = (numerator >> (INT_BITS - 1)) &
> numerator;
>
>    /* shift numerator right by one if denominator is 2 or -2 */
>    numerator >>= absoluteValueIs2;
>
>    /* and if numerator is negative and odd,
>     * add one so that the shift becomes division */
>    numerator += numeratorIsNegativeAndOdd & absoluteValueIs2;
>
>    return numerator;
> }

I wrote this earlier, it's very similar.

int divide(int dividend, int divisor) {
    int temp, shamt;

    /* if divisor is negative, negate dividend */
    temp = divisor >> 31;
    dividend = (dividend ^ temp) - temp;

    /* if dividend is negative and need shift, add 1 to dividend */
    shamt = ~divisor & 1;
    dividend += shamt & ((unsigned)dividend >> 31);
    return dividend >> shamt;
}

The remarkable thing (to me, at least) is that gcc (2.95.3 for x86) produced
the obvious translation of:
    temp = divisor >> 31;
    dividend = (dividend ^ temp) - temp;

Given the equivalent part in your code:
>    int mask = denominator >> (INT_BITS - 1);
>    int isNegative = mask & 1;
>    numerator = (numerator ^ mask) + isNegative;

Despite the different approach to fixing the rounding, the code ends up
basically the same complexity; yours compiles to one less "movl", no "shrl",
and one additional unusual instruction: "ctld" (sign extend EAX into
EDX:EAX).

Alex

.