[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Brian Gough
Subject: Re: [Bug-gsl] PATCH: faster gsl_stats_minmax()
Date: Sat, 7 Jan 2006 19:01:24 +0000

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/

reply via email to

[Prev in Thread] Current Thread [Next in Thread]