Re: Multiplication by a constant - how?

>However, more complex forms are possible. For example: 10100101 can be
>done with a shift an add a second shift and another add whereas just
>taking runs of ones requires 3 shifts and 3 adds.
>
>So, to find an optimal sequence you have to look for repeated
>bit-patterns that can be extracted and handled all at once. I have
>never seen an optimal scheme for this either (obviously, you can try
>exhaustive enumeration).


A nice paper on the subject is


    title="Multiplication by Integer Constants",
    author="Robert L. Bernstein",
    journal=Software Practice and Experience
    volume=16,
    number=7,
    month=jul,
    year=1986,
    pages="641--652",


Has code, but with a couple of mistakes.


You can get a version I wrote up via anonymous ftp from cs.rice.edu,
in the directory public/preston/optimizer in the file multiply.ps.gz


Bernstein's techniques won't always find optimal code. One way around
the "problem" is to write a little program that exhaustively computes
optimal sequences and let it crunch for a long time. Where it does a
better job than the heuristic approaches, record the better approach
in a hash table. Then use the hash table and heuristic at compile
time.


Since most integer multipliers are pretty fast these days, you'll want
to always compare against that alternative. (i.e., use the multiplier
if it's faster)


Preston Briggs
--

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