Intel's Ronler Acres Plant

Silicon Forest
If the type is too small, Ctrl+ is your friend

Friday, January 27, 2012

Computing Pi

A while back Stu put up a post that had a newish formula for computing the value of pi. Just for grins, I thought I would see if I could implement the formula in code, that is, write a computer program to compute the value of pi using this formula. I mean, you never know about these things. Sometimes you get formulas that look nice, but when you try and turn them into code you find out there is one piece of psycho-babble in the formula that cannot be implemented in any kind of straight forward manner. Anyway, I tried it and I was successful, and it did indeed compute an accurate value of pi. Bear in mind that accurate is a relative term.

It is claimed that this particular formula is unique in that it can compute any digit of pi without having to compute any of the previous digits. I tried to figure out how this was being done. I failed. The formula computes a series of values and each value is added to the previous total. Each successive value makes the total a little bit more precise. Each successive value is several times smaller than the previous one, so if the first value computes the first digit, then the second value will have no effect on the first digit, but it will have an impact on the second digit, and so on. However, each value that is computed is an insane decimal number in it's own right, and so the string of digits to the right of the decimal point goes on indefinitely. So while computing the Nth value of this series will not effect earlier digits, the Nth digit is still going to be the sum of all the Nth digits from all the previously computed values.

I eventually figured out what they meant. Typically these formulas include a section that needs to be repeated several times in order to achieve the required accuracy. Most of these formulas require that after you have completed the necessary number of steps and have arrived at some total, you now subject this total to another formula for further manipulation. This newish formula does not require this second step.

I took a look at the article on Pi in Wikipedia and it has a whole list of formulas for calculating Pi. And that's when it struck me that although we have these formulas, we have no explanation for how they work. Matter of fact, all we have is someone's word that they do work. And how do you know what the 10,000th digit of Pi is anyway? You can only verify the value empirically (by measuring a physical circle) out to ten or maybe 20 digits. Beyond that we are talking the intellectual equivalent of peacock feathers: very pretty but totally useless. I imagine each one of these formulas was the result of someone's doctoral thesis in mathematics and the proof of each one is probably 400 pages of inscrutable squiggles. Presumably they can all be tested against each other by writing and running a computer program.

One of the formulas was developed by an Indian prodigy about 100 years ago. It is able to compute the value of pi to the limits of my machine in three steps. The new formula takes about a dozen steps.

So now I'm wondering if I can compute the value of pi straight up from nothing. The standard way to do something like this is to divide a circle into a bunch of triangles, like cutting up a pie, and then add the lengths of the bases of all the triangles. The smaller you make the triangles, the more closely the bases of these triangle will approximate the circle, and the closer you will get to the true value of pi. So I figured out how to calculate the base of ever smaller triangles using the pythagorean formula, and put it in a program, and in a couple dozen steps or so I had a pretty good approximation.

Links:
I could find Stu's story about BBP.

2 comments:

Ole Phat Stu said...

My BBP post

http://www.savory.de/blog_mar_09.htm#20090314

Stu

Chuck Pergiel said...

Criminently, that was almost three years ago! Well, I'm glad I finally got this post up. Geez, three years. Who'd a thunk it?