Re: strength redcution (Danny =?iso-8859-1?q?Dub=E9?=)
1 May 2005 01:59:58 -0400

          From comp.compilers

Related articles
strength redcution (Vespasian) (2005-04-30)
Re: strength redcution (2005-05-01)
Re: strength redcution (glen herrmannsfeldt) (2005-05-01)
| List of all articles for this month |

From: (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 <> 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:


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é
[Seems like an awfully complicated way to do a modulo counter. -John]

Post a followup to this message

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