21 Mar 1997 10:09:55 -0500

Related articles |
---|

Multiplication by a constant - how? Sergey.Solyanik@bentley.com (Sergey Solyanik) (1997-03-14) |

Re: Multiplication by a constant - how? rweaver@ix.netcom.com (1997-03-16) |

Re: Multiplication by a constant - how? harwood@trinidad.progress.com (1997-03-16) |

Re: Multiplication by a constant - how? d.sand@ix.netcom.com (Duane Sand) (1997-03-16) |

Re: Multiplication by a constant - how? harwood@trinidad.progress.com (1997-03-16) |

Re: Multiplication by a constant - how? dlmoore@ix.netcom.com (David L Moore) (1997-03-16) |

Re: Multiplication by a constant - how? preston@tera.com (1997-03-21) |

Re: Multiplication by a constant - how? torbenm@diku.dk (1997-03-21) |

Re: Multiplication by a constant - how? Sergey.Solyanik@bentley.com (Sergey Solyanik) (1997-03-27) |

Re: Multiplication by a constant - how? cdg@nullstone.com (Christopher Glaeser) (1997-03-31) |

Re: Multiplication by a constant - how? preston@cs.rice.edu (1997-04-02) |

From: | preston@tera.com (Preston Briggs) |

Newsgroups: | comp.compilers |

Date: | 21 Mar 1997 10:09:55 -0500 |

Organization: | /etc/organization |

References: | 97-03-062 97-03-092 |

Keywords: | arithmetic, optimize |

*>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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.