Nick Hodges

Calculating Pi

09 Jan

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.

17 Responses to “Calculating Pi”

  1. 1
    David Heffernan Says:

    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!!

  2. 2
    J M Says:

    Why 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).

  3. 3
    Louis Kessler Says:

    Actually, 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.

  4. 4
    K.A. Says:

    Why 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 :)

  5. 5
    Uwe Raabe Says:

    Couldn’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
    Result := Result + (1/Denominator)
    else
    Result := Result - (1/Denominator);

  6. 6
    Nick Hodges Says:

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

    Nick

  7. 7
    Nick Hodges Says:

    Uwe — 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

  8. 8
    Uwe Raabe Says:

    If you like the boolean case constuct, so then. At least you omitted the else clause…

  9. 9
    Dels Says:

    Didn’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

  10. 10
    Eric Says:

    TBH 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).

  11. 11
    Eric Says:

    Well, 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:
    http://members.shaw.ca/francislyster/pi/pi.html

  12. 12
    David Heffernan Says:

    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.

  13. 13
    Alister Christie Says:

    Pi=3. Useful for large values of 3 or small values of Pi.

  14. 14
    David Heffernan Says:

    Xepol,

    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.

  15. 15
    Andrey Says:

    I 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?

  16. 16
    Patrick van Logchem Says:

    Somewhat 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/BaileyBorwein–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
    This 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."

  17. 17
    Steve Taylor Says:

    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

© 2014 Nick Hodges | Entries (RSS) and Comments (RSS)

Your Index Web Directorywordpress logo
Close