W następstwie estymatora Pi z Monte Carlo wyzwaniem jest stworzenie najkrótszego kodu dla stałej Pi. Z wyjątkiem tego, że Twój kod musi zawsze wyświetlać kolejne cyfry pi.

Jest to kod golfowy, więc wygrywa najkrótsze przesłanie (w bajtach), z tym wyjątkiem, że musi wypisać pierwsze 10 000 cyfr w mniej niż 10 sekund na rozsądnym komputerze i nigdy nie może się zakończyć.

Nie można używać żadnych wbudowanych funkcji Pi ani Trigger.

Usunięto twardy limit rozmiaru kodu.

CJam - 48

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

To oblicza π jako sumę 2 * (k! / (2k + 1) !!) z coraz większą precyzją i na każdym kroku wypisuje kilka cyfr od miejsca, w którym zostało przerwane.

Możesz wypróbować online zmodyfikowaną wersję, która wykonuje tylko 8 iteracji (zewnętrzna pętla) i drukuje 512 cyfr, lub w rzeczywistości używa interpretera Java . Na moim laptopie dochodzi do 16384 cyfr w około 6 sekund.

Uwaga: ten program jest bardzo wymagający pamięci; lepiej zachowująca się, ale nieco dłuższa wersja to:

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

Wyjaśnienie:

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

Python, 138 bajtów

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

Wdrożenie http://www.cs.ox.ac.uk/jeremy.gibbons/publications/spigot.pdf .

GolfScript (81 znaków)

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

Demo online (jest to znacznie wolniejsze niż rozsądny pulpit i zawiera trywialne zmiany kodu, które zapętlają skończoną liczbę razy).

Oczywiście użyłem algorytmu czopka, o którym wspomniałem we wcześniejszym komentarzu, ale zajęło mi trochę czasu, aby go zagrać w sposób satysfakcjonujący. Algorytm przedstawiony w pracy Gibbonsa to (pseudokod)

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
}

Powyższy kod GolfScript jest równoważny (pseudokod)

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
}

co oszczędza niektóre znaki podczas inicjalizacji i zarządzania stosami.

Pyth - 87 85 bajtów

Kolejne tłumaczenie strony http://www.cs.ox.ac.uk/jeremy.gibbons/publications/spigot.pdf . Miałem zrobić Python, ale @orlp mnie pobił, więc zrobiłem Pyth. Wystarczająco mały, aby zmieścił się w tweecie.

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

Daje wyjście na standardowe wyjście, aczkolwiek w sposób przerywany ze względu na bufor drukowania, który pochodzi z ustawień end=""drukowania. Obecnie nie drukuję przecinka dziesiętnego, ponieważ specyfikacja mówi „kolejne cyfry”. To zadania zabijają mój wynik.

=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

Wypróbuj tutaj . (Uwaga: Ponieważ interpreter online daje tylko pełne wyniki, nieskończona pętla jest niedostępna, więc drukuje tylko pierwsze 100, co zwiększa rozmiar kodu. Aby wypróbować nieskończoność, pobierz lokalnego interpretera).

wyczucie czasu

Na mojej Google Cloud Compute mikro wystąpienie, zgodnie z czasem GNU zajęło: real: 0m2.062s więc jest oczywiście wystarczająco szybkie.

Scala, 599 bajtów

Poniższy kod jest prostym portem kodu Pascal z Dodatku 2 do Algorytmu czopowego dla cyfr Pi . Najwyraźniej bardzo mało grało w golfa. Kod generuje 10 000 cyfr w czasie krótszym niż 10 sekund piSpigot(10000)i jeśli jedna ma nieskończoną pamięć, można sparametryzować ją w celu wygenerowania wielu cyfr, ale nie nieskończonych. Nie jestem pewien, czy spełnia to ograniczenia problemów, więc proszę o informację zwrotną.

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)

Befunge-98 (PyFunge), 120 bajtów

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<

Wypróbuj online!

Jest to granica pod względem limitu czasu. 10 000 cyfr zajmuje około 11 sekund na moim laptopie, ale jestem pewien, że musi być „rozsądny” komputer, który mógłby to zrobić szybciej.

Jeśli jednak wypróbujesz to na TIO, pamiętaj, że nic nie zwróci, dopóki nie osiągnie 60-sekundowego limitu czasu, ponieważ algorytm został zaprojektowany tak, aby działał wiecznie. Do tego czasu będziesz mieć o wiele więcej niż 10 000 cyfr.

Używam algorytmu czopka Jeremy Gibbons, który moim zdaniem jest taki sam jak większość innych odpowiedzi tutaj. Zauważ jednak, że zależy to od interpretera mającego komórki pamięci o dowolnej precyzji, a jedyną znaną mi implementacją, która obsługuje, jest PyFunge .

Wyjaśnienie

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.