Wed, 14 Oct 1992 21:06:27 GMT

Related articles |
---|

Strength reduction of constant multipliers cliffc@cs.rice.edu (1992-10-13) |

Re: Strength reduction of constant multipliers sastdr@unx.sas.com (1992-10-14) |

Re: Strength reduction of constant multipliers sastdr@unx.sas.com (1992-10-15) |

Strength reduction of constant multipliers cliffc@cs.rice.edu (1992-10-15) |

Re: Strength reduction of constant multipliers davidm@voltaire.rational.com (1992-10-14) |

Re: Strength reduction of constant multipliers preston@dawn.cs.rice.edu (1992-10-20) |

Constant divisions, remainders rutt@paradise.mti.sgi.com (1992-10-20) |

multiplication by constant - quick comparison of algorithms wu@sequent.com (Youfeng Wu) (1992-10-21) |

Re: Constant divisions, remainders Cheryl_Lins@gateway.qm.apple.com (Cheryl Lins) (1992-10-21) |

Newsgroups: | comp.compilers |

From: | davidm@voltaire.rational.com (David Moore) |

Organization: | Rational |

Date: | Wed, 14 Oct 1992 21:06:27 GMT |

References: | 92-10-057 |

Keywords: | arithmetic, optimize |

cliffc@cs.rice.edu (Cliff Click) writes:

Although it is undoubtably obvious, no-one to my knowledge has remarked

that you can use Booth's algorithm for run's of ones of length>2. This

just uses the fact that 1...1 = 10...0 - 1 (Eg 111 = 1000-1) So you need

an add and a subtract per run, rather than an add per bit.

Of course, you have to be wary of overflow.

BTW, you can something neat with divides by a constant. Once again, you

have to be careful about overflow; it is most useful if you have double

length operations available. You simply take the reciprocal of the

constant, truncated at a point which will not cause any loss in result

accuracy, and do the mixed point multiply (that is, an integer multiply

followed by a right shift). I first saw this idea in Urs Amman's Pascal

compiler for the CDC 6600, where it was used for address calculation on

packed arrays.

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.