Hi! I have to report average value of incoming numbers, how i could do that without using some sort of data structure to keep track of all values and then calculating average by summing them and dividing by number of values?
+1
A:
keep current sum and count. Update both on every incoming number.
avg = sum / count.
ob1
2010-06-02 08:39:13
It could be one simple solution, but i cant use this simple method because of limited precision of floating point numbers - i have huge count of numbers incoming every second so sum would become very large number and some floating point errors will occur...
Oscar
2010-06-02 08:44:42
@Oscar: you should specify this restriction in your question, then. As it stands, your question isn't very complicated!
Dan Puzey
2010-06-02 08:48:27
@Dan: That's a well-known problem with averaging floating-point numbers and should be considered nearly always when you sum large amounts of numbers.
Joey
2010-06-02 08:53:04
You can also keep current avg and count, and do new_avg = (old_avg*old_count + incoming) / (old_count + 1)
ob1
2010-06-02 08:55:24
@ob1: so you're doing exactly the same, just with an added multiplication.
Joey
2010-06-02 08:57:23
@Johannes: Oh, right ... oops :-)
ob1
2010-06-02 09:28:08
I know it's *well-known*, but the OP didn't specify anything about "large amounts" of numbers.
Dan Puzey
2010-06-02 12:07:05
+1
A:
Just keep running sum and how many numbers you have received, that's all you need to compute the average.
dcp
2010-06-02 08:39:24
+1
A:
If you have the numbers a[1] a[2] ... a[n] and you know their average is avg(n) = (a[1] + ... + a[n]) / n, then when you get another number a[n + 1] you can do:
avg(n + 1) = (avg(n) * n + a[n + 1]) / (n + 1)
Some floating point errors are unavoidable, but you should test this and see if it's good enough.
To avoid overflow, you could do the division first:
avg(n + 1) = (avg(n) / (n + 1)) * n + (a[n + 1] / (n + 1))
IVlad
2010-06-02 08:49:36
+1
A:
If I'm not totally mistaken, one could calculate the avg(n+1) also this way:
avg(n+1) = (a[1]+ ... + a[n+1]) / (n+1) =
= (a[1]+ ... + a[n])/(n+1) + a[n+1]/(n+1) =
= (n(a[1]+ ... + a[n])/n) / (n+1) + a[n+1]/(n+1) =
= n*avg(n) / (n+1) + a[n+1]/(n+1) =
= n/(n+1) * avg(n) + a[n+1]/(n+1)
so multiply the old avg by n/(n+1) and add the new element divided by n+1. Depending on how high n will get and how big your values are, this could reduce rounding errors...
EDIT: Of course you have to calculate n/(n+1) using floats, otherwise it will always render 0...
king_nak
2010-06-02 08:59:20
A:
you don't need to keep track the total sum, only counter:
class Averager {
float currentAverage;
size_t count;
float addData (float value) {
this->currentAverage += (value - this->currentAverage) / ++count;
return this->currentAverage;
}
}
from-> http://stackoverflow.com/questions/3316261/prevent-long-running-averaging-from-overflow
uray
2010-07-23 07:55:20