views:

6935

answers:

45

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.

A: 

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);
}
Greg Beech
I don't think your term<0.00001 exit condition suffices. In fact, I only see one solution so far, from strager, that solves the problem of deciding when to exit (other than to hardcode a sufficient number of iterations).
dreeves
@dreeves: (term<0.00001) and (|curr-prev|<0.00001) are exactly the same condition, since curr=prev+-term.
JB
+13  A: 

52 chars in Python:

print 4*sum(((-1.)**i/(2*i+1)for i in xrange(5**8)))

(51 dropping the 'x' from xrange.)

36 chars in Octave (or Matlab):

l=0:5^8;disp((-1).^l*(4./(2.*l+1))')

(execute "format long;" to show all the significant digits.) Omitting 'disp' we reach 30 chars:

octave:5> l=0:5^8;(-1).^l*(4./(2.*l+1))'
ans = 3.14159009359631
Federico Ramponi
Seeing as I can't edit community wikis yet: You can reduce this by another character by using `xrange(999999)` instead of `xrange(1000000)`. It's still accurate enough to get the first five decimals right.
Ben Blank
'-1.0' can become '1.' and xrange can become range, at least on my macbook...
Alabaster Codify
@jamesbrady, no, '-1' cannot be changed to '1'
Corey
thank you for 999999 and 1., but range(999999) is pure blasphemy :D
Federico Ramponi
Replace 999999 with 10**6 (= 1000000) to shave off a couple of chars. (other, shorter alternatives include 8**7 ( = 2097152) or 6**8 ( = 1679616).
gnud
...which brings us to 53 chars, possibly 52 if the drop the x from xrange. Thank you :D
Federico Ramponi
Here's a 38 char version (with Python 3 style division): sum(8/i/(i-2)for i in xrange(3,3e6,4)) --- see my ruby post below for an explanation
zenazn
@Corey: oops, yep i meant drop the zero, not the sign too
Alabaster Codify
Why are you raising 5 to a power of 8? Why not do a shift operation for speed.
Ross Rogers
Code golf = as few chars as possible, not as fast as possible.
zenazn
I managed to get your Python version down to 46 characters: print 2*sum((-1)**i/(i+.5)for i in range(1e5))
Zach Langley
I posted a 38 char version above, if anyone wants to edit this post (I can't yet). ... ... *hint hint*
zenazn
I managed it in MATLAB with 23 chars: a=1e6;sum(4./(1-a:4:a))
gnovice
I took out a space.
recursive
+1  A: 

Ruby:

irb(main):031:0> 4*(1..10000).inject {|s,x| s+(-1)**(x+1)*1.0/(2*x-1)}
=> 3.14149265359003
derobert
That output isn't accurate to 5 decimals...
Adam Peck
Can be made slightly smaller:4*(0..max).inject(0){|s,x|s+(-1)**x/(2*x+1.0)}
Martin Carpenter
sine, cosine, cosine, sine, 3.14159!!
brad.lane
+1  A: 

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;
}
Darin Dimitrov
-1 for confusingly naming your variable 'pi' when its value is actually pi/4
finnw
+17  A: 

Another C# version:

(60 characters)

4*Enumerable.Range(0, 500000).Sum(x => Math.Pow(-1, x)/(2*x + 1));  // = 3,14159
CMS
Interesting. I think this is the most readable of all the examples thus far. LINQ is quite useful.
Charlie Salts
It is beautiful.
Alex Baranosky
Very elegant solution!
Si
To save 10 few characters, replace `Math.Pow(-1, x)` with `x%2==0?1:-1` and remove the 6 spaces inside the code.
configurator
+4  A: 

Perl :

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

for a total of 42 chars.

Learning
oh, so many chars. bloat-ware ;-)
Hynek -Pichi- Vychodil
Learning
It's getting interesting :) You can even use 5.10's say.
JB
JB
+9  A: 
Juliet
The F# would be slightly more idiomatic if you replaced `Math.Pow(-1.0, y)` with `-1.0 ** y`.
Joel Mueller
It's community wiki, you can improve it yourself :)
badp
+3  A: 

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.

Clayton
+22  A: 

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.

JB
Kinda brute-force, it seems (100 thousand iterations, just for five digits?).
strager
One less character: $.=.5;$\=2/$.++-$\for 0..1e6;print
Hudson
@Hudson: that's *two* less characters, actually--great stuff! I've spent all night trying to get rid of the initial --$, with stuff like 4/++$,++ and I didn't even think of changing the fraction.
JB
@strager: 1e6 is the shortest way to write [whatever number of iterations is needed] that I know of. I wished to evade the debate of what 5-digit accuracy actually meant. What *really* makes the thing slow is the use of $\ instead of just any other variable (3x as slow here). But it saves chars...
JB
You're right -- my character count included the newline. Here's a way to make it even more obfuscated, but doesn't save any bytes: $.=.5;$\=2/$.++-$\for$...1e6;print
Hudson
It is longer, but slightly less readable based on dweeves rearranging: $/++;$\+=8/$//($/+2),$/+=4for$/..1e6;print
Hudson
this is great stuff JB
Learning
+4  A: 

Ruby, 41 chars (using irb):

s=0;(3..3e6).step(4){|i|s+=8.0/i/(i-2)};s

Or this slightly longer, non-irb version:

s=0;(3..3e6).step(4){|i|s+=8.0/i/(i-2)};p s

This is a modified Leibniz:

  1. Combine pairs of terms. This gives you 2/3 + 2/35 + 2/99 + ...
  2. Pi becomes 8 * (1/(1 * 3) + 1/(5 * 7) + 1/(9 * 11) + ...)
zenazn
+2  A: 

Language: dc, Char count: 35

dc -e '9k0 1[d4r/r2+sar-lad274899>b]dsbxrp'
Hynek -Pichi- Vychodil
That's too much recursion on my Linux box:osbox:/tmp: dc -e '9k0 1[d4r/r2+sar-lad999999>b]dsbxrp'Segmentation fault
Hudson
massif reports 1,032 bytes are being used on my 64-bit system, and reports a stack size of 0. Obviously something's up with massif. I guess a stack overflow could occur, but it didn't for me. It did take quite a bit of time to execute though.
strager
Unfortunately dc have not tail call optimization. But it works for me. One million should not be too much macro expansions.
Hynek -Pichi- Vychodil
@Hudson: I have decreased iterations for you a little bit ;-)
Hynek -Pichi- Vychodil
It still segfaults when I try it.
JB
I have$ dc --versiondc (GNU bc 1.06.94) 1.3.94
Hynek -Pichi- Vychodil
worksforme `dc (GNU bc 1.06.94) 1.3.94`
J.F. Sebastian
+2  A: 

Language: C99 (implicit return 0), Char count: 99 (95 + 4 required spaces)

exit condition depends on current value, not on a fixed count

#include <stdio.h>

float p, s=4, d=1;
int main(void) {
  for (; 4/d > 1E-5; d += 2)
        p -= (s = -s) / d;
  printf("%g\n", p);
}

compacted version

#include<stdio.h>
float
p,s=4,d=1;int
main(void){for(;4/d>1E-5;d+=2)p-=(s=-s)/d;printf("%g\n",p);}
pmg
You can take the "void" out of main's declaration for a four-char savings. You can also declare it to be a C++ program and change "stdio.h" to "cstdio" to save one char.
John Zwinck
"void" removed, thank you. And I'll leave it as C :)
pmg
Hmmmm ... "int main() { /* ... */ }" is implementation defined. "void" returns to my program.
pmg
You can init s to -4, and remove the 4* from the printf. This saves one character. Also, why can't p be a float? Stick it next to s.
strager
I like that initialization of s to 4! p cannot be a float because if it is "%g" prints "3.1416" and "%f" prints "3.141595" -- this may be an implementation issue?
pmg
Ah, well, have you tried making s a double then? =] Also, I believe s=-s is shorter than s*=-1.
strager
Another character is stripped when you set s=4 and use p-= instead. Of course, you can make d=1 and d-=2 instead.
strager
Code revamped incorporating your suggestions. I also made the exit condition a bit different
pmg
On the exit condition: what? Care to explain that one a bit? I see you're eliminating the sign issue by multiplying q and s, but I don't see where the -3E-5 comes from.
strager
it's the "while (q*s < -3E-5)". q is the current value (1/3, 1/5, 1/7, ...) and I multiply by s to get rid of positive/negative confusion. When the current term gets smaller than ~0.00001 (don't forget s is 4), the loop terminates.
pmg
The -3E-5 comes from 0.00001 * 4. 0.00001 is the precision I want, 4 is the value of s, but -4E-5 didn't get enough precision :)
pmg
I've refactored your version a bit more, and came up with this: float p,s=4,d=1;int main(void){for(;4/d>1E-5;d+=2)p-=(s=-s)/d;printf("%g\n",p);} // 99 characters, if you add the #include. It beats my version when stripped down! I'm surprised. =]
strager
Aha! I've updated my own response, and it beats my version of yours by one character using my own method. This is rather competitive...
strager
LOL, thanks again. If I remove the "void" from 'our' latest main ...
pmg
"int main() { ... }" is perfectly fine, it's not implementation defined. You may in fact save 4 chars by removing "void".
Johannes Schaub - litb
+6  A: 

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.

strager
Not a guru ... but, yes, globals are initialized to 0.
pmg
Thanks; shaved off two characters in my first two versions.
strager
+1  A: 

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;
}
BenAlabaster
I'd normally do that myself: "think outside the box." However, I'd probably be more serious at an interview, unless it's very obvious there's a better solution. In this case, the problem was converting words into an algorithm and, finally, code.
strager
Maybe, it would depend very much on the vibe I get from the interviewer. If they were a very staunch interviewer, I'd probably code it out as they'd expect to see it, but if the atmosphere was more relaxed, I'd let my cheekiness show through :P
BenAlabaster
Is all that Math.Pow stuff shorter than a temporary + multiply? double s = 1; for(...; ...; s=-s)t += s / ...; Also, can't you increment n by two, and start at n=1, thus making 2*n+1=>n? Also, you don't need parentheses around (2*n) due to OOO.
strager
Actually going back and looking at it again, using Math.Pow, you don't have to cast as double, so you avoid having to do that and you don't need to create a second variable to keep track of 1 or -1. The alternative is using (n % 2 == 0) to check for the negative which is longer too.
BenAlabaster
+6  A: 

Mathematica, 27 chars (arguably as low as 26, or as high as 33)

NSum[8/i/(i+2),{i,1,9^9,4}]

If you remove the initial "N" then it returns the answer as a (huge) fraction.

If it's cheating that Mathematica doesn't need a print statement to output its result then prepend "[email protected]" for a total of 33 chars.

NB:

If it's cheating to hardcode the number of terms, then I don't think any answer has yet gotten this right. Checking when the current term is below some threshold is no better than hardcoding the number of terms. Just because the current term is only changing the 6th or 7th digit doesn't mean that the sum of enough subsequent terms won't change the 5th digit.

dreeves
Well, the question /did/ as for "a function that calculates Pi to an accuracy of 5 decimal places." It doesn't have to do anything with the calculation. =]
strager
True, but it does also mention an exit condition...
dreeves
The exit condition can be computed before even getting to the iteration. If it saves chars and is provably accurate enough, it's all fair game to me.
JB
+5  A: 

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;
}
Jason
You don't really know what code golf is, do you
1800 INFORMATION
If you program like this in a code golf, your normal code must be incredible! XD
fortran
+36  A: 

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

+++++++[>+++++++>+<<-]>++.-----.+++.+++.---.++++.++++.>+++.
strager
+1 for utter awesomeness.
Salty
+1 Haven't seen this language for some time :D
m3rLinEz
What divisions? you're doing a print "3.14159" :-P, the only actual PI calculation on brainfuck I've seen it's 20,000+ characters long! http://dl.getdropbox.com/u/35146/PI16.txt
CMS
@CMS, Shh! That's the secret. ;P
strager
Wow... lol lol lol what a rip off
DFectuoso
+1 for having the cheekiness :P
Atmocreations
+3  A: 

Javascript:

a=0,b=-1,d=-4,c=1e6;while(c--)a+=(d=-d)/(b+=2)

In javascript. 51 characters. Obviously not going to win but eh. :P

Edit -- updated to be 46 characters now, thanks to Strager. :)


UPDATE (March 30 2010)

A faster (precise only to 5 decimal places) 43 character version by David Murdoch

for(a=0,b=1,d=4,c=~4e5;++c;d=-d)a-=d/(b-=2)
Salty
Is it possible to do something like b=d=-1? (I don't know Javascript.) Also, d=-d is shorter than d*=-1, and you can initialize d to -4 (kills b=d=-1 optimization) and remove the 4* at the end (as I mentioned to pmg for his answer).
strager
Brilliant. Down to 46 characters now, with your help. :)I spent some time looking at the code again and managed to combine 3 definitions into one block:a=b=d=-1But the code required to reverse the effects of a being -1 made the overall code exactly the same as the version i posted above. :(
Salty
a=0,b=-1,d=-4,c=1e6;while(c--)a+=(d=-d)/(b+=2)^ Final version, with your help. =]
Salty
@Salty, You can edit your answer to show your better solution. Also, can you initialize c to 0 (along with a), and compare c in the while, like: while(c++<1e6). Does that affect the char count much?
strager
It actually comes out to exactly the same char count. I tried it earlier. :P
Salty
It's taken 10 months, but finally a version **one character shorter** is available: `for(a=0,b=-1,d=-4,c=1e6;c--;)a+=(d=-d)/(b+=2)`
Alex Barrett
43 characters and over twice as fast the 46 character version (but ONLY precise to .00001): `for(a=0,b=1,d=4,c=~4e5;++c;d=-d)a-=d/(b-=2)`
David Murdoch
+2  A: 

Most of the current answers assume that they'll get 5 digits accuracy within some number of iterations and this number is hardcoded into the program. My understanding of the question was that the program itself is supposed to figure out when it's got an answer accurate to 5 digits and stop there. On that assumption here's my C# solution. I haven't bothered to minimise the number of characters since there's no way it can compete with some of the answers already out there, so I thought I'd make it readable instead. :)

    private static double GetPi()
    {
        double acc = 1, sign = -1, lastCheck = 0;

        for (double div = 3; ; div += 2, sign *= -1)
        {
            acc += sign / div;

            double currPi = acc * 4;
            double currCheck = Math.Round(currPi, 5);

            if (currCheck == lastCheck)
                return currPi;

            lastCheck = currCheck;
        }
    }
Evgeny
Fixed your formatting. Also, my answer (http://stackoverflow.com/questions/407518/code-golf-leibniz-formula-for-pi#408454) takes a different approach: it asserts that the current value to add (or subtract) is >=0.000005 (enough to cause rounding), and terminates otherwise.
strager
One thing: == comparison on doubles is *evil*! You can still get an incorrect answer (perhaps an infinite loop?)! You have been warned.
strager
That's an interesting point. It could become an issue with higher precision, but for 5 digits it works fine. I've tested it with 8 digits, too.
Evgeny
I'm not convinced this is (mathematically) right. Just because two iterations in a row have the same first 5 digits doesn't mean that if you add enough additional terms those 5 digits won't change.
dreeves
Indeed. This is a problem for the general case. This is only safe because you know in advance the value of pi. If it had several zeros or nines in a row, it could easily appear to stabilize earlier digits for several iterations before actually settling down.
recursive
@dreeves and recursive - I'm not sure about that. The values are alternatively higher and lower with each iteration and they converge, so as far as I can see, once the last 5 digits are the same they will never be different again.
Evgeny
@Evgeny: for a counterexample, the same series offset by pi-1 converges to 1. After enough iterations, all numbers we add are smaller than 1e-5; the sum is less than 1e-5 away from 1, alternating above and below it. And its first 5 fractional digits alternate between 99999 and 00000.
JB
@JB But in that case you would never have two iterations in a row that contained the same first 5 digits, would you? :)
Kirk Broadhurst
+20  A: 

Ruby, 33 characters

(0..1e6).inject{|a,b|2/(0.5-b)-a}
Zach Langley
Very interesting. Quite a language.
Learning
It doesn't print the result at the end. How many more characters does that require?
Hudson
@Hudson, just two, by placing "p " before it. But the question just asks to compute pi, not print it
Zach Langley
It does actually compute `pi` (1e-6 error) http://codepad.org/y6FcU3Fv
J.F. Sebastian
A: 

VB 117 chars:

Function Pi()
  Dim t = 0D
  For n = 0 To 1000000
    t += Math.Pow(-1, n) / (2 * n + 1)
  Next
  Return 4 * t
End Function

VB LINQ 115 chars (omitting the unnecessary line continuation):

Function Pi()
  Return 4 * Enumerable.Range(0, 1000000) _
             .Sum(Function(n) Math.Pow(-1, n) / (2 * n + 1))
End Function

And then call:

Sub Main()
  Console.WriteLine("{0:n5}", Pi)
End Sub
BenAlabaster
+3  A: 

C# using iterator block:

static IEnumerable<double> Pi()
{
    double i = 4, j = 1, k = 4;
    for (;;)
    {
        yield return k;
        k += (i *= -1) / (j += 2);
    }
}
dalle
+10  A: 
Gracenotes
It doesn't overflow stack here with foldl and 9^6 :)
ShreevatsaR
Oh, I didn't check to see if the non-strict version worked for 9^6 (it didn't with 10^6). Edited to reflect this!
Gracenotes
Even shorter - foldr1(-)$map(4/)[1,3..9^6]
Matajon
A: 

Another VB solution, using the rather cool aggregation syntax:

Public ReadOnly Pi As Double = 4 * Aggregate i In Enumerable.Range(0, 100000) _
                                   Select (-1) ^ i / (i * 2 + 1) Into Sum()

Expression only: 74 characters without unnecessary whitespaces.

Konrad Rudolph
+51  A: 

J, 14 chars

4*-/%>:+:i.1e6

Explanation

  • 1e6 is number 1 followed by 6 zeroes (1000000).
  • i.y generates the first y non negative numbers.
  • +: is a function that doubles each element in the list argument.
  • >: is a function that increments by one each element in the list argument.

So, the expression >:+:i.1e6 generates the first one million odd numbers:

1 3 5 7 ...

  • % is the reciprocal operator (numerator "1" can be omitted).
  • -/ does an alternate sum of each element in the list argument.

So, the expression -/%>:+:i.1e6 generates the alternate sum of the reciprocals of the first one million odd numbers:

1 - 1/3 + 1/5 - 1/7 + ...

  • 4* is multiplication by four. If you multiply by four the previous sum, you have π.

That's it! J is a powerful language for mathematics.


Edit: since generating 9! (362880) terms for the alternate sum is sufficient to have 5 decimal digit accuracy, and since the Leibniz formula can be written also this way:

4 - 4/3 + 4/5 - 4/7 + ...

...you can write a shorter, 12 chars version of the program:

-/4%>:+:i.9!
friol
it can be done even in 12 chars, with some more optimization: -/4%>:+:i.!9
friol
I'd be interested in the explanations for the optimized version too.
JB
9! is just the factorial of 9 (362,880) wich is the first factorial of n > 100,000 = 1e6.
Gumbo
From all the J answers here and on Project Euler, I assumed that J programmers had taken an oath never to explain their code to anyone. Thanks for the step-by-step explanation!
MatrixFrog
+1  A: 

64 chars in AWK:

~# awk 'BEGIN {p=1;for(i=3;i<10^6;i+=4){p=p-1/i+1/(i+2)}print p*4}'
3.14159
LoranceStinson
Nice. You can chop off two characters by distributing the 4 into the rest of the code: awk 'BEGIN {p=4;for(i=3;i<10^6;i+=4){p=p-4/i+4/(i+2)}print p}'
Zach Langley
Nice! Thanks. I tend to forget you can do that in equations.
LoranceStinson
+4  A: 
{0.0..1E6}|>Seq.fold(fun a x->a+ -1.**x/(2.*x+1.))0.|>(*)4.

F# (Interactive Mode) (59 Chars)

(Yields a warning but omits the casts)

David Klein
You cannot remove the spaces in `( * )`.
Jon Harrop
+10  A: 

Oracle SQL 73 chars

select -4*sum(power(-1,level)/(level*2-1)) from dual connect by level<1e6
tuinstoel
+1 for the language choice :)
friol
+2  A: 

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)))
Alan
A: 

Erlang, ~126 chars:

-module (pi).
-export ([pi/0]).

pi() -> 4 * pi(0,1,1).
pi(T,M,D) ->
 A = 1 / D,
 if A > 0.00001 
           -> pi(T+(M*A), M*-1, D+2);
     true  -> T
 end.
cheng81
+5  A: 

common lisp, 55 chars.

(loop for i from 1 upto 4e5 by 4 sum (/ 8d0 i (+ i 2)))
Upvote just for having the prettiest solution.
fatcat1111
+1  A: 
#!/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)
A: 

Here's mine in C++, probably the longest way of doing it :P

double pi(){
   bool add = true;
   double rPi = 0;
   for(long i = 1; i < 99999999; i=i+2)
   {
            double y = (double) i;
            double x = (double) 1;
            if(add)
            {
                   rPi = rPi + (x/y);
                   add = false;
            }
            else
            {
                    rPi = rPi - (x/y);
                    add = true;
            }
   }
            return (rPi * (double) 4);
   }
hmm you could kill add and make coeff go from -1 to 1 and back by negation
mannicken
+1  A: 

C++

double LeibnizPi( double tolerance )
{
    double sum = 1.0;
    for( int plus_div = 5, minus_div = -3, limit = 10 / tolerance; plus_div < limit ; plus_div += 4, minus_div -= 4 )
        sum += 1./plus_div + 1./minus_div;
    return 4 * sum;
}
Vadim Ferderer
+1  A: 

After noting that

(= (- (/ 4 n)
      (/ 4 (+ n 2)))
   (/ 8 n (+ n 2)))

or, in a more familiar notation:

4    4      8
- - --- = ------
n   n+2   n(n+2)

Common Lisp, with a do* loop (62 essential characters):

(do* ((n 1 (+ n 4))
      (p 8/3 (+ p (/ 8 n (+ n 2)))))
     ((< (- pi p) 1e-6)
      p)

with a tail recursive function (70 essential characters):

(defun l (n p)
  (if (< (- pi p) 1e-6)
      p
      (l (+ n 4)
          (+ p (/ 8 n (+ n 2))))))
(l 1 0)

and with the extended loop (86 essential characters):

(loop for n from 1 by 4
      sum (/ 8 n (+ n 2)) into p
      until (< (- pi p) 1e-6)
      finally (return p))

all under the presumption that preliminary checks how far we have to go to get the desired accuracy are cheating.

Svante
A: 

I just sort of wrote this right after reading interview question in the topic on controversial opinion. It ain't pretty but it took me about 3-4 minutes and I am checking for accuracy in each loop. C++. I'll wake up tomorrow and post a solution that doesn't suck :)

double get_pi(int acc)
{

  double pi;
  double dynamicpart;
  int operationCoeff = 1;
  int denom = 3;
  while(1)
  { 
      dynamicpart =
         1/denom + operationCoeff*(denom+2);
      pi = 4*(1-dynamicpart);
      if(!(pi*acc*10-(int)pi*acc*10)) break;
)
      denom+=2;
      operationCoeff = -operationCoeff;
  }



}
mannicken
+1  A: 

double d = 1; double s = 1; double pi = 0;

while(4.0 / d > 0.000001){
    pi += s*4.0/d;
    d+=2;
    s = -s;        
}
printf("%f\n", pi);
+8  A: 

23 chars in MATLAB:

a=1e6;sum(4./(1-a:4:a))
gnovice
tested it: ans = 3.1416
Jader Dias
@Jader: Did you set `format long` first? That will display more digits (since MATLAB displays fewer by default).
gnovice
A: 

Uh....as a general rule in numeric processing one should sum series from the smallest term toward the largest to avoid trouble with loss of precision. So in

fortran77

stripped down (248 characters)

      function pi(n)
      pi=0.
      t=10**(-n-0.5)
      i=int(4/t)
      i=i/2
      s=-1.                     
      do 1 j=i*2+1,1,-2
         pi = pi + s/j
         s=-s
 1    continue
      pi=abs(pi)*4              
      return
      end

With a scaffold and comments (600 characters)

      program leibnitz

      n=5
      p=int(pi(n)*10.**n)/10.**n
      write(6,*)p 

      stop
      end

c     Returns pi computed to <n> digits by the leibniz formula
      function pi(n)
      pi=0.
c     find the smallest term we need by insuring that it is too small to
c     effect the interesting digits.
      t=10**(-n-0.5)
      i=int(4/t)
      i=i/2
      s=-1.                     ! sign of term, might be off by one, but
      do 1 j=i*2+1,1,-2
         pi = pi + s/j
         s=-s
 1    continue
      pi=abs(pi)*4              ! we fix the sign problem here
      return
      end

output:

   3.1415901

It seems to work for arbitrary number of digits up to 6ish where the precision of real runs out. It is not optimized for speed or for minimum number of operations.

dmckee
A: 

Java

void pi(){
 double x=1,y=1,d=1;
 for(;x<1E6;) { y=-y;d+=y/((2*x++)+1); }
 System.out.println(d*4);
}
vertigo
A: 

Python 3 (40 bytes)

sum(8/(n*(n+2))for n in range(1,5**8,4))

This version uses optimization from @Svante's answer.

print +7 bytes

print(sum(8/(n*(n+2))for n in range(1,5**8,4)))

Python 2.x +1 byte

sum(8./(n*(n+2))for n in range(1,5**8,4))

print +6 bytes

print sum(8./(n*(n+2))for n in range(1,5**8,4))

http://codepad.org/amtxUxKp

J.F. Sebastian
A: 

1 Character: . Written in "MySuperDuperDomainSpecificLanguageThatOnlyReturnsThisOneAnswerAndNothingElse".

Yes this is meant as a joke, but seriously unless you disallow DSLs then EVERY Code Golf contest could be won by some goober who writes his own language that uses one character to return just that one result...

jeffa00
A: 

Lua, 46 characters

p=4 for i=3,9^6,4 do p=p-8/i/(i+2)end print(p)
gwell
A: 

I don't want to learn another programming language.

c196790
A: 

Java

    double pi=0,s=-1,i=1;
    for (;i<1E6;i+=2)pi+=((1d/i)*(s=-s)); 
    pi*=4;
Obed