Re: Strength reduction of constant multipliers

cliffc@cs.rice.edu (Cliff Click) writes:


Although it is undoubtably obvious, no-one to my knowledge has remarked
that you can use Booth's algorithm for run's of ones of length>2. This
just uses the fact that 1...1 = 10...0 - 1 (Eg 111 = 1000-1) So you need
an add and a subtract per run, rather than an add per bit.


Of course, you have to be wary of overflow.


BTW, you can something neat with divides by a constant. Once again, you
have to be careful about overflow; it is most useful if you have double
length operations available. You simply take the reciprocal of the
constant, truncated at a point which will not cause any loss in result
accuracy, and do the mixed point multiply (that is, an integer multiply
followed by a right shift). I first saw this idea in Urs Amman's Pascal
compiler for the CDC 6600, where it was used for address calculation on
packed arrays.
--

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