# multiplication by constant - quick comparison of algorithms

## Youfeng Wu <wu@sequent.com>Wed, 21 Oct 1992 06:29:44 GMT

From comp.compilers

Related articles
Strength reduction of constant multipliers cliffc@cs.rice.edu (1992-10-13)
Re: Strength reduction of constant multipliers davidm@voltaire.rational.com (1992-10-14)
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: Youfeng Wu Organization: Compilers Central Date: Wed, 21 Oct 1992 06:29:44 GMT Keywords: arithmetic, optimize References: 92-10-057 92-10-069

For all numbers in [2, 10000], there is a total number of 64612 one's in
their binary represenations, and the following compares the total number
of add/sub/shift instructions used to perform all of the multiplications.

Cliff's Bernstein (Preston Briggs)
==========================================================
#insts 81751 70616
#insts/

Note: Cliff's algorithm generates many "shift by zero" and "add by zero"
instructions. The above numbers have already removed these nop
instructions.

It should be interesting to compare them when LEA instruction is allowed.
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/ I will summarize my approach in a later message.

Youfeng Wu
--

Post a followup to this message

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