For some reason I started thinking about summing up some reciprocals, specifically computing pi using the famously slow (but historically important) series by
Leibniz
So I did some programming, and here's what happened next. I don't include any code, so you can enjoy writing your own - nothing here takes more than a dozen lines.
So, if it weren't so terribly slow (wikipedia says "Calculating π to 10 correct decimal places using direct summation of the series requires precisely five billion terms"), we'd just be alternately adding and subtracting the reciprocals of the odd numbers, and multiplying by four. If we do just that, we take ages to get only very modest results. But it is very simple to program...
It turns out that we can add up ten thousand terms in a minute, in Basic, on a Beeb, we get just a few digits of accuracy, and we don't get much more if we double the work:
I reckoned that the alternate partial sums were always overshooting or undershooting but by just a little less each time... should be possible to get a better result by adding the final term halved. After some experimentation and a little thought, I realised that was just the same as averaging the last two partial sums.
Using that idea just 100 terms, and just 1 second, gets us a bit of accuracy:
But these results too seem to undershoot then overshoot, so it looks like we could average these partial sums too... in fact I think you can keep doing that, and it turns out to be, I think, something a little like
Euler's acceleration idea. Except that was proved whereas this is just playing.
So here we see we can get plenty of accuracy in just a screen's worth of results, in a couple of seconds:
It
turns out that if you do enough maths, you can get all the averaging done in the construction of the series, and compute a different series instead, which is equivalent. But that's then a program of a different form - simpler and faster, but different. For one thing, it computes half pi rather than a quarter pi.
I did wonder a bit about perhaps trying to use
Kahan's method to improve the accuracy of summation, but once I was adding rather few terms that went out the window. Likewise thoughts about using a
double precision idea.
(For more on the history of the series, previous work, and similar things, perhaps see
here.)
