Prześlij Pi… właśnie

11

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.

Społeczność
źródło
1
Czy przez tweetable rozumiesz, że kod musi mieć mniej niż 140 znaków?
Ypnypn,
5
Problem sam w sobie wydaje się trudny bez ograniczenia charakteru.
BobTheAwesome
1
@BobTheAwesome Usunięto limit znaków według popularnego zapotrzebowania.
1
@ mbomb007 Wcale nie jest oczywiste, że przecinek dziesiętny musi być wydrukowany, ani że cyfry mogą nie być oddzielone spacjami. Wyzwanie polega jedynie na „wypisywaniu kolejnych cyfr pi”. Kropka dziesiętna nie jest cyfrą. 3141...jest to - kolejne cyfry pi.
orlp
1
Byłoby najlepiej, gdyby wydrukowana liczba to Pi, więc na przykład między cyframi nie było spacji. Byłoby jeszcze lepiej, gdyby zawierała przecinek dziesiętny.

Odpowiedzi:

7

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
aditsu zrezygnowało, ponieważ SE jest ZŁEM
źródło
8

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 .

orlp
źródło
Pokonaj mnie o 5 minut ..... :)
Maltysen
To jest świetne. Miałem jednak nadzieję, że wszystkie cyfry będą na jednej linii. Innymi słowy, że dane wyjściowe wyglądałyby jak Pi.
2
@Lembik Zmieniłem odpowiedź - 7 bajtów dłużej, ale teraz wszystko w jednej linii.
orlp
5

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.

Peter Taylor
źródło
4

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.

Maltysen
źródło
3

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)
Dave Swartz
źródło
5
Myślę, że wymóg tworzenia cyfr ad infinitum oznacza, że ​​musisz użyć algorytmu przesyłania strumieniowego zamiast algorytmu, który przyjmuje parametr n. Patrz np. Cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf
Peter Taylor
Nieskończona pamięć i nieskończony czas powinny dawać nieskończoną liczbę cyfr.
1

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.
James Holderness
źródło