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.

Bedfellow

When the answer is shorter than the program to compute it, there's not much point in golfing, is there? – Kielce

I would state the 'accuracy of 5 decimal places' as 'within 0.00001'. It's not obvious that the 5th decimal place in your example solution is necessarily correct. – Lead

Tip, in case this helps: a little rearranging yields 8*(1/1/3 + 1/5/7 + 1/9/11 + ...) – Dd

Computing the numerical value of Pi using the Leibniz formula is a complete wate of time due to its low rate of convergence (as mentioned in the wiki article you linked to). It's akin to teaching Bubblesort in a Uni CS course. – Aleenaleetha

I just noticed your mention of the exit condition. Does that mean it doesn't count if you hardcode the number of terms? – Dd

If someone asked me this in an interview I'd ask for a new question. The value of Pi is constant. Dumb question and a waste of interview time. Seriously an organization that thinks BS like this is a valid interview question... – Domestic

@jcollum, and seriously a programmer who failed to produce the answer isn't worth any further questioning. – Dysphemism

also, at jcollum, it is not a perfectly known constant as it is irrational, so it is worth being able to compute it. This particular method may not be the most efficient but your statement is also 'Dumb'. – Lazos

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!

Downspout

it can be done even in 12 chars, with some more optimization: -/4%>:+:i.!9 – Downspout

I'd be interested in the explanations for the optimized version too. – Kielce

9! is just the factorial of 9 (362,880) wich is the first factorial of n > 100,000 = 1e6. – Fennelly

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! – Asymptomatic

But to land the job do it 1000 times faster with a small correction term. Here it is in Scala (not in it's most compact form to show the correction term at the end): val n = 1000; (0 to n).foldLeft(0.0){(a,i)=>a + Math.pow(-1,i)/(2*i+1)}*4+Math.pow(-1,n+1)/n. I suspect J can add this correction term with a few symbols to get the desired accuracy with 1/1000 of the terms. – Infusive

Answer 2

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

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

Dhruv

@CMS, Shh! That's the secret. ;P – Dhruv

Answer 3

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.

Kielce

Kinda brute-force, it seems (100 thousand iterations, just for five digits?). – Dhruv

One less character: $.=.5;$\=2/$.++-$\for 0..1e6;print – Dither

@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. – Kielce

@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... – Kielce

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 – Dither

It is longer, but slightly less readable based on dweeves rearranging: $/++;$\+=8/$//($/+2),$/+=4for$/..1e6;print – Dither

Answer 4

Ruby, 33 characters

(0..1e6).inject{|a,b|2/(0.5-b)-a}

Adscription

Very interesting. Quite a language. – Microgamete

It doesn't print the result at the end. How many more characters does that require? – Dither

@Hudson, just two, by placing "p " before it. But the question just asks to compute pi, not print it – Adscription

Answer 5

Another C# version:

(60 characters)

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

Timbuktu

Interesting. I think this is the most readable of all the examples thus far. LINQ is quite useful. – Malvasia

To save 10 few characters, replace Math.Pow(-1, x) with x%2==0?1:-1 and remove the 6 spaces inside the code. – Dreamy

Answer 6

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

Miocene

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. – Virginity

@jamesbrady, no, '-1' cannot be changed to '1' – Dolora

thank you for 999999 and 1., but range(999999) is pure blasphemy :D – Miocene

Replace 999999 with 106 (= 1000000) to shave off a couple of chars. (other, shorter alternatives include 87 ( = 2097152) or 6**8 ( = 1679616). – Rattlebrain

...which brings us to 53 chars, possibly 52 if the drop the x from xrange. Thank you :D – Miocene

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 – Devilfish

@Corey: oops, yep i meant drop the zero, not the sign too – Polygon

Why are you raising 5 to a power of 8? Why not do a shift operation for speed. – Ararat

Code golf = as few chars as possible, not as fast as possible. – Devilfish

I managed to get your Python version down to 46 characters: print 2*sum((-1)**i/(i+.5)for i in range(1e5)) – Adscription

I posted a 38 char version above, if anyone wants to edit this post (I can't yet). ... ... hint hint – Devilfish

I managed it in MATLAB with 23 chars: a=1e6;sum(4./(1-a:4:a)) – Christen

Answer 7

Oracle SQL 73 chars

select -4*sum(power(-1,level)/(level*2-1)) from dual connect by level<1e6

Sackcloth

Answer 8

23 chars in MATLAB:

a=1e6;sum(4./(1-a:4:a))

Christen

@Jader: Did you set format long first? That will display more digits (since MATLAB displays fewer by default). – Christen

Answer 9

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.

Horsepowerhour

It doesn't overflow stack here with foldl and 9^6 :) – Litterbug

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! – Horsepowerhour

Even shorter - foldr1(-)$map(4/)[1,3..9^6] – Dorsal

Answer 10

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.

Dhruv

Not a guru ... but, yes, globals are initialized to 0. – Lizliza

Thanks; shaved off two characters in my first two versions. – Dhruv

Answer 11

F#:

Attempt #1:

let pi = 3.14159

Cheating? No, its winning with style!

Attempt #2:

let pi =
    seq { 0 .. 100 }
    |> Seq.map (fun x -> float x)
    |> Seq.fold (fun x y -> x + (Math.Pow(-1.0, y)/(2.0 * y + 1.0))) 0.0
    |> (fun x -> x * 4.0)

Its not as compact as it could possibly get, but pretty idiomatic F#.

Santinasantini

The F# would be slightly more idiomatic if you replaced Math.Pow(-1.0, y) with -1.0 ** y. – Deglutition

Answer 12

common lisp, 55 chars.

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

Moraine

Answer 13

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 "Print@" 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.

Dd

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. =] – Dhruv

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. – Kielce

Take a look at the series. It's easy to prove that the sum of all the terms after the nth has absolute value less than the nth. – Marathon

Answer 14

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;
}

Mountie

If you program like this in a code golf, your normal code must be incredible! XD – Fendig

Answer 15

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)

Undersigned

You cannot remove the spaces in ( * ). – Devin

Answer 16

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

Devilfish

Answer 17

Perl :

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

for a total of 42 chars.

Microgamete

:) .. how about this: sub {$---&&4/$----&}print- _$-=1e6 – Microgamete

It's getting interesting :) You can even use 5.10's say. – Kielce

Doing it the other way round gets down to 31: sub {$-++<1e6&&4/$-++-&}say _ – Kielce

Answer 18

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;
}

Heartrending

-1 for confusingly naming your variable 'pi' when its value is actually pi/4 – Breechcloth

Answer 19

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

Materials

Answer 20

C# using iterator block:

static IEnumerable<double> Pi()
{
    double i = 4, j = 1, k = 4;
    for (;;)
    {
        yield return k;
        k += (i *= -1) / (j += 2);
    }
}

Frazer

Answer 21

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)

Filipino

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). – Dhruv

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=-1 But the code required to reverse the effects of a being -1 made the overall code exactly the same as the version i posted above. :( – Jerkwater

a=0,b=-1,d=-4,c=1e6;while(c--)a+=(d=-d)/(b+=2) ^ Final version, with your help. =] – Jerkwater

@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? – Dhruv

It actually comes out to exactly the same char count. I tried it earlier. :P – Jerkwater

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) – Specific

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) – Filipino

Answer 22

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.

Parlando

Answer 23

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;
        }
    }

Cobelligerent

Fixed your formatting. Also, my answer (#408018) takes a different approach: it asserts that the current value to add (or subtract) is >=0.000005 (enough to cause rounding), and terminates otherwise. – Dhruv

One thing: == comparison on doubles is evil! You can still get an incorrect answer (perhaps an infinite loop?)! You have been warned. – Dhruv

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. – Cobelligerent

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. – Dd

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. – Existential

@Dd 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. – Cobelligerent

@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. – Kielce

@JB But in that case you would never have two iterations in a row that contained the same first 5 digits, would you? :) – Painty

Answer 24

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);}

Lizliza

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. – Lusk

Hmmmm ... "int main() { /* ... */ }" is implementation defined. "void" returns to my program. – Lizliza

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. – Dhruv

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? – Lizliza

Ah, well, have you tried making s a double then? =] Also, I believe s=-s is shorter than s*=-1. – Dhruv

Another character is stripped when you set s=4 and use p-= instead. Of course, you can make d=1 and d-=2 instead. – Dhruv

Code revamped incorporating your suggestions. I also made the exit condition a bit different – Lizliza

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. – Dhruv

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. – Lizliza

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

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. =] – Dhruv

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... – Dhruv

"int main() { ... }" is perfectly fine, it's not implementation defined. You may in fact save 4 chars by removing "void". – Pneumodynamics

Answer 25

Language: dc, Char count: 35

dc -e '9k0 1[d4r/r2+sar-lad274899>b]dsbxrp'

Hypesthesia

That's too much recursion on my Linux box: osbox:/tmp: dc -e '9k0 1[d4r/r2+sar-lad999999>b]dsbxrp' Segmentation fault – Dither

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. – Dhruv

Unfortunately dc have not tail call optimization. But it works for me. One million should not be too much macro expansions. – Hypesthesia

@Hudson: I have decreased iterations for you a little bit ;-) – Hypesthesia

It still segfaults when I try it. – Kielce

I have $ dc --version dc (GNU bc 1.06.94) 1.3.94 – Hypesthesia

Answer 26

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);
}

Bedfellow

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). – Dd

@dreeves: (term<0.00001) and (|curr-prev|<0.00001) are exactly the same condition, since curr=prev+-term. – Kielce

Answer 27

Java

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

Roguish

Answer 28

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

Stowers

Answer 29

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.

Domingodominguez

Answer 30

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;
}

Recipe

Answer 31

#!/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)

Pekan

Answer 32

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

Minefield

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}' – Adscription

Nice! Thanks. I tend to forget you can do that in equations. – Minefield

Answer 33

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;
}

Fretwork

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. – Dhruv

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 – Fretwork

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. – Dhruv

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. – Fretwork

Answer 34

Ruby:

irb(main):031:0> 4*(1..10000).inject {|s,x| s+(-1)**(x+1)*1.0/(2*x-1)}
=> 3.14149265359003

Quinquefid

Can be made slightly smaller: 4*(0..max).inject(0){|s,x|s+(-1)**x/(2*x+1.0)} – Snowplow

sine, cosine, cosine, sine, 3.14159!! – Lama

Answer 35

R - 27 chars

sum(4/seq(1,1e6,2)*c(1,-1))

Areca

Answer 36

PHP, 99 chars

$output =

${!${''}=function(){$pi=1;for($i=0;$i<pow(10,6);$i++){$pi+=($i%2?1:-1)/(3+$i*2);}return $pi*4;}}();

var_dump($output);

I guess there is some pretty tricks i don't know to reduce this answer ! Took the one-line output trick from this post.

Dilute

Answer 37

Lua, 46 characters

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

Goldston

Answer 38

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

Tomlinson

Answer 39

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);
}

Millais

Answer 40

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.

Heeler

Answer 41

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;
  }



}

Leifleifer

Answer 42

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);
   }

Schliemann

hmm you could kill add and make coeff go from -1 to 1 and back by negation – Leifleifer

Answer 43

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.

Triage

Answer 44

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.

Mimir

Answer 45

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

Fretwork

Answer 46

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

Electrostatic