Senden Sie Pi… genau

11

In Anlehnung an den Monte-Carlo-Schätzer von Pi besteht diese Herausforderung darin, den kürzesten Code für die Konstante Pi zu erzeugen. Außer hier muss Ihr Code für immer aufeinanderfolgende Ziffern von pi ausgeben.

Dies ist Code Golf, daher gewinnt die kürzeste Übermittlung (in Bytes), außer dass die ersten 10.000 Ziffern in weniger als 10 Sekunden auf einem vernünftigen PC ausgegeben werden müssen und niemals beendet werden dürfen.

Sie können keine integrierten Funktionen für Pi oder Trigger verwenden.


Die feste Grenze für die Codegröße wurde entfernt.

Gemeinschaft
quelle
1
Meinen Sie mit tweetable, dass der Code weniger als 140 Zeichen enthalten muss?
Ypnypn
5
Das Problem an sich scheint ohne die Zeichenbeschränkung herausfordernd zu sein.
BobTheAwesome
1
@BobTheAwesome Die Zeichenbeschränkung wurde auf vielfachen Wunsch entfernt.
1
@ mbomb007 Es ist überhaupt nicht offensichtlich, dass der Dezimalpunkt gedruckt werden muss oder dass die Ziffern möglicherweise nicht durch Leerzeichen getrennt sind. Die Herausforderung besteht lediglich darin, "aufeinanderfolgende Ziffern von pi auszugeben". Der Dezimalpunkt ist keine Ziffer. 3141...ist das - aufeinanderfolgende Ziffern von pi.
Orlp
1
Es wäre am besten, wenn die ausgedruckte Zahl Pi wäre, sodass beispielsweise kein Leerzeichen zwischen den Ziffern vorhanden wäre. Es wäre sogar noch besser, wenn es den Dezimalpunkt enthalten würde.

Antworten:

7

CJam - 48

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

Dies berechnet π als 2 * Summe (k! / (2k + 1) !!) mit immer größerer Genauigkeit und druckt bei jedem Schritt eine Reihe von Ziffern, von denen es aufgehört hat.

Sie können online eine modifizierte Version ausprobieren , die nur 8 Iterationen (äußere Schleife) ausführt und 512 Ziffern druckt, oder den Java-Interpreter für die reale Sache verwenden. Auf meinem Laptop werden es in ungefähr 6 Sekunden 16384 Stellen.

Hinweis: Dieses Programm ist sehr speicherhungrig. Eine besser erzogene, aber etwas längere Version ist:

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

Erläuterung:

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 beenden, weil SE böse ist
quelle
8

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

Implementierung von http://www.cs.ox.ac.uk/jeremy.gibbons/publications/spigot.pdf .

orlp
quelle
Schlagen
Das ist toll. Ich hatte jedoch gehofft, dass die Ziffern alle in einer Zeile stehen würden. Mit anderen Worten, dass die Ausgabe wie Pi aussehen würde.
2
@Lembik Ich habe meine Antwort geändert - 7 Bytes länger, aber jetzt alle in einer Zeile.
Orlp
5

GolfScript (81 Zeichen)

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

Online-Demo (das ist viel langsamer als ein vernünftiger Desktop und hat triviale Codeänderungen, um eine endliche Anzahl von Schleifen durchzuführen).

Ich habe natürlich den Zapfenalgorithmus verwendet, den ich in einem früheren Kommentar erwähnt habe, aber ich habe eine Weile gebraucht, um ihn zu meiner Zufriedenheit zu spielen. Der in Gibbons 'Arbeit vorgestellte Algorithmus ist (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
}

Das obige GolfScript entspricht (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
}

Dadurch werden einige Zeichen bei der Initialisierung und bei der Stapelverwaltung gespeichert.

Peter Taylor
quelle
4

Pyth - 87 85 Bytes

Eine weitere Übersetzung von http://www.cs.ox.ac.uk/jeremy.gibbons/publications/spigot.pdf . Ich wollte Python machen, aber @orlp hat mich geschlagen, also habe ich Pyth gemacht. Klein genug, um in einen Tweet zu passen.

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

Es gibt eine Ausgabe an stdout aus, wenn auch in intermittierenden Schritten, da der Druckpuffer aus der Druckeinstellung stammt end="". Ich drucke derzeit keinen Dezimalpunkt, da in der Spezifikation "aufeinanderfolgende Ziffern" steht. Es sind die Aufgaben, die meine Punktzahl töten.

=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

Probieren Sie es hier aus . (Hinweis: Da der Online-Interpreter nur vollständige Ergebnisse liefert, ist die Endlosschleife ausgefallen, sodass nur die ersten 100 gedruckt werden, wodurch sich die Codegröße erhöht. Laden Sie den lokalen Interpreter herunter, um die Endlosversion auszuprobieren.)

Zeitliche Koordinierung

Auf meiner Google Cloud Compute-Mikroinstanz hat es laut Gnu-Zeit gedauert: real: 0m2.062sEs ist also offensichtlich schnell genug.

Maltysen
quelle
3

Scala, 599 Bytes

Der folgende Code ist ein gerader Port des Pascal-Codes aus Anhang 2 eines Spigot-Algorithmus für die Ziffern von Pi . Offensichtlich wurde noch sehr wenig Golf gespielt. Der Code generiert 10.000 Ziffern in piSpigot(10000)weniger als 10 Sekunden mit und wenn man einen unendlichen Speicher hat, kann er so parametrisiert werden, dass er viele Ziffern erzeugt, aber nicht unendlich. Ich bin nicht sicher, ob dies die Problembeschränkungen erfüllt. Bitte geben Sie 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)
Dave Swartz
quelle
5
Ich denke, dass die Anforderung, Ziffern ad infinitum zu erzeugen, bedeutet, dass Sie einen Streaming-Algorithmus verwenden müssen, anstatt einen, der einen Parameter verwendet n. Siehe z. B. cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf
Peter Taylor
Unendlicher Speicher und unendliche Zeit sollten eine unendliche Anzahl von Ziffern ergeben.
1

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<

Probieren Sie es online aus!

Dies ist eine Grenze in Bezug auf das Zeitlimit. 10.000 Stellen dauern auf meinem Laptop ungefähr 11 Sekunden, aber ich bin mir sicher, dass es einen "vernünftigen" PC geben muss, der dies schneller kann.

Wenn Sie es jedoch auf TIO ausprobieren, beachten Sie, dass es nichts zurückgibt, bis das Zeitlimit von 60 Sekunden erreicht ist, da der Algorithmus so konzipiert ist, dass er für immer weitergeht. Zu diesem Zeitpunkt haben Sie jedoch weit mehr als 10.000 Stellen.

Ich verwende den Jeremy Gibbons-Zapfenalgorithmus, der meiner Meinung nach mit den meisten anderen Antworten hier identisch ist. Beachten Sie jedoch, dass dies davon abhängt , dass der Interpreter über Speicherzellen mit beliebiger Genauigkeit verfügt. Die einzige mir bekannte Implementierung, die dies unterstützt, ist PyFunge .

Erläuterung

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
quelle