   standard deviation
  Hi,   I need a quick approximation of the standard deviation of a list of data.As i do not need an accurate calculation, I was wondering if I can do that faster then the usual algorithm for standard deviation calculation. Like, in one pass over the array of data?are there some algorithms around for that?regards   
  If you have a lot of data, then you can approximate it as such:double sum = 0.0, sumsq = 0.0;foreach (double i in values) {  sum += i;  sumsq += i*i;}double avg = sum / (double)n.Length;double sqavg = sumsq / (double)n.Length;return Math.Sqrt(sqavg - avg * avg);;  One pass that does twice the work per piece of data isn't much better than two passes that do half the work, is it?However, if you have a large list of data that's randomly distributed, so that there is no tendency for high or low values to appear at the start more so than later, or values closer or further from the average to appear at the start, you could estimate the standard deviation using the usual or "single-pass" calculation, but only using part of the data.  Using more data gives a better estimate, but the improvement for each additional sample decreases as the number of samples increases.   ;Quote:Original post by Geoff the MedioOne pass that does twice the work per piece of data isn't much better than two passes that do half the work, is it?Actually, it could be. Doing more work in a single pass gives the CPU opportunities to parallelize instructions, and it only needs to read from memory once. Reading from memory is expensive if the whole thing doesn't fit in the cache.In a quick test on my Mac, it seems the single-pass solution is almost twice as fast.#include <iostream>#include <cstdlib>#include <ctime>#include <vector>#include <cmath>#include <sys/time.h>double standard_deviation(double const *data, unsigned n){  double sum=0.0;  for(unsigned i=0;i<n;++i){    double x=data;    sum+=x;  }  double avg = sum/n;    double sum2=0.0;  for(unsigned i=0;i<n;++i){    double x=data-avg;    sum2+=x*x;  }  double avg2 = sum2/n;    return std::sqrt(avg2);}double standard_deviation_fast(double const *data, unsigned n){  double sum=0.0;  double sum2=0.0;  for(unsigned i=0;i<n;++i){    double x=data;    sum+=x;    sum2+=x*x;  }  double avg = sum/n;  double avg2 = sum2/n;    return std::sqrt(avg2 - avg*avg);}double now(){  struct timeval tp;  gettimeofday(&tp,0);  return tp.tv_sec+.000001*tp.tv_usec;}int main(){  std::srand(std::time(0));  std::vector<double> v;    v.reserve(100000000);  for(unsigned i=0;i<100000000;++i)    v.push_back(double(std::rand())/RAND_MAX);  double start = now();  double stddev = standard_deviation(&v[0], v.size());  double elapsed = now() - start;  double start_fast = now();  double stddev_fast = standard_deviation_fast(&v[0], v.size());  double elapsed_fast = now() - start_fast;  std::cout << "2 pass: " << elapsed << " (" << stddev << ")\n";  std::cout << "1 pass: " << elapsed_fast << " (" << stddev_fast << ")\n";}The results are this:2 pass: 0.382032 (0.288661)1 pass: 0.196705 (0.288661)EDIT: It should be noted that the single-pass solution is less precise and you can end up with a negative estimate for the variance, because of rounding errors. Example: (1.0000000000006472 1.0000000000001552 1.0000000000004842 1.0000000000001321) with doubles   ;  Thanks a lot all three of you for your help.Actually I have to do calculations on the GPU. On there, memory access and loops are expensive. Storing large data is another issue, and in my application an approximation would do good enough.thanks again   ;  Trying to average more than a thousand values with a 32-bit precision (like the one present on a GPU) will result in wild losses of precision. When I was doing Monte Carlo simulation in GPGPU, I had to move the entire averaging process back to the CPU to get a precision that wasn't laughable. If you can afford an approximation (as opposed to a loss of precision through rounding errors), you should consider polling a few values out of the entire data set instead of trying to optimize a global process.   ;  thanks for the advice. I have another question and let me ask it here.If I have a minimum, maximum, mean and standard deviation of some data available. Can I extract a box plot out of it?Box plot usually requires minimum, maximum, median, lower quartile and upper quartile for plotting.In short, can we find quartiles of the dataset from mean and standard deviation?regards   ;Quote:Original post by me_here_meIn short, can we find quartiles of the dataset from mean and standard deviation?No.   