- Forum
- General C++ Programming
- Standard Deviation without arrays the Do
Standard Deviation without arrays the Donald Knuth method
So. For a project we are supposed to write a file that reads a file containing numbers then determine the data set's mean, minimum, maximum, and standard deviation. Not so bad, right? No. We cannot implement arrays for the standard deviation. Instead we are supposed to use a method mentioned by Donald Knuth in The Art of Computer Programming using recurrence. It explains what to do in the assignment, but I cannot make heads or tail of it. I know how to do everything else, I just don't understand how to get the standard deviation this way. I even understand the math and logic behind it, but it asks for subscripts and it goes over my head. Here are the outlined steps for standard deviation:
Step 1: Initialize 𝑚0 = 𝑥1, 𝑠0 = 0, and 𝑘0 = 1. Here, 𝑥1 is our first sample point, or the first number in
the file.
Step 2: Every time we read a new value, “x”, we increment “k”, and we we update “m” and “s” using the
rules below. Be very careful with the subscripts! When we update s, we need both the current mean AND
the previous one.
𝑚𝑘 = 𝑚𝑘−1 + (𝑥 – 𝑚𝑘−1)/𝑘
𝑠𝑘 = 𝑠𝑘−1 + (𝑥 – 𝑚𝑘−1) ∗ (𝑥 – 𝑚𝑘)
Step 3: When we want the standard deviation (after we have read all of the numbers in the file), we
calculate it using the following equation:
𝜎 = √
𝑠
𝑘 − 1
I'm not asking for anyone to do this for me, just explain how to write this the way it's required. Or walk me through it. Thanks in advance!
Step 1: Initialize 𝑚0 = 𝑥1, 𝑠0 = 0, and 𝑘0 = 1. Here, 𝑥1 is our first sample point, or the first number in
the file.
Step 2: Every time we read a new value, “x”, we increment “k”, and we we update “m” and “s” using the
rules below. Be very careful with the subscripts! When we update s, we need both the current mean AND
the previous one.
𝑚𝑘 = 𝑚𝑘−1 + (𝑥 – 𝑚𝑘−1)/𝑘
𝑠𝑘 = 𝑠𝑘−1 + (𝑥 – 𝑚𝑘−1) ∗ (𝑥 – 𝑚𝑘)
Step 3: When we want the standard deviation (after we have read all of the numbers in the file), we
calculate it using the following equation:
𝜎 = √
𝑠
𝑘 − 1
I'm not asking for anyone to do this for me, just explain how to write this the way it's required. Or walk me through it. Thanks in advance!
Would you mind telling me which Donald Knuth book and which page number.
Idk what level CS course you are taking, but the fact that you actually get to study Donald Knuth for class is kinda cool. We would never do that in our system - Knuth is not textbooky enough.
Idk what level CS course you are taking, but the fact that you actually get to study Donald Knuth for class is kinda cool. We would never do that in our system - Knuth is not textbooky enough.
| This algorithm is due to Knuth,[5] who cites Welford,[6] .. 5. Donald E. Knuth (1998). The Art of Computer Programming, volume 2: Seminumerical Algorithms, 3rd edn., p. 232. Boston: Addison-Wesley. 6. B. P. Welford (1962)."Note on a method for calculating corrected sums of squares and products". Technometrics 4(3):419–420. https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance |
Topic archived. No new replies allowed.