1 May 2005 01:59:58 -0400

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

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.