Code Golf: Leibniz formula for Pi

Question

I recently posted one of my favourite interview whiteboard coding questions in "What's your more controversial programming opinion", which is to write a function that computes Pi using the Leibniz formula.

It can be approached in a number of different ways, and the exit condition takes a bit of thought, so I thought it might make an interesting code golf question. Shortest code wins!

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 within 0.00001.

Edit: 3 Jan 2008

As suggested in the comments I changed the exit condition to be within 0.00001 as that's what I really meant (an accuracy 5 decimal places is much harder due to rounding and so I wouldn't want to ask that in an interview, whereas within 0.00001 is an easier to understand and implement exit condition).

Also, to answer the comments, I guess my intention was that the solution should compute the number of iterations, or check when it had done enough, but there's nothing to prevent you from pre-computing the number of iterations and using that number. I really asked the question out of interest to see what people would come up with.

Answer 1

Perl

26 chars

26 just the function, 27 to compute, 31 to print. From the comments to this answer.

sub _{$-++<1e6&&4/$-++-&_}       # just the sub
sub _{$-++<1e6&&4/$-++-&_}_      # compute
sub _{$-++<1e6&&4/$-++-&_}say _  # print

28 chars

28 just computing, 34 to print. From the comments. Note that this version cannot use 'say'.

$.=.5;$\=2/$.++-$\for 1..1e6        # no print
$.=.5;$\=2/$.++-$\for$...1e6;print  # do print, with bonus obfuscation

36 chars

36 just computing, 42 to print. Hudson's take at dreeves's rearrangement, from the comments.

$/++;$\+=8/$//($/+2),$/+=4for$/..1e6
$/++;$\+=8/$//($/+2),$/+=4for$/..1e6;print

About the iteration count: as far as my math memories go, 400000 is provably enough to be accurate to 0.00001. But a million (or as low as 8e5) actually makes the decimal expansion actually match 5 fractional places, and it's the same character count so I kept that.

Answer 2

Another C# version:

(60 characters)

4*Enumerable.Range(0, 500000).Sum(x => Math.Pow(-1, x)/(2*x + 1));  // = 3,14159

Answer 3

Using the formula for the error term in an alternating series (and thus the necessary number of iterations to achieve the desired accuracy is not hard coded into the program):

public static void Main(string[] args) {
    double tolerance = 0.000001;
    double piApproximation = LeibnizPi(tolerance);
    Console.WriteLine(piApproximation);
}

private static double LeibnizPi(double tolerance) {
    double quarterPiApproximation = 0;

    int index = 1;
    double term;
    int sign = 1;
    do {
        term = 1.0 / (2 * index - 1);
        quarterPiApproximation += ((double)sign) * term;
        index++;
        sign = -sign;
    } while (term > tolerance);

    return 4 * quarterPiApproximation;
}

Answer 4

For the record, this Scheme implementation has 95 characters ignoring unnecessary whitespace.

(define (f)
  (define (p a b)
    (if (> a b)
      0
      (+ (/ 1.0 (* a (+ a 2))) (p (+ a 4) b))))
  (* 8 (p 1 1e6)))

Answer 5

C# cheating - 50 chars:

static single Pi(){
  return Math.Round(Math.PI, 5));
}

It only says "taking into account the formula write a function..." it doesn't say reproduce the formula programmatically :) Think outside the box...

C# LINQ - 78 chars:

static double pi = 4 * Enumerable.Range(0, 1000000)
               .Sum(n => Math.Pow(-1, n) / (2 * n + 1));

C# Alternate LINQ - 94 chars:

static double pi = return 4 * (from n in Enumerable.Range(0, 1000000)
                               select Math.Pow(-1, n) / (2 * n + 1)).Sum();

And finally - this takes the previously mentioned algorithm and condenses it mathematically so you don't have to worry about keep changing signs.

C# longhand - 89 chars (not counting unrequired spaces):

static double pi()
{
  var t = 0D;
  for (int n = 0; n < 1e6; t += Math.Pow(-1, n) / (2 * n + 1), n++) ;
  return 4 * t;
}

Answer 6

Here's a solution in MUMPS.

pi(N)
 N X,I
 S X=1 F I=3:4:N-2 S X=X-(1/I)+(1/(I+2))
 Q 4*X

Parameter N indicates how many repeated fractions to use. That is, if you pass in 5 it will evaluate 4 * (1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11)

Some empirical testing showed that N=272241 is the lowest value that gives a correct value of 3.14159 when truncated to 5 decimal points. You have to go to N=852365 to get a value that rounds to 3.14159.