Re: Multiplication by a constant - how?

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

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