# Re: strength redcution

## Danny.Dube@ift.ulaval.ca (Danny =?iso-8859-1?q?Dub=E9?=)1 May 2005 01:59:58 -0400

From comp.compilers

Related articles
strength redcution julie.spicer@verizon.net (Vespasian) (2005-04-30)
Re: strength redcution Danny.Dube@ift.ulaval.ca (2005-05-01)
Re: strength redcution gah@ugcs.caltech.edu (glen herrmannsfeldt) (2005-05-01)
| List of all articles for this month |

 From: Danny.Dube@ift.ulaval.ca (Danny =?iso-8859-1?q?Dub=E9?=) Newsgroups: comp.compilers Date: 1 May 2005 01:59:58 -0400 Organization: Compilers Central References: 05-04-097 Keywords: optimize Posted-Date: 01 May 2005 01:59:58 EDT

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]

Post a followup to this message