[Bug-gsl] PATCH: faster gsl_stats_minmax()

[Martin Jansche]

Hi Brian,

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.

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.

Regards,
-- mj

minmax.diff
Description: Text Data