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

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!

Answer 2

Haskell

I got it down to 34 characters:

foldl subtract 4$map(4/)[3,5..9^6]

This expression yields 3.141596416935556 when evaluated.

Edit: here's a somewhat shorter version (at 33 characters) that uses foldl1 instead of foldl:

foldl1 subtract$map(4/)[1,3..9^6]

Edit 2: 9^6 instead of 10^6. One has to be economical ;)

Edit 3: Replaced with foldl' and foldl1' with foldl and foldl1 respectively—as a result of Edit 2, it no longer overflows. Thanks to ShreevatsaR for noticing this.

Answer 3

F# (Interactive Mode) (59 Chars)

{0.0..1E6}|>Seq.fold(fun a x->a+ -1.**x/(2.*x+1.))0.|>(*)4.

(Yields a warning but omits the casts)

Answer 4

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

Answer 5

common lisp, 55 chars.

(loop for i from 1 upto 4e5 by 4 sum (/ 8d0 i (+ i 2)))

Answer 6

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