Subj : Re: faster approach to division
To   : comp.programming
From : Peter Ammon
Date : Sat Jul 16 2005 01:31 am

Alex Fraser wrote:
> "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;

That's pretty interesting.  gcc 3.3 and gcc 4 on the PowerPC were not 
able to produce that transformation, and your code generated two fewer 
instructions.

I thought your re-use of the bitmask as the value -1 was very clever. 
I'll have to remember that one.

> 
> 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

Your idea to always add one if a shift is necessary is also quite 
clever.  Wish I'd thought of that!

-Peter


-- 
Pull out a splinter to reply.

.