Re: [Bug-gsl] PATCH: faster gsl_stats_minmax()

[Brian Gough]

Martin Jansche writes:
 > I'm attaching a patch for a modified implementation of
 > gsl_stats_minmax() that uses fewer comparisons than the current
 > version. The idea (which appears in the Cormen et al. textbook on
 > algorithms) is to unroll the main loop, considering two elements in
 > each iteration. Then only the smaller of the two needs to be compared
 > against the minimum, and the larger against the maximum.  This saves
 > n/2 comparisons in total, compared with the current version.

Useful, I wasn't aware of that algorithm.

 > As an aside, it would be easy to modify this even further to deal with
 > NaNs by ignoring them. In the case of order statistics, it might make
 > sense to change the semantics so that max is an element from the input
 > array such that the array does not contain any element that is greater
 > than max. At the moment -- both in the current version and in this
 > patch -- the behavior is undefined if the array contains NaNs. Also,
 > it's not clear to me what should happen if n == 0.

Thanks for pointing that out - It is important to handle NaNs.  I
decided to fix it by returning NaN (or the corresponding index) if the
data contains NaN.  I think that is in the IEEE spirit (that any
operation involving a NaN gives a NaN result).  Can you adjust your
implementation to handle that?  Take a look at the latest checked in
version of minmax_source.c to see how I check for NaN.  You might want
to check whether it offers as much performance improvement then,
because the isnan will add some overhead.

-- 
Brian Gough

Network Theory Ltd,
Publishing Free Software Manuals --- http://www.network-theory.co.uk/