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

## Tim Rentsch <txr@alumni.caltech.edu>

9 Nov 1997 12:16:14 -0500

*From comp.compilers*

| List of all articles for this month |

**From: ** | Tim Rentsch <txr@alumni.caltech.edu> |

**Newsgroups: ** | comp.compilers |

**Date: ** | 9 Nov 1997 12:16:14 -0500 |

**Organization: ** | Compilers Central |

**References: ** | 97-11-038 |

**Keywords: ** | arithmetic, optimize |

> 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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.