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