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

#!/usr/bin/env python
from math import *
denom = 1.0
imm = 0.0
sgn = 1
it = 0
for i in xrange(0, int(1e6)):
    imm += (sgn*1/denom)
    denom += 2
    sgn *= -1    
print str(4*imm)

Answer 2

Language: C, Char count: 71

float p;main(i){for(i=1;1E6/i>5;i+=2)p-=(i%4-2)*4./i;printf("%g\n",p);}

Language: C99, Char count: 97 (including required newline)

#include <stdio.h>
float p;int main(){for(int i=1;1E6/i>5;i+=2)p-=(i%4-2)*4./i;printf("%g\n",p);}

I should note that the above versions (which are the same) keep track of whether an extra iteration would affect the result at all. Thus, it performs a minimum number of operations. To add more digits, replace 1E6 with 1E(num_digits+1) or 4E5 with 4E(num_digits) (depending on the version). For the full programs, %g may need to be replaced. float may need to be changed to double as well.

Language: C, Char count: 67 (see notes)

double p,i=1;main(){for(;i<1E6;i+=4)p+=8/i/(i+2);printf("%g\n",p);}

This version uses a modified version of posted algorithm, as used by some other answers. Also, it is not as clean/efficient as the first two solutions, as it forces 100 000 iterations instead of detecting when iterations become meaningless.

Language: C, Char count: 24 (cheating)

main(){puts("3.14159");}

Doesn't work with digit counts > 6, though.

Answer 3

C#:

public static double Pi()
{
    double pi = 0;
    double sign = 1;
    for (int i = 1; i < 500002; i += 2)
    {
        pi += sign / i;
        sign = -sign;
    }
    return 4 * pi;
}

Answer 4

Perl :

$i+=($_&1?4:-4)/($_*2-1)for 1..1e6;print$i

for a total of 42 chars.

Answer 5

Here's a recursive answer using C#. It will only work using the x64 JIT in Release mode because that's the only JIT that applies tail-call optimisation, and as the series converges so slowly it will result in a StackOverflowException without it.

It would be nice to have the IteratePi function as an anonymous lambda, but as it's self-recursive we'd have to start doing all manner of horrible things with Y-combinators so I've left it as a separate function.

public static double CalculatePi()
{
    return IteratePi(0.0, 1.0, true);
}

private static double IteratePi(double result, double denom, bool add)
{
    var term = 4.0 / denom;
    if (term < 0.00001) return result;    
    var next = add ? result + term : result - term;
    return IteratePi(next, denom + 2.0, !add);
}

Answer 6

Language: Brainfuck, Char count: 51/59

Does this count? =]

Because there are no floating-point numbers in Brainfuck, it was pretty difficult to get the divisions working properly. Grr.

Without newline (51):

+++++++[>+++++++<-]>++.-----.+++.+++.---.++++.++++.

With newline (59):

+++++++[>+++++++>+<<-]>++.-----.+++.+++.---.++++.++++.>+++.