Path: utzoo!mnetor!tmsoft!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!samsung!munnari.oz.au!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
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: <4763@goanna.cs.rmit.oz.au>
Date: 13 Feb 91 05:37:01 GMT
References: <21658@yunexus.YorkU.CA> <1991Feb12.233522.5195@Think.COM>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 32

In article <21658@yunexus.YorkU.CA> racine@yunexus.yorku.ca
wants to calculate
             \~
    a[j] = k*/_  c**((x[i]-x[j])**2),    for j=1..n
             i=1..n
for given k, c, x[].  Assembler is most unlikely to be any help at all,
because a large chunk of the time is spent inside exp(), which isn't
going to run any faster when you call it from assembler.  One thing
that *can* be done is to chop the time nearly in half by noting that
(x[i]-x[j])**2 = (x[j]-x[i])**2.  We can also optimise the i==j case,
as x[i]-x[j] = 0 then, hence c**(et cetera) = 1.0.

	register int i, j;
	register double t;

	for (j = 1; j <= n; j++) a[j] = 1.0;
	for (j = 1; j <= n; j++)
	    for (i = j+1; i <= n; i++) {
		t = x[i] - x[j];
		t = exp(t*t*con);	/* c**((x[i]-x[j])**2) */
		a[i] += t;
		a[j] += t;		/* symmetric! */
	    }
	for (j = 1; j <= n; j++) a[j] *= k;

This should do roughly half the work of the original code.
A good rule of thumb is:  FIRST look for algebraic identities that
can reduce the amount of computation you need, and only AFTER you
have done that should you even begin to think about hacking the code.

-- 
Professional programming is paranoid programming