Path: utzoo!mnetor!tmsoft!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!uunet!brunix!gvr
From: gvr@cs.brown.edu (George V. Reilly)
Newsgroups: comp.lang.c
Subject: Re: Execution time bottleneck: How to speed up execution?
Message-ID: <64745@brunix.UUCP>
Date: 13 Feb 91 05:41:32 GMT
References: <21658@yunexus.YorkU.CA> <1991Feb12.233522.5195@Think.COM>
	    <15884.27b919a3@levels.sait.edu.au>
Sender: news@brunix.UUCP
Reply-To: gvr@cs.brown.edu (George V. Reilly)
Organization: Brown University Department of Computer Science
Lines: 44


In article <1991Feb12.233522.5195@Think.COM>, barmar@think.com
(Barry Margolin) writes an excellent followup to Jeff Racine's
question about hand-optimizing a bottleneck in his code.

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

I second Barry's recommendation of Bentley's `Writing Efficient Programs'.

One additional suggestion: if you can make assertions about
	r = con * (x[i] - x[j]) * (x[i] - x[j])
such as r is an integer in the range 1 <= r <= 50 or 
r is a multiple of 0.125 in the range -3.75 <= r <= +7.875,
then you can precompute a table of all of the possible results.
Caveat: if r is a multiple of some number (e.g., 0.1) which
cannot be expressed as an exact binary fraction (assuming
binary FP hardware), then the results may be inaccurate.

In article <15884.27b919a3@levels.sait.edu.au> marwk@levels.sait.edu.au (Ray)
writes:

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

I can make no sense of this statement.  It's not equivalent to
the original code.
________________
George V. Reilly   `| Pas une pipe'	gvr@cs.brown.edu   +1 (401) 863-7684
uunet!brunix!gvr   gvr@browncs.bitnet	Box 1910, Brown U, Prov, RI 02912