Calculate the most digits of pi

Question

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.

Answer 1

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.

Answer 2

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 * 10¹¹ 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.

Answer 3

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.

Answer 4

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.