Re: strength redcution

Vespasian <julie.spicer@verizon.net> writes:
> Anyone know how to replace the expression,
>
> i div c,
>
> with addition and/or subtraction, where c in a constant and
> i is the index of a loop that increments with a step size of 1
> [Seems to me you'd have to keep a separate counter and each time
> that counter reached c, add one to the quotient value and reset
> the counter. -John]


The following paper may present a solution to your problem:


                http://citeseer.ist.psu.edu/granlund94division.html


The authors explain how to replace the expression:


                i div c


where c is a constant by an equivalent expression:


                (i * t) div (2 ^ k)


where t and k are constants. The benefits come from the fact that a
division by a power of 2 can be simulated (on most machines) using a
shift of the bits to the right, which turns the expression into:


                (i * t) >> k


What is particularly interesting in your case is that i is an
induction variable and the value of i div c is easy to update when i
is incremented. The update can be done using only an addition and a
shift. You need to introduce a temporary variable x which holds the
current value of i * t. When i is initialized to V, you need to
initialize x to V * t. Each time i is incremented, you add t to x.
Then the current value of the quotient can be obtained by computing
x >> k.


Note that you have to be careful because, in worst case, you need to
perform the replacement computations in n+1 bits in order to correctly
simulate the division in n bits.


--
                Danny Dubé
                Danny.Dube@ift.ulaval.ca
[Seems like an awfully complicated way to do a modulo counter. -John]

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