6
\$\begingroup\$

Compute 30000 digits of the mathematical constant π, with the fastest code.

Implement in any computer programming language that I can run in my 64 bit Linux machine. You should provide your compiler optimization options if any. I am ready to install a new compiler or language runtime to run your code, given that I am not spending any money.

The code that finishes calculation and prints the output in the shortest time wins! I will measure the running time with the time command.

note 1: The program should be single threaded.
note 2: With 3.14, the number of digits is 3; with 3.1415, 5, and so on.
note 3: Hard coding π is not allowed.
note 4: Now you can use any number form in your code, not only integer.
note 5: Your output, which should be in decimal digits, need not contain the .. Just print out the numbers.
note 6: Your last digit should not be rounded up. If the next digit after the last is 5 or more, you should round up your last digit still leave the last digit as is.

Since this question was marked as duplicate, to this question. I should explain that this is a 'fastest-code' question not 'code-golf' and thus not a dupliate. The 'code-golf' answers are not well suited as an answer to this question; they are not the 'fastest'.

Improve this question
\$\endgroup\$
16
  • \$\begingroup\$ @trichoplax After thinking about a while with your comment, I decided to change my mind. Yes, since this is computing the 'digits', rounding up seems incorrect. I changed note 6. \$\endgroup\$
    – user41542
    Commented Jun 12, 2015 at 15:14
  • 4
    \$\begingroup\$ This isn't an exact duplicate of the quadratic convergence on pi question, but it's close enough that IMO it's a dupe. \$\endgroup\$
    – Peter Taylor
    Commented Jun 12, 2015 at 15:48
  • 1
    \$\begingroup\$ Are you going to redirect the output to /dev/null for measuring the time? I have a feeling that output might take much longer than the actual calculation even then, but it would be even worse if it's actually printed to a terminal. \$\endgroup\$
    – Reto Koradi
    Commented Jun 12, 2015 at 15:52
  • 1
    \$\begingroup\$ "I think for the new challenge to qualify as a duplicate, those old answers also have to be competitive." Code-golf answers ARE competitive for this question, since the linked question ALSO required fast run-time (quadratic convergence). Thus each answer in that question will ALSO be fast, and therefore competitive. \$\endgroup\$
    – mbomb007
    Commented Jun 12, 2015 at 17:01
  • 1
    \$\begingroup\$ I have a C++ program that does it in zero time (it takes a long time to compile though...) Are you including the time to compile the program? \$\endgroup\$
    – Jerry Jeremiah
    Commented Aug 28, 2015 at 2:53

1 Answer 1

Reset to default
3
\$\begingroup\$

Python 2 (Spigot Algorithm)

This is just Jeremy Gibbon's algorithm implemented in python. Definitely will be faster once someone else implements this in another language. Other methods might be faster too since I started working on this when the rules stated that I could only use integers. I originally tried doing this without string conversion and joining, but it was actually slower..

def p():
 q,r,t,j=1,180,60,2
 while True:
    u,y=3*(3*j+1)*(3*j+2),(q*(27*j-12)+5*r)//(5*t);yield y;q,r,t,j=10*q*j*(2*j-1),10*u*(q*(5*j-2)+r-y*t),t*u,j+1
p=p()
print''.join(str(p.next())for x in[1]*30000)

Completes on my work machine in about 53 seconds.

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Thanks for this. I was reading that PDF after searching for algorithms (without seeing your link to it), and I was having a hard time reading the Haskell syntax. I'm glad I can see it now in a language I can understand. \$\endgroup\$
    – mbomb007
    Commented Jun 12, 2015 at 17:04
  • \$\begingroup\$ Also, since this isn't code-golf, don't feel like you need to cram the internal of the while onto one line. And, you can use / instead of // since this is Python 2, though you can leave it for readability. \$\endgroup\$
    – mbomb007
    Commented Jun 12, 2015 at 17:09
  • 2
    \$\begingroup\$ @mbomb007 Yeah, I realized I didn't need to golf it, it just sort of happened, haha. \$\endgroup\$
    – Kade
    Commented Jun 12, 2015 at 18:14
  • \$\begingroup\$ Here it is golfed more (just for fun): ideone.com/lOhcxB . Run it with a number < 30000 if you want to see output (I used 300). \$\endgroup\$
    – mbomb007
    Commented Jun 12, 2015 at 19:44