Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

There are a lot of challenges on this site regarding pi, but none that challenge you to calculate as many digits of pi as possible.

As you all may know, pi in its decimal form goes on for infinity, so calculating it in its entirety is near to impossible. However, I challenge you to write a program in your language of choice that can calculate as many digits of pi as possible, and include an explanation with your code. The winner will be decided by popularity contest.

The only restriction is that your program cannot connect to the internet. The point is not to have your program search the internet for the most digits of pi.

So in summary, the goal is to write a program that computes as many digits of pi as possible (in decimal, so 3.14159....). Your program cannot simply connect to the internet and lookup digits, it needs to calculate it.

Note here that the goal here is to calculate as many digits as possible, but that is not the winning criteria. The winner will be based on popularity (number of upvotes). Remember, we're here to learn just as much as to have fun.

Winner will be decided on July 16 at 10 AM eastern time.

And please, don't be this guy. Let's have fun.

share|improve this question

closed as unclear what you're asking by Peter Taylor, user80551, Martin Büttner, Manu, nderscore Jul 10 at 12:49

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

5  
What's stopping me from calculating "all" of them? (It'll take some time, I know, but there's no time constraint in your challenge.) –  Martin Büttner Jul 9 at 23:06
2  
I don't have time to implement it now but maybe the BBP algorithm? The question doesn't explicitly say you have to use decimal... –  baum Jul 9 at 23:13
2  
In your question, you said "near to impossible". Given the universe has a finite lifespan, it IS impossible :) –  aronchick Jul 10 at 3:51
2  
print "3.2" I win, it's the law –  Nick T Jul 10 at 6:12
3  
This can either be "Calculate pi to arbitrary precision" as a popularity contest (pretty boring and not far off a duplicate of codegolf.stackexchange.com/q/506/194 ); or "Calculate as many digits of pi as possible in a given time" as fastest-code. But at present it seems to be asking for both, which doesn't make sense. –  Peter Taylor Jul 10 at 7:23

4 Answers 4

up vote 13 down vote accepted

C

The following is my favourite implementation of a pi calculation program:

#define _ F-->00 || F-OO--;
long F=00,OO=00;
main(){F_OO();printf("%1.3f\n", 4.*-F/OO/OO);}F_OO()
{
            _-_-_-_
       _-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
       _-_-_-_-_-_-_-_-_
            _-_-_-_
}

Found here with the following explanation:

Pi -- A unique program layout and the most unusual method of calculating pi I have ever seen. The source code is a circle and the program works by calculating its own area and diameter, and then doing a division to approximate pi!! Very bizzare.

I haven't tried this, but I guess you can make the circle larger to calculate more digits of pi.

share|improve this answer
1  
This is pretty cool! Can you put the language you used as the title though? –  CailinP Jul 9 at 23:48
    
It's C, but I can appreciate that might not be immediately obvious. :) –  Greg Hewgill Jul 9 at 23:49
2  
I challenge you to write a program in your language of choice Ok, you referenced a program from an ofuscation contest here. That would have been a neat reference in the comments, but I don't see how this qualifies for an answer. –  Num Lock Jul 10 at 5:30
    
I agree. This is not an answer, it's a link. –  DeadMG Jul 10 at 10:28
1  
@GregHewgill "I haven't tried this, but I guess you can make the circle larger to calculate more digits of pi." Radius 50 is accurate to 1.3e-4: codepad.org/dVM0rwpG –  primo Jul 10 at 10:49

Mathematica

I'm definitely going for the simplicity/golf award here with 5 characters:

π~N~n

Just defined n to be the number of digits you want.

I did a quick test to figure out how many digits that allows me to calculate within a week. I ran this for n from 100 000 to 10 000 000 in steps of 100 000 and measured the time. The plot looks very much linear (apart from a few outliers, because I used my machine during the test), so I got a least squares fit for a linear function, solved it for n and plugged in t = 60*60*24*7. On my 3 year-old laptop, I'd get about 4.5 * 1011 digits, which is 450 billion. Realistically it might be a bit less, as I can't predict whether the algorithm used by Mathematica will at some point slow down, e.g. due to memory or cache constraints.

share|improve this answer
1  
The plot is definitely not linear. From my experience the time increases exponentially. –  qwr Jul 10 at 2:49
1  
Technically the Using built-in functions to do the work no-longer-funny answer is an upvote short of a qualified majority, but it's still not funny. –  Peter Taylor Jul 10 at 7:26

C - 13 million digits

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#define DIGITS 13000000

int main() {
  uint64_t d=0,h=1e9;
  uint32_t b,c=30*((DIGITS+25)/9),e=0,g;
  uint32_t* f=(uint32_t*)malloc(4*c);
  while(b=c-=30){
    while(--b){
      d=d*b+h*(e?f[b]:2);
      f[b]=d%(g=2*b-1);
      d/=g;
    }
    printf(e?"%09d":"%d.",e+d/h);
    e=d%h;
  }
  free(f);
  return 0;
}

Using only standard libraries, compiled with gcc -O2. The formula used is the following:

This can be derived directly from the Leibniz Series, as can be seen elsewhere. Standard long division is used, in base 1000000000 rather than base 10, storing the remainders for each division in an array.

The algorithm is quadratic: 10000 digits takes ~0.35s, 100000 takes ~35s, etc (10 times as many takes 100 times as long). I estimate that all 13000000 will take approximately 6d 20h 18m, give or take, using a constant 170MB of memory.

share|improve this answer
    
What are you talking about?? Your source is only around 300, not THIRTEEN MILLION –  Christopher Wirt Jul 10 at 17:42
1  
@ChristopherWirt This is the number of digits I estimate this program could produce in 7 days time. –  primo Jul 11 at 5:28

C# - 412 394 chars, 3000 digits, 7 seconds

I wrote this program myself, except for the square root function. It calculates π using the Chudnovsky formula and uses the .Net BigInteger class for fixed-point math.

using B=System.Numerics.BigInteger;class M{static void Main(){B f=B.Pow(10,3000);B z=0;for(int k=0;k<220;k++)z+=f*F(6*k)*(13591409+545140134*new B(k))/(F(3*k)*B.Pow(F(k),3)*B.Pow(-640320,3*k));System.Console.WriteLine(f*f/(12*z*f/S(B.Pow(640320,3)*f*f)));}static B F(B N){return(N.Sign>0)?N*F(N-1):1;}static B S(B N){if(0==N)return 0;B o=(N>>1)+1;for(B a=o+N/o>>1;a>1)o=a;return o;}}

With some extra white space:

using B=System.Numerics.BigInteger;
class M{
static void Main(){
B f=B.Pow(10,3000);
B z=0;
for(int k=0;k<220;k++)
z+=f*F(6*k)*(13591409+545140134*new B(k))/(F(3*k)*B.Pow(F(k),3)*B.Pow(-640320,3*k));
System.Console.WriteLine(f*f/(12*z*f/S(B.Pow(640320,3)*f*f)));
}
static B F(B N){return(N.Sign>0)?N*F(N-1):1;}
static B S(B N){if(0==N)return 0;B o=(N>>1)+1;for(B a=o+N/o>>1;a>1)o=a;return o;}}

The Main function calculates Pi, and the other 2 functions are (respectively) Factorial and Square Root. The number of digits (3000) can be changed in the Main function, just be sure to change the number of Chudnovsky terms (220) to match, otherwise some digits will be incorrect.
It takes about 7 seconds to run on my computer right now.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.