Mon, 12 Oct 1992 19:27:07 GMT

Related articles |
---|

strength reduction of constant multiplication ? wu@sequent.com (Youfeng Wu) (1992-10-08) |

Re: strength reduction of constant multiplication ? preston@dawn.cs.rice.edu (1992-10-09) |

Re: strength reduction of constant multiplication ? macrakis@osf.org (1992-10-12) |

Newsgroups: | comp.compilers |

From: | macrakis@osf.org (Stavros Macrakis) |

Organization: | OSF Research Institute |

Date: | Mon, 12 Oct 1992 19:27:07 GMT |

Keywords: | arithmetic, theory |

References: | 92-10-036 |

Youfeng Wu <wu@sequent.com> writes:

...It is beneficial to replace the multiplication by a sequence of

[shift and add instructions]

...But I found out that for certain cases this algorithm is not

optimal. Do anyone know a reference on this subject?

Preston Briggs alluded to this, but to be more explicit: this problem is

very similar to the problem of computing powers with a minimal number of

multiplications. The big difference is that shift(i) usually costs the

same as shift(1). For a discussion of the power problem, in the form of

"addition chains", see Knuth's Art of Computer Programming vol 2

(Seminumerical Algorithms).

-s

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.