Re: Q: division vs multiplication

kptben@aol.com (KPT Ben) writes:
> martens@cis.ohio-state.edu (Jeff Martens) wrote:
>
> On the PPC, you can divide any signed 32-bit integer by 2^n by using (in
> PPC assembly):
> ....


A general way to do integer divides by constants is to take the
reciprocal of the constant as a fixed point number ( keeping just the
fractional part) and doing a multiply - just keeping the top half of
the result.


For example, if you have 32 bit values, divide the divisor into
0x100000000 to get the reciprocal and then multiply by this value.


The PowerPC has a "muls" instruction which can be used for this.
So you can do any positive/(positive constant) divide in the 5 cycles
it takes for a multiply.


You need to be careful about signs - I forget the details but
they are easy enough to work out, and various machines will
allow various fast tricks.


Even if you do not have a 32*32 bit => top half of 64 bit multiply
available, you can use this for numbers that are adequately small,
using a standard integer multiply and a shift.




See my article on the AM29000 in Doctor Dobb's (Jan 92) or Urs
Amman's Pascal compiler for the CDC 6600 for examples (I stole the
idea from him) It was very valuable on the CDC 6600 because the
machine was (60 bit) word addressable and this trick allowed access
to packed arrays reasonably quickly. Urs Amman's code contains the
details of working out how many bits are needed to the right of the
implied binary point, although this is also easy enough to derive for
oneself. [Of course, the array index is assumed to be fair]


----------------------------------------------------------------------
While we are on the subject of divides, has anyone ever found it
useful to do the following:


Suppose we have a loop induction variable which is divided by a
constant value:


for i in 1..N loop
a(i/3):=a(i/3)+b(i);
end loop;


We could apply Bresenham's algorithm here providing N can be bounded
adequately, so that each time round the loop we do an add and a shift
to get i/3.


It is a simple enough optimization to implement, but I have my doubts
that it is actually useful. Any comments?
--

Return to the comp.compilers page.
Search the comp.compilers archives again.