Execution time bottleneck: How to speed up execution?

[marwk at levels.sait.edu.au]

In article <21658 at yunexus.YorkU.CA>, racine at yunexus.yorku.ca (Jeff Racine) writes:
> Execution time query:
>
> I have the following nested loop in which I must sum (over all i), for each
> x[j], e raised to the power x[i]-x[j] squared (times a constant).
>
> This section of the program is of order n-squared (i.e. execution time
> increases at the rate of the number of observations squared).
>
>    for (j=1; j <= n; j++) {
>       sum = 0.0;
>       for (i=1; i<= n; i++) {
>          sum += exp( con * (x[i]-x[j]) * (x[i]-x[j]) );
>       }
>       a[j] = k*sum;
>    }
>
> This part of the algorithmn is a bottleneck. I want to make this as
> quick as possible. What are my options? I have heard that assembler
> would be faster. How much faster would assembler be? Would it be worth
> the effort? Are there other alternatives that you can see?  Any
> improvement would be welcome.
>
> Any help would be greatly appreciated. Thanks for your time and effort.
>
>
> --------------------------------------------------------------------

There are some redundant calculations here:

(1) rewrite the sum as Sum = 2 * S{i=1,i=n-1} S{j=i+1,j=n} f(i,j)

    this cuts the number of calculations in half.

(2) x(i) - x(j) is being calculated twice in the inner loop.

    store these differences in a variable in the inner loop,
    then square this var.

    On a MAC fx with a 68882 this will make little difference, but
    with a PC and 80287 this will provide a noticable increase in speed.

(3) make the loop variables 'register int'

(4) if allowed make x[] a register variable too.
               and the difference variable.

    else make them global variables.

(5) if possible make n a #defined constant rather than a variable.

I would not bother with assembler unless you can make better use of
the registers than the compiler, or you have very fast real multiplication,
difference and exponential routines you can use.

There may be other improvements, but I cannot think of any nmore at the
moment.

Ray
--
University of South Australia   | Plus ca change, plus c'est la meme chose.
P.O. Box 1                      | Ghing thien me how, ming thien gung me how.
Ingle Farm                      | Knobs, knobs everywhere,
South Australia                 |              just vary a knob to think!