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

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

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