Subj : Re: faster approach to division
To   : comp.programming
From : Peter Ammon
Date : Fri Jul 15 2005 11:53 am

Gerry Quinn wrote:
> In article <db4oo5$fq5$1@grapevine.lcs.mit.edu>, cbarber@curl.com 
> says...
> 
> 
>>These only work if 'value' is non-negative. (e.g., right-shifting -1 will 
>>produce -1).
>>
>>To divide a signed value by 2, you need to write something like:
>>
>>  (value + ((unsigned)value >> 31)) >> 1
>>
>>but I wouldn't bother w/ stuff like this unless profiling shows that you need to.
> 
> 
> I think you could do much better in assembly than C.  I was thinking 
> about doing this without branching the other day, and I couldn't find a 
> way of doing it in C that wasn't clumsy.

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 benchmarked this against straight division and a case-based approach. 
  With gcc 4, the bitwise function above took .91 seconds, the 
case-based approach took 1.56 seconds, and the straight division took 
2.75 seconds.

Pretty interesting stuff.

-Peter

-- 
Pull out a splinter to reply.

.