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

Sergey Solyanik <ssolyanik@icdc.com>
9 Nov 1997 12:06:15 -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)
[2 later articles]
| List of all articles for this month |
From: Sergey Solyanik <ssolyanik@icdc.com>
Newsgroups: comp.compilers
Date: 9 Nov 1997 12:06:15 -0500
Organization: Bentley Systems, Inc.
References: 97-11-038
Keywords: arithmetic, optimize

Vincent Lefevre wrote:
>
> Some compilers (including gcc) are able to convert a "multiply by a
> constant" operation into a sequence of shifts and adds/subtracts.


The method I am using for our JIT compiler is memoizing dynamic
algorithm that uses a dag of best match sequences. I cannot share the
source code because it is commercial product, but I've put algorithm
description and compiled program (win32) that uses it at:


http://w3.icdc.com/~solyanik/decomp.html


This algorithm is a "smart brute force" (as any dynamic algorithm),
but it seems to work and it turned out to be fast enough for JIT
environment.


I would be very interested to seem smarter implementation.


Regards -


Sergey Solyanik
Software Developer
Bentley Systems, Inc
--

Post a followup to this message

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