Fri, 28 Apr 1995 19:26:55 GMT

Related articles |
---|

[10 earlier articles] |

Re: Q: division vs multiplication jmccarty@spdmail.spd.dsccc.com (1995-04-18) |

Re: Q: division vs multiplication leichter@zodiac.rutgers.edu (1995-04-11) |

Re: Q: division vs multiplication kptben@aol.com (1995-04-17) |

Re: Q: division vs multiplication pcg@aber.ac.uk (1995-04-17) |

Re: Q: division vs multiplication gsc@magna.com.au (1995-04-18) |

Re: Q: division vs multiplication jbuck@Synopsys.COM (1995-04-28) |

Re: Q: division vs multiplication davidm@flora.Rational.com (1995-04-28) |

Re: Q: division vs multiplication Roger@natron.demon.co.uk (Roger Barnett) (1995-04-28) |

Re: Q: division vs multiplication jmccarty@spdmail.spd.dsccc.com (1995-04-29) |

Division by constant in loop (Was: division vs multiplication) Terje.Mathisen@hda.hydro.com (1995-05-02) |

Newsgroups: | comp.compilers |

From: | davidm@flora.Rational.com (David Moore) |

Keywords: | arithmetic |

Organization: | Rational Software Corp |

References: | 95-04-080 95-04-126 |

Date: | Fri, 28 Apr 1995 19:26:55 GMT |

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?

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.