Re: Multiply by a constant --> shift-and-adds algorithm?

Danny Dube <dube@brachio.IRO.UMontreal.CA>
11 Nov 1997 14:34:18 -0500

          From comp.compilers

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)
Re: Multiply by a constant --> shift-and-adds algorithm? cdg@nullstone.com (Christopher Glaeser) (1997-11-13)
Re: Multiply by a constant --> shift-and-adds algorithm? ssolyanik@icdc.com (Sergey Solyanik) (1997-11-14)
Re: Multiply by a constant --> shift-and-adds algorithm? shankar@powertelglobal.com (Shankar Unni) (1997-11-15)
Multiply by a constant --> shift-and-adds algorithm? preston@tera.tera.com (1997-11-16)
Re: Multiply by a constant --> shift-and-adds algorithm? cdg@nullstone.com (Christopher Glaeser) (1997-11-18)
| List of all articles for this month |

From: Danny Dube <dube@brachio.IRO.UMontreal.CA>
Newsgroups: comp.compilers
Date: 11 Nov 1997 14:34:18 -0500
Organization: Universite de Montreal
References: 97-11-038
Keywords: arithmetic, optimize, bibliography

An algorithm that produces good sequences of instructions and that is
reasonably efficient is the one from Bernstein:


@Article{bernstein86,
    author = {Robert L. Bernstein},
    title = {Multiplication by Integer Constants},
    journal = {Software --- Practice and Experience},
    year = 1986,
    volume = 16,
    number = 7,
    month = {jul},
    pages = {641--652}
}


The algorithm doesn't produce an optimal sequence in general. Neither
did `gcc' when I checked it. So it may be the algorithm used in it.


--
                Danny Dubé
                dube@IRO.UMontreal.CA
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.