Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!hp4nl!dutrun!duteca!kooijman
From: kooijman@duteca (Richard Kooijman)
Newsgroups: comp.lang.c
Subject: Re: Execution time bottleneck: How to speed up execution?
Keywords: Execution time, would like to speed up. Alternatives?
Message-ID: <1221@duteca.UUCP>
Date: 13 Feb 91 10:41:43 GMT
References: <21658@yunexus.YorkU.CA>
Organization: Delft University of Technology, Netherlands
Lines: 44

racine@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;
>   }


exp ( a * b * c ) = exp (a) ^ (b * c) = pow ( exp(a), b * c) =
pow ( con2, b * c)


exp(a) with a=con makes a new constant con2 = exp(con), which only
has to be calculated once.
Although your C compiler should be smart enough to see it itself:
replace :  (x[i]-x[j])*(x[i]-x[j])  with : dummy = x[i]-x[j];
                                           dummy * dummy

This causes x[i]-x[j] to be evaluated only once.

The expression sum+= ... will now be as follows:

dummy = x[i] - x[j];
sum += pow ( con2, dummy * dummy );

Now, I hope that pow() works at least as fast as exp(), because otherwise
you wouldn't have speeded it up a lot, except for reducing the number of 
operations.

I can't see more optimizations, but maybe I look into some more later.


Richard.