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.
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
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.
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.
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.)
On my google cloud compute micro instance, according to gnu time it took: real: 0m2.062s so it is obviously fast enough.
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)
n. See e.g. cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf
\$\endgroup\$
– Peter Taylor
Mar 15 '15 at 22:36
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<
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.
3141...is that - consecutive digits of pi. \$\endgroup\$ – orlp Mar 16 '15 at 12:03