CODEWITHSUNDEEP
code-golfrosetta-stone
Greg Beech
Greg Beech

Reputation: 136637

Code Golf: Leibniz formula for Pi

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.

Upvotes: 31

Views: 15683

Answers (30)

Eduardo Leoni
Eduardo Leoni

Reputation: 9050

R - 27 chars

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

Upvotes: 0

leen
leen

Reputation: 9098

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)

Upvotes: 4

Olivier
Olivier

Reputation: 3471

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.

Upvotes: 0

user447587
user447587

Reputation:

Java

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

Upvotes: 1

Salty
Salty

Reputation: 6688

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)

Upvotes: 3

gwell
gwell

Reputation: 2753

Lua, 46 characters

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

Upvotes: 0

friol
friol

Reputation: 7096

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!

Upvotes: 61

jeffa00
jeffa00

Reputation: 677

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

Upvotes: -1

Juliet
Juliet

Reputation: 81526

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

Upvotes: 9

tuinstoel
tuinstoel

Reputation: 7306

Oracle SQL 73 chars

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

Upvotes: 13

Federico A. Ramponi
Federico A. Ramponi

Reputation: 47075

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

Upvotes: 14

jfs
jfs

Reputation: 414325

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

Upvotes: 0

vertigo
vertigo

Reputation:

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

Upvotes: 0

strager
strager

Reputation: 90022

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

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

Upvotes: 36

dmckee --- ex-moderator kitten
dmckee --- ex-moderator kitten

Reputation: 101181

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.

Upvotes: 0

gnovice
gnovice

Reputation: 125864

23 chars in MATLAB:

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

Upvotes: 10

Maykie
Maykie

Reputation: 

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

Upvotes: 1

mannicken
mannicken

Reputation: 7123

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



}

Upvotes: 0

Svante
Svante

Reputation: 51501

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.

Upvotes: 1

Vadim Ferderer
Vadim Ferderer

Reputation: 921

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

Upvotes: 1

Zach Langley
Zach Langley

Reputation: 6786

Ruby, 33 characters

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

Upvotes: 23

teishu
teishu

Reputation:

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

Upvotes: 0

user48821
user48821

Reputation: 6031

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

Upvotes: 1

Gracenotes
Gracenotes

Reputation: 3042

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.

Upvotes: 10

user49117
user49117

Reputation: 786

common lisp, 55 chars.

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

Upvotes: 7

cheng81
cheng81

Reputation: 2434

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.

Upvotes: 0

Hynek -Pichi- Vychodil
Hynek -Pichi- Vychodil

Reputation: 26121

Language: dc, Char count: 35

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

Upvotes: 2

Alan
Alan

Reputation: 7064

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

Upvotes: 3

BenAlabaster
BenAlabaster

Reputation: 39846

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

Upvotes: 1

JB.
JB.

Reputation: 42114

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.

Upvotes: 24

Related Questions