The usual algorithms for computing variance and standard deviation work on the full data set. What if you have a time series and want the standard deviation for a moving window? You could do the computation from fresh every time the window is advanced, but surely there’s a better way.
Category Archives: Mathematics
The Number With Negative Absolute Value
As you know, computers internally work only with ones and zeros, and everything is represented in some way using these “bits.” Using M bits you can encode 2M different values. Let’s say you’re interested in encoding the signed integers …, -1, 0, 1, 2, …. To make things simple, let’s use a fixed number of …
Let’s draw the Mandelbrot set!
When I was 12 or 13 I saw a science program about fractals and chaos theory. I was intrigued by the intricate organic shapes and bright colors, especially of the Mandelbrot set, and decided I wanted to learn how to make them. This is how I got interested in mathematics and programming in the first …
Welford’s method for computing variance
The standard deviation is a measure of how much a dataset differs from its mean; it tells us how dispersed the data are. A dataset that’s pretty much clumped around a single point would have a small standard deviation, while a dataset that’s all over the map would have a large standard deviation. Given a …
What is O(0)
If you have ever taken a course in algorithms or data structures you’ll have seen big-O notation. For example you’ll know that a bubble sort runs in O(n²) time and merge sort in O(n log n) time. Maybe you have been explained that with big-O adding and multiplying by constants doesn’t matter, so O(1000n+1000) is …