Re: strength reduction of constant multiplication ?

macrakis@osf.org (Stavros Macrakis)
Mon, 12 Oct 1992 19:27:07 GMT

          From comp.compilers
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)
| List of all articles for this month |
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.