Subj : Re: faster approach to division
To   : comp.programming
From : Christopher Barber
Date : Thu Jul 14 2005 01:12 am

Willem wrote:
> Willem wrote:
> ) Mark wrote:
> ) ) I assume then that the divisor was known to you at compile time.  My 
> ) ) situation is more like: x / f(...) where f(...) will always return +/-1 
> ) ) or +/-2, determined at run time.
> )
> ) *always* ?
> )
> ) In that case, I guess you can come up with something faster,
> ) but you need to think beyond 'if' statements.
> )
> ) there may be some bit twiddling trick.
> 
> For example, in C:
>   result = value >> (divisor - 1);
> Will work for division by 1 and 2.
> 
> And:
>   result = (value >> ((divisor - 1) & 1)) * ((divisor >> 2) | 1);
> Will work for division by +1, +2, -1 and -1.
> 
> I'm not sure I worked it out correctly, nor am I sure these are the fastest
> methods, and I'm not even entirely sure it will beat straight division,
> but it should at least give you an idea what you could try.

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.

- Christopher

.