Re: Multiplication by a constant - how?

Sergey Solyanik <Sergey.Solyanik@bentley.com>
27 Mar 1997 13:18:07 -0500

          From comp.compilers

Related articles
[2 earlier articles]
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)
| List of all articles for this month |

From: Sergey Solyanik <Sergey.Solyanik@bentley.com>
Newsgroups: comp.compilers
Date: 27 Mar 1997 13:18:07 -0500
Organization: BSI
References: 97-03-062 97-03-092 97-03-114
Keywords: arithmetic

Preston Briggs wrote:
>
> title="Multiplication by Integer Constants",


I will take a look, thank you.


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


I've done it with memoizing algorithm that tries and builds a tree of
numbers/decompositions. It produces EXACTLY the same sequence as
Visual C compiler. When I ran it for all 32K numbers, the longest
sequence was 11 operations. By the way, with memoization it really
runs very fast - factoring all 32K numbers took well under half a
minute.


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


Yes and no. Not always. On Intel you have to reserve EAX+EDX for mul/imul,
but this forces my register allocator to become non-symmetrical, and forces
it sometimes spill when it should not. Multiplication with shifts can be
done in usually one, sometimes two arbitrary registers.


Regards --


Sergey.Solyanik@bentley.com
--


Post a followup to this message

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