Subj : Re: faster approach to division
To   : comp.programming
From : Tim Rentsch
Date : Tue Jul 12 2005 05:20 pm

Mark P <not@my.real.email> writes:

> goose wrote:
> > Mark P wrote:
> > 
> >> I'm working on a problem which involves a fair amount of integer 
> >> division but in essentially all cases the divisor is +/- 1 or +/- 2. 
> >> I'm using C++ and trying to figure out whether I should code this as 
> >> just ordinary division or whether it makes sense to create a special 
> >> class (basically a wrapped enumeration) to hold my possible divisor 
> >> values.  Then I would overload operator/() to recast division as a 
> >> null operation or a sign flip and/or right shift.
> >>
> >> Anyone have any intuition on this?  I've tried a few very simple tests 
> >> comparing division and shifting and it's hard to discern a difference, 
> >> but I'm not sure my tests are very effective.  (Are modern machines 
> >> optimized to divide by 1 and 2 quickly?)
> >>
> >> Thanks for your advice,
> >> Mark
> > 
> > 
> > I've had need for something similar in the past, I've found
> > that the fastest way for me to do it was by #define a macro
> > to do the division.
> 
> 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.

Maybe this doesn't apply to your problem, but if it were me
I'd consider recasting the solution and writing

    x_over_f( x, ... )

and do the optimized division inside the body of x_over_f,
where x_over_f includes the same calculation that f does,
and also the division.  (I'm assuming that the calculation
inside x_over_f can identify the special values with no
extra work, or at least minimal extra work.)

All the above assuming that the performance of the division
here is essential to delivering a usable program.

.