Transmit Pi… precisely

Question

Following on from Monte Carlo estimator of Pi this challenge is to produce the shortest code for the constant Pi. Except here your code must output consecutive digits of pi forever.

This is code golf, so the shortest submission (in bytes) wins except that it must output the first 10,000 digits in less than 10 seconds on a reasonable PC and it must never terminate.

You can't use any built-in for Pi or trig functions.

---

Removed the hard limit on code size.

Answer 1

CJam - 48

3.1o{1YAZ2*:Z#*{_2$*2$2*)/@)\}h*]:+sX2*:X>X<o1}g

This calculates π as 2*sum(k!/(2k+1)!!) with greater and greater precision and at every step prints a bunch of digits from where it left off.

You can try online a modified version that does only 8 (outer loop) iterations and prints 512 digits, or use the java interpreter for the real thing. On my laptop it gets to 16384 digits in about 6 seconds.

Note: this program is very memory-hungry; a better behaved but slightly longer version is:

3.1o{T2AZ2*:Z#*1{@2$+@2$*2$2*)/@)1$}g;;sX2*:X>X<o1}g

Explanation:

3.1o              print 3.1
{…1}g             repeat indefinitely
    1YA           push 1, 2 and 10 (Y=2, A=10)
    Z2*:Z         push Z*2 (Z=3 initially) and store back in Z
    #*            calculate 2*10^Z (2 from the formula and 10^Z for precision)
                  this is the term for k=0, and the earlier 1 represents k
    {…}h          do-while
                  at each iteration, the stack contains: terms, k, last-term
        _2$*      copy the previous term and k and multiply them
        2$2*)/    divide the previous number by 2*k+1
                  this is the current term of the series
        @)\       increment k and move it before the current term
                  the current term now serves as the loop condition
                  so the loop terminates when the term becomes 0
    *             multiply k and the last term (0), to get rid of k
    ]:+s          put all the terms in an array, add them and convert to string
                  we obtain an approximation of π*10^Z
    X2*:X         push X*2 (X=1 initially) and store back in X
    >X<o          print X digits starting from the X position

Answer 2

Python, 138 bytes

q,r,t,i=1,180,60,2
while 1:u,y=27*i*(i+1)+6,(q*(27*i-12)+5*r)//(5*t);print(y,end="");q,r,t,i=10*q*i*(2*i-1),10*u*(q*(5*i-2)+r-y*t),t*u,i+1

Implementation of http://www.cs.ox.ac.uk/jeremy.gibbons/publications/spigot.pdf.

Answer 3

GolfScript (81 chars)

1:i:^3{3i):i*(.(*3*.@*.5*3$27i*12-*+@^*:^5*/.print^*2$5i*2-*--\10*i*2i*(*\10*.}do

Online demo (that's much slower than a reasonable desktop, and has trivial code changes to loop a finite number of times).

I have, of course, used the spigot algorithm which I mentioned in an earlier comment, but it took me a while to golf it to my satisfaction. The algorithm as presented in Gibbons' paper is (pseudocode)

q = 1; r = 180; t = 60; i = 2
while (true) {
    u = 3*(3*i+1)*(3*i+2)
    y = (q*(27*i-12)+5*r) / (5*t)
    print y
    r += q*(5*i-2)-y*t
    r *= 10*u
    q *= 10*i*(2*i-1)
    t *= u
    i += 1
}

The GolfScript above is equivalent to (pseudocode)

t = i = q = 1; r = 3
while (true) {
    u = 3*(3*i+1)*(3*i+2)
    i += 1
    r *= u
    t *= u
    y = (q*(27*i-12)+5*r) / (5*t)
    print y
    r -= y*t - q*(5*i-2)
    q *= 10*i*(2*i-1)
    r *= 10
}

which saves some characters in the initialisation and in the stack management.

Answer 4

Pyth - 87 85 bytes

Another translation of http://www.cs.ox.ac.uk/jeremy.gibbons/publications/spigot.pdf. I was gonna do Python but @orlp beat me to it, so I did Pyth. Small enough to fit in a tweet.

=H3=d1=bd=Gd#K+**hb27b6~b1=H*HK=d*dKJ/+*-*27b12G*5H*5d=H*T-H-*Jd*-*5b2G=G***GTbtybpkJ

It gives output to stdout, albeit in intermittent steps because of the print buffer that comes from setting end="" in print. I currently don't print the decimal point since the spec says "consecutive digits". Its the assignments that are killing my score.

=H3                     Set H to 3
=d1                     Set d to 1
=bd                     Set b to d which is 1
=Gd                     Set G to d which is 1
#                       Infinte Loop
  K                     Set K to
    +**hb27b6           27*b*(b+1)+6
  ~b1                   b+=1
  =H*HK                 H*=K
  =d*dK                 d*=K
  J                     Set J to
    /                   Integer division
      +*-*27b12G*5H     G*(27*b-12)+5*H
      *5d               5*d
  =H                    Set H to
    *T-H-*Jd*-*5b2G     10*(H-(J*d -G*(5*b-2)))
  =G                    Set G to
    ***GTbtyb           G*10*b*(2*b-1)
  pkJ                   Print J with the end as "", not a newline

Try it here. (Note: Since the online interpreter only give completed results, the infinite loop is out, so it only prints first 100 which increases code size. To try out infinite, download the local interpreter.)

Timing

On my google cloud compute micro instance, according to gnu time it took: real: 0m2.062s so it is obviously fast enough.

Answer 5

Scala, 599 bytes

The code below is a straight port of the Pascal code from Appendix 2 of A Spigot Algorithm for the Digits of Pi. Clearly very little golfing has yet been done. The code does generate 10,000 digits in under 10 seconds with piSpigot(10000) and if one has infinite memory can be parameterized to generate many digits, but not infinite. I am not sure if this is meeting the problem constraints so please provide feedback.

def piSpigot(n: Int): Unit = {
  val len=10*n/3
  var nines=0
  var predigit=0
  val a=Array.fill(len)(2)
  (1 to n).foreach {_=>
    var q=0
    (1 to n).reverse.foreach{i=>
      var x=10*a(i)+q*i
      a(i)=x%(2*i-1)
      q=x/(2*i-1)
    }
    a(1)=q%10
    q/=10
    if (q==9) {
      nines+=1
    } else if (q==10) {
      print(predigit+1)
      1.to(nines).foreach(_=>print(0))
      predigit=0
      nines=0
    } else {
      print(predigit)
      predigit=q
      if (nines!=0) {
        1.to(nines).foreach(_=>print(9))
        nines=0
      }
    }
  }
  println(predigit)
}
piSpigot(10000)

Answer 6

Befunge-98 (PyFunge), 120 bytes

cf*10p'<20p11>00p1+:30p:::*+39**6+:30g39**c-00g*10gv
>:2*1-*00g*a*^
^:p02*g02p01*a*-*g02\+g01*g00-2*5g03,+*86:/*5g02+*5<

Try it online!

This is borderline in terms of the timelimit. 10,000 digits take around 11 seconds on my laptop, but I'm sure there must be a "reasonable" PC that could do it faster than that.

However, if you're trying it out on TIO, note that it won't return anything until it hits the 60 second time limit, since the algorithm is designed to keep going forever. By that time you'll have a lot more than 10,000 digits though.

I'm using the Jeremy Gibbons spigot algorithm, which I think is the same as most other answers here. However, note that this relies on the interpreter having arbitrary precision memory cells, and the only implementation I'm aware of that supports that is PyFunge.

Explanation

cf*10p                     Initialise r to 180.
      '<20p                Initialise t to 60.
           11              Initialise i and q on the stack to 1.

>                          Start of the main loop.
 00p                       Save the current value of q in memory.
    1+:30p                 Increment i and save a copy in memory.      
          :::*+39**6+      Calculate u = 27*(i*i+i)+6.
                     :     Make a duplicate, since we'll need two copies later.

       30g39**c-00g*10gv   Calculate y = (q*(27*i-12)+5*r)/(5*t).
              /*5g02+*5<
        ,+*86:             Convert y to a character so we can output it.

*a*-*g02\+g01*g00-2*5g03   Calculate r = 10*u*(q*(i*5-2)+r-y*t)

         p01               Save the updated r.
     *g02                  Calculate t = t*u
  p02                      Save the updated t.

>:2*1-*00g*a*              Calculate q = 10*q*i*(i*2-1).
^:
             ^             Return to the start of the main loop.