Comment by pvillano
10 days ago
To be pedantic, median is cheaper than sorting. O(n) with a quicksort-like algorithm.
Also, if you're taking an average of floating point numbers, you might want to sort it first and add from smallest to largest, to better preserve precision
An aside, but I recently learned -- if one is willing to use a very modest amount of memory -- summing floating-point numbers with no loss of precision is effectively a solved problem with the XSUM algorithm.
https://glizen.com/radfordneal/ftp/xsum.pdf
That paper explains some useful optimisation details, but obviously since the floats are all (either infinity or) some multiple of a known tiny fraction (their smallest non-zero number), we can definitely sum them accurately.
Not if the ratio between the largest and smallest floats is very large (2^(2^n)) where n is the number of bits in the exponent.
3 replies →
That’s great for mean, but you don’t need to sort for mean.