## Calculating Pi

This was fun to write. I read this interesting post on StackOverflow, which had an answer about asking interview questions, and this was the example he gave:

Given that Pi can be estimated using the function 4 * (1 - 1/3 + 1/5 - 1/7 + …) with more terms giving greater accuracy, write a function that calculates Pi to an accuracy of 5 decimal places.

Now, I don’t get to do much coding anymore, but hey, I’m not completely out of it, so I thought I’d try my hand at it. This is what I came up with:

function CalculatePi(aIterations: Cardinal): Extended; var Counter: Cardinal; Denominator: integer; begin Counter := 0; Denominator := 3; Result := 1; repeat case Odd(Counter) of True: begin Result := Result + (1/Denominator); end; False: begin Result := Result - (1/Denominator); end; end; Inc(Counter); Denominator := Denominator + 2; until Counter >= aIterations ; Result := Result * 4; end;

Now, again, I’m no Barry Kelly, and I’m sure that this could be optimized, but I was pretty pleased with that in a ‘that’s what I would have hacked out in an interview" kind of way.

The more iterations you pass in, the more precise it gets, obviously. I actually didn’t answer the full question (I skipped the precision part), but casual testing shows that about 10,000,000 iterations gets about 5 decimal points of accuracy. In fact, 10,000,000 iteration produces 3.14159275358978, which is pretty accurate.

Using Extended is pretty inefficient when you only need 5dps. Seems strange to bother with the odd/even test. You may as well do -1/n + 1/(n+2) each loop and then you don’t need that test.

function CalculatePi(aIterations: Cardinal): Double;

var

Counter: Cardinal;

Denominator: integer;

begin

Counter := 0;

Denominator := 3;

Result := 1.0;

repeat

Result := Result - 1.0/Denominator + 1.0/(Denominator+2);

Inc(Counter, 2);

Denominator := Denominator + 4;

until Counter >= aIterations ;

Result := Result * 4.0;

end;

It’s actually quite easy to do the test of 5dp accuracy.

Glad you’ve got Barry writing the code!!

January 9th, 2009 at 5:39 pmWhy did you choose Counter to be Cardinal and Denominator to be integer?

Denominator is always Counter * 2, so at large alterations values, you will may get an overvlow (if you really have the time to wait until then).

January 9th, 2009 at 6:09 pmActually, PI is 3.14159265358979 (I memorized it to 25 decimals when I was in grade 6 - what a nerd I was/am) so Nick, please change your middle 7 to a 6.

January 9th, 2009 at 6:45 pmWhy did you use begin..end in the case block?

It makes it bulky and ugly, when you just have one statement.

Just my 2c though

January 9th, 2009 at 11:10 pmCouldn’t this:

case Odd(Counter) of

True: begin

Result := Result + (1/Denominator);

end;

False: begin

Result := Result - (1/Denominator);

end;

end;

be better written like this?

if Odd(Counter) then

January 10th, 2009 at 12:52 amResult := Result + (1/Denominator)

else

Result := Result - (1/Denominator);

See — I told you guys that you’d optimize it for me.

Nick

January 10th, 2009 at 9:07 amUwe — I know it is weird, but I like the case construct with a boolean.

K.A. — I always put single statements in begin…end pairs, so that I’m sure to have them if I have to add another line. It’s easy to add the line without remembering to put a begin..end in, and that’s a bug.

Nick

January 10th, 2009 at 1:01 pmIf you like the boolean case constuct, so then. At least you omitted the else clause…

January 11th, 2009 at 5:10 amDidn’t Pi was equal to 22/7? LOL then it must be somewhere at 3.1428571428571428571428571428571 (and still go on :D) or

3.14286 in 5 decimal places

PS: My math when i was school usually get C LOL

January 11th, 2009 at 9:30 amTBH there is nothing to be proud or brag about that Odd() testing you implemented, quickly hacked code or not.

As for the accuracy of this method, it’s not the one you want to use to compute more than a couple decimals of PI, and then only for show. It converges very slowly and is highly sensitive to floating point precision (error accumulates). IIRC about half a dozen decimals is about the best accuracy you can expect to get from this method using regular floating point math.

In an interview your implementation wouldn’t have ranked very high for me, and you wouldn’t have gotten bonus points for doing the numerically correct implementation (hint: get rid of that division per step).

January 11th, 2009 at 10:34 pmWell, Xepol, you would fail the test too

When presenting such a subject to a developer the aim wouldn’t be to compute PI, but to test his ability at handling a simple bit of math code. So the "use PI constant" answer would just indicate you didn’t understand the question

Also the math optimization actually isn’t one of those ugly deals. A basic change is the one stated above of regrouping terms two-by-two (shaving half the divs, and transforming the series in a monotonous one, which is also useful for simplifying the 5 decimals places test requirement).

For more on the subject:

http://en.wikipedia.org/wiki/Leibniz_formula_for_pi

As for computing millions of decimals, it’s fairly quick, and has been quick for several years now:

January 11th, 2009 at 11:51 pmhttp://members.shaw.ca/francislyster/pi/pi.html

Eric, Xepol:

The original premise of this post is what you would do if someone asked you, in a job interview, to produce some code to implement an algorithm of their specification. I should think that suggesting different algorithms, or using a pre-calculated constant value would not help much in getting the job!

I said in an earlier post that knowing when to stop (i.e. 5dp accuracy) wasn’t all that difficult to code. I now realise that I wasn’t thinking straight. It is actually non-trivial.

January 12th, 2009 at 6:06 amPi=3. Useful for large values of 3 or small values of Pi.

January 12th, 2009 at 11:06 amXepol,

They don’t want you to calculate pi that way. Don’t be silly. They want to know whether or not you can write code.

January 12th, 2009 at 5:10 pmI liked the question. I guess you failed the test.

First, without accuracy test you do not have the answer.

Second, the given way to calculate PI has been well crafted: the result goes up, than down, than up again, but going up it cannot exceed any previous value it had when it also went up. Thus, on each iteration you get either the upper boundary for PI or the lower boundary and these boundaries converge. So, the accuracy test is indeed trivial, and the question perfectly detects the lack of any desire to look for one.

Finally, it is informative to see how a programmer identifies the "accuracy of 5 digital points". It can be either "the difference between PI and the returned value is 0.00001 or less" or "5 digits after the point in the return value are correct". Which will be chosen? Will a question be asked?

January 16th, 2009 at 12:06 amSomewhat recently an algorithm was discovered to calculate _any_ digit of Pi without having to calculate the preceding digits (!)

Read up on it here : http://en.wikipedia.org/wiki/Bailey–Borwein–Plouffe_formula : "The Bailey–Borwein–Plouffe formula (BBP formula) provides a spigot algorithm for the computation of the nth binary digit of π. This summation formula was discovered in 1995 by Simon Plouffe. The formula is named after the authors of the paper in which the formula was first published, David H. Bailey, Peter Borwein, and Plouffe.

The discovery of this formula came as a surprise. For centuries it had been assumed that there was no way to compute the nth digit of π without calculating all of the preceding n − 1 digits."

"Advantages of the BBP algorithm

February 2nd, 2009 at 3:30 amThis algorithm computes π without requiring custom data types having thousands or even millions of digits. The method calculates the nth digit without calculating the first n − 1 digits, and can use small, efficient data types.

The algorithm is the fastest way to compute the nth digit (or a few digits in a neighborhood of the nth), but π-computing algorithms using large data types remain faster when the goal is to compute all the digits from 1 to n."

If all you need is 5 place accuracy you can just use the old COBOL (shudder!) programmer’s mnemonic involving the first three odd numbers:

_Pi_

113)355

==> 355 / 113 = 3.1415929203539823008849557522124

February 22nd, 2009 at 5:49 am