7 Nov 1997 00:51:40 -0500

Related articles |
---|

Multiply by a constant --> shift-and-adds algorithm? Vincent.Lefevre@ens-lyon.fr (Vincent Lefevre) (1997-11-07) |

Re: Multiply by a constant --> shift-and-adds algorithm? rweaver@ix.netcom.com (1997-11-09) |

Re: Multiply by a constant --> shift-and-adds algorithm? preston@cs.rice.edu (1997-11-09) |

Re: Multiply by a constant --> shift-and-adds algorithm? ssolyanik@icdc.com (Sergey Solyanik) (1997-11-09) |

Multiply by a constant --> shift-and-adds algorithm? txr@alumni.caltech.edu (Tim Rentsch) (1997-11-09) |

Re: Multiply by a constant --> shift-and-adds algorithm? n8tm@aol.com (1997-11-11) |

Re: Multiply by a constant --> shift-and-adds algorithm? dube@brachio.IRO.UMontreal.CA (Danny Dube) (1997-11-11) |

[6 later articles] |

From: | Vincent Lefevre <Vincent.Lefevre@ens-lyon.fr> |

Newsgroups: | comp.compilers |

Date: | 7 Nov 1997 00:51:40 -0500 |

Organization: | Ecole Normale Superieure de Lyon, France |

Keywords: | arithmetic, theory, comment |

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]

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.