Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!samsung!think.com!paperboy!hsdndev!cmcl2!adm!smoke!gwyn
From: gwyn@smoke.brl.mil (Doug Gwyn)
Newsgroups: comp.lang.c
Subject: Re: Execution time bottleneck: How to speed up execution?
Message-ID: <15178@smoke.brl.mil>
Date: 13 Feb 91 21:03:23 GMT
References: <21658@yunexus.YorkU.CA>
Organization: U.S. Army Ballistic Research Laboratory, APG, MD.
Lines: 29

In article <21658@yunexus.YorkU.CA> racine@yunexus.yorku.ca (Jeff Racine) writes:
>   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.

Conversion to assembler would not help much, since the majority of
the time is spent in evaluating the exponential function.  There are
some simple rearrangements that would help substantially, however:
	(1)  Factor out the e^con and fold it into the "k" multiplier.
	(2)  If your compiler is not highly optimizing, introduce a
	register double variable into which x[i]-x[j] is stored, then
	mutliply that temporary by itself to produce the argument to
	exp().
	(3)  Consider precomputing the matrix exp((x[i]-x[j])^2), which
	is symmetric, so you need only compute a little more than half
	the [i,j] combinations.
If this is being used for some sort of matching procedure with integral
x[.] values, you might also consider using an information-statistics
procedure using n*log(n) terms instead; such terms can be precomputed
(or dynamically computed and cached) for a gain in efficiency.