Subj : Re: faster approach to division
To   : comp.programming
From : Rob Thorpe
Date : Tue Jul 12 2005 03:57 am

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

As Walter says, benchmark it if you really need the speed.

Assuming you're targeting x86 machines: -

Pentium 4's have many cycles of latency in divide instructions, 56-70
is listed in the data I have.  Other microprocessors are slightly
better, Athlons are ~40 cycles.

Since you're dividing by small numbers you will probably hit the ~56
cycle end of the range on the P4, but there are no gaurantees.

If you can gaurantee you're always dividing by something no larger than
a byte then idiv becomes faster, on at least some x86 machines.

AFAICR Depending on the language you are using the compiler may or may
not be able to synthesis a small divide into shifts.  Because, in x86
signed-shifts have slightly different effects to division.

.