Tue, 2 May 1995 07:12:41 GMT

Related articles |
---|

Re: Q: division vs multiplication martens@cis.ohio-state.edu (1995-04-16) |

Re: Q: division vs multiplication davidm@flora.Rational.com (1995-04-28) |

Division by constant in loop (Was: division vs multiplication) Terje.Mathisen@hda.hydro.com (1995-05-02) |

Newsgroups: | comp.compilers |

From: | Terje.Mathisen@hda.hydro.com (Terje Mathisen) |

Keywords: | optimize, design |

Organization: | Hydro Data, Norsk Hydro (Norway) |

References: | 95-04-080 95-04-162 |

Date: | Tue, 2 May 1995 07:12:41 GMT |

davidm@flora.Rational.com (David Moore) writes:

[snip]

*>While we are on the subject of divides, has anyone ever found it*

*>useful to do the following:*

*>*

*>Suppose we have a loop induction variable which is divided by a*

*>constant value:*

*>*

*> for i in 1..N loop*

*> a(i/3):=a(i/3)+b(i);*

*> end loop;*

*>*

*>We could apply Bresenham's algorithm here providing N can be bounded*

*>adequately, so that each time round the loop we do an add and a shift*

*>to get i/3.*

I _hope_ I never find a programmer writing code like that, but if I do,

I'd say it would be much better to unroll the inner loop enough times to

get rid of the division:

for (i = 1;(i < 3) && (i < N); i++) {

a[0] += b[i];

}

for (j = 1; i < N-2; j++, i+=3) {

a[j] += b[i] + b[i+1] + b[i+2];

}

while (i < N) {

a[j] += b[i];

i++;

}

This version will reduce the number of accesses to the destination array

by a factor of three, which will tend to (at least) double the speed of

the code, besides the speedup from getting rid of all the divisions.

-Terje Mathisen (include std disclaimer) <Terje.Mathisen@hda.hydro.com>

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.