16 Mar 1997 23:41:50 -0500

Related articles |
---|

Multiplication by a constant - how? Sergey.Solyanik@bentley.com (Sergey Solyanik) (1997-03-14) |

Re: Multiplication by a constant - how? rweaver@ix.netcom.com (1997-03-16) |

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

From: | David L Moore <dlmoore@ix.netcom.com> |

Newsgroups: | comp.compilers |

Date: | 16 Mar 1997 23:41:50 -0500 |

Organization: | Netcom |

References: | 97-03-062 |

Keywords: | arithmetic, optimize |

Sergey Solyanik wrote:

*>.Does anybody*

*> know what algorithm is used and where can I look for information?*

John remarks:

*> [In the computer theory biz this topic is known as addition chains. I know*

*> lots of heuristics but no general optimal scheme. -John]*

To expand:

The simplest form is booth's algorithm in which each chain of 1's

produces a shift, and add, a shift and a subtract, using the fact that

1..(n times)..1 is equal to 2^n-1.

However, more complex forms are possible. For example: 10100101 can be

done with a shift an add a second shift and another add whereas just

taking runs of ones requires 3 shifts and 3 adds.

So, to find an optimal sequence you have to look for repeated

bit-patterns that can be extracted and handled all at once. I have

never seen an optimal scheme for this either (obviously, you can try

exhaustive enumeration).

These days the question is rather moot since most hardware can do a

general integer multiply in a few cycles. Notice that the code the

Microsoft compiler is generating cannot be multi-way issued, which is

likely to be bad on many current chips.

If integer multiply is slow, you can often get better speed by using

your floater to do the integer multiply rather than expanding it out

into a long chain of shifts and multiplies. Provided you have denorms

turned on, this is only two register moves, a multiply, and a small

number of mask and shift operations. It is even faster if you can turn

off normalization, although I don't know of any current hardware that

will allow this on an instruction by instruction basis.

If either of these is true, only short add and shift sequences gain any

advantage.

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.