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

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