Division by constant in loop (Was: division vs multiplication)

Terje.Mathisen@hda.hydro.com (Terje Mathisen)Tue, 2 May 1995 07:12:41 GMT

From comp.compilers

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)
| List of all articles for this month |

 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