Re: Strength reduction of constant multipliers

davidm@voltaire.rational.com (David Moore)
Wed, 14 Oct 1992 21:06:27 GMT

          From comp.compilers

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)
| List of all articles for this month |

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.