Re: Multiplication by constants

Jeff Ledermann <lederman@dstc.qut.edu.au> writes:


>I recently picked up Preston Briggs and Tim Harvey's excellent
>paper "Multiplication by Integer Constants"
>(ftp://cs.rice.edu/public/preston/optimizer/multiply.ps.gz).
>I was interested to compare their more formal approach with
>the very simple heuristic I've been using in the GPM code
>generators with some success.


Everyone should understand that the little paper doesn't describe a
new approach; instead, it's simply an implementation (with an attempt
at an explanation) of Bernstein's approach


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


>Their algorithm includes a neat memoizing feature so that once an
>optimal factorization is found it never has to be calculated again
>(for that run). Extending the persistence leads to the (probably
>not terribly novel) approach of precalculating all factors (well up
>to some limit anyway), using brute force to find optimal sequences.
>
>Has anyone experience with this?


Perhaps David Chase will respond to this too.


First, remember that Bernstein's approach doesn't always find optimal
sequences. Thus, the memoization doesn't keep track of optimal
sequences, merely good sequences. Note also that it all intermediate
steps in the exploration are recorded, even if they don't turn out to
be useful for a particular problem. That way, if another problem can
use them, re-exploration will be avoided.


Given the memoization, it's possible to seed it with optimal
sequences. One way to do this is to write an exhaustive (offline)
algorithm that finds truly optimal sequences, and compares them to the
best sequences discovered by the heuristic approach. If, for some
number N, the heuristic approach turns out to be non-optimal, then
simply record the optimal sequence in the memo table. In this
fashion, you avoid the need to record every optimal sequence.


Preston Briggs


--

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