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

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
can I find such an algorithm or some references about this problem?


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]
--

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