11
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ By tweetable, do you mean that the code must be less than 140 characters? \$\endgroup\$ – Ypnypn Mar 15 '15 at 19:30
  • 5
    \$\begingroup\$ The problem in itself seems challenging without the character limitation. \$\endgroup\$ – BobTheAwesome Mar 15 '15 at 20:02
  • 1
    \$\begingroup\$ @BobTheAwesome Removed the character limit by popular demand. \$\endgroup\$ – user9206 Mar 15 '15 at 20:07
  • 1
    \$\begingroup\$ @mbomb007 It's not obvious at all that the decimal point must be printed, or that the digits may not be seperated by whitespace. The challenge is merely to "output consecutive digits of pi". The decimal dot is not a digit. 3141... is that - consecutive digits of pi. \$\endgroup\$ – orlp Mar 16 '15 at 12:03
  • 1
    \$\begingroup\$ It would be best if the number printed out was Pi so there was no space between digits for example. It would be even better if it included the decimal point. \$\endgroup\$ – user9206 Mar 16 '15 at 12:06
7
\$\begingroup\$

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
\$\endgroup\$
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Beat me to it by 5 minutes..... :) \$\endgroup\$ – Maltysen Mar 16 '15 at 0:18
  • \$\begingroup\$ This is great. I was however hoping the digits would all be on one line. In other words, that the output would look like Pi. \$\endgroup\$ – user9206 Mar 16 '15 at 21:21
  • 2
    \$\begingroup\$ @Lembik I changed my answer - 7 bytes longer, but now all on one line. \$\endgroup\$ – orlp Mar 16 '15 at 21:30
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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)
\$\endgroup\$
  • 5
    \$\begingroup\$ I think that the requirement to produce digits ad infinitum means that you need to use a streaming algorithm rather than one which takes a parameter n. See e.g. cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf \$\endgroup\$ – Peter Taylor Mar 15 '15 at 22:36
  • \$\begingroup\$ Infinite memory and infinite time should give an infinite number of digits . \$\endgroup\$ – user9206 Mar 20 '15 at 16:21
1
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy