# Multiply by a constant --> shift-and-adds algorithm?

## Vincent Lefevre <Vincent.Lefevre@ens-lyon.fr>7 Nov 1997 00:51:40 -0500

From comp.compilers

Related articles
Multiply by a constant --> shift-and-adds algorithm? Vincent.Lefevre@ens-lyon.fr (Vincent Lefevre) (1997-11-07)
Re: Multiply by a constant --> shift-and-adds algorithm? rweaver@ix.netcom.com (1997-11-09)
Re: Multiply by a constant --> shift-and-adds algorithm? preston@cs.rice.edu (1997-11-09)
Re: Multiply by a constant --> shift-and-adds algorithm? ssolyanik@icdc.com (Sergey Solyanik) (1997-11-09)
Multiply by a constant --> shift-and-adds algorithm? txr@alumni.caltech.edu (Tim Rentsch) (1997-11-09)
Re: Multiply by a constant --> shift-and-adds algorithm? n8tm@aol.com (1997-11-11)
Re: Multiply by a constant --> shift-and-adds algorithm? dube@brachio.IRO.UMontreal.CA (Danny Dube) (1997-11-11)
[6 later articles]
| List of all articles for this month |

 From: Vincent Lefevre Newsgroups: comp.compilers Date: 7 Nov 1997 00:51:40 -0500 Organization: Ecole Normale Superieure de Lyon, France Keywords: arithmetic, theory, comment

Some compilers (including gcc) are able to convert a "multiply by a
constant" operation into a sequence of shifts and adds/subtracts. I
don't know whether or not they find the optimal solution, but after
a few tests, the algorithm used by gcc seems to be quite good. Where

Note: the sequence giving the minimum number of required operations
(shift or add or subtract) as a function of the constant is in Sloane's
Encyclopedia of Integer Sequences (A008342), but there is no reference
(except the author's e-mail, that is no longer valid).

--
Vincent Lefevre <vlefevre@ens-lyon.fr>
WWW: http://www.ens-lyon.fr/~vlefevre/
PhD st. in Computer Science, 2nd year
[This has come up before. As I recall, it's not hard to invent
heuristics that do pretty well, but it's extremely hard to generate
optimal code. -John]
--

Post a followup to this message