# Re: multiplication by constant - quick comparison of algorithms

## preston@helena.cs.rice.edu (Preston Briggs)Wed, 21 Oct 1992 21:43:58 GMT

From comp.compilers

Related articles
Strength reduction of constant multipliers cliffc@cs.rice.edu (1992-10-13)
multiplication by constant - quick comparison of algorithms wu@sequent.com (Youfeng Wu) (1992-10-21)
Re: multiplication by constant - quick comparison of algorithms preston@helena.cs.rice.edu (1992-10-21)
Re: multiplication by constant - quick comparison of algorithms bgb@iexist.att.com (1992-10-25)
Re: multiplication by constant - quick comparison of algorithms chased@rbbb.Eng.Sun.COM (1992-10-27)
Re: multiplication by constant - quick comparison of algorithms joe@babel.ho.att.com (1992-10-28)
| List of all articles for this month |

 Newsgroups: comp.compilers From: preston@helena.cs.rice.edu (Preston Briggs) Organization: Rice University, Houston Date: Wed, 21 Oct 1992 21:43:58 GMT References: 92-10-057 92-10-079 Keywords: arithmetic, optimize

Youfeng Wu <wu@sequent.com> writes:
>By allowing the following LEA instructions:
>
> LEA( b, i, s ) = b + i << s, where s = 1, 2, or 3
>
>I have an algorithm that achieves:
>
>#insts 53670
>#insts/
>
>The question is how we can push the ratio of #insts/

Well, obviously we can improve the ratio by allowing more powerful
instructions! For example, simply allowing s to equal 1, 2, 3, or 4 will
shorten some sequences. Arbitrary shifts and 3-operand add instructions
would shorten other sequences.

It would probably be more interesting to determine what constant integer
multiplies actually occur and make sure those are handled well. For
example, even the simplest techniques handle *4 and *8 (arising commonly
when accessing arrays of single and double-precision floats) perfectly.

The explicit case of the LEA mentioned above has been explored at
Hewlett-Packard (I gave the reference a while ago). They describe a
rule-based approach that finds optimal sequences quickly for all numbers
less than 10,000 (with 12 exceptions, handled in a little table). Note
that it's much easier to explore the exponential search space in this case
since the shifts are limited to 1, 2, or 3. Of course, I'd still do such
exploring offline!

I've done a little exponential searching (overnight) for optimal sequences
of adds, subtracts, and arbitrary left shifts. For the integers between 1
and 1000, Bernstein's algorithm requires a total of 5512 cycles whereas
the optimal sequences require only 5039.

Preston Briggs
--

Post a followup to this message