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?


A good place to start, if one is interested in understanding the
problem rather than just getting an algorithm, is Knuth (Art of
Computer Programming, what else?). Somewhere in AOCP (forgive me, I
don't recall which volume even) he has a long discussion of "addition
chains", which is basically the same problem except limited to just
additions rather than adds, subtracts, and shifts. He outlines an
approach that finds optimal sequences; although no algorithm is given,
I would say the outline is enough for an enterprising graduate student
to construct a program.


If I recall correctly, this is under Combinatorial Algorithms, but I
don't have the books handy just now.
[It's in section 4.6.3, "Evaluation of Powers", in Volume 2. -John]


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


Yes, considering the amount of time Knuth spends discussing just the
simpler problem. His approach for addition chains, however, should be
reasonably straightforward -- I did not say easy! -- to generalize to
the add-subtract-shift chains, in which case the algorithm to include
in a compiler is any of the good heuristics, plus a small (I hope)
exception table that is pre-tabulated by the longer-running optimal
sequence generator.


regards,


Tim Rentsch




--

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