Transmitir Pi ... precisamente

11

Siguiendo el estimador de Pi de Monte Carlo, este desafío es producir el código más corto para el Pi constante. Excepto aquí, su código debe generar dígitos consecutivos de pi para siempre.

Este es el código de golf, por lo que el envío más corto (en bytes) gana, excepto que debe generar los primeros 10,000 dígitos en menos de 10 segundos en una PC razonable y nunca debe terminar.

No puede usar ninguna función incorporada para Pi o trigonométricas.


Se eliminó el límite estricto en el tamaño del código.

Comunidad
fuente
1
Por tweetable, ¿quiere decir que el código debe tener menos de 140 caracteres?
Ypnypn
55
El problema en sí mismo parece desafiante sin la limitación de caracteres.
BobTheAwesome
1
@BobTheAwesome Se eliminó el límite de caracteres por demanda popular.
1
@ mbomb007 No es obvio en absoluto que el punto decimal deba imprimirse o que los dígitos no se separen con espacios en blanco. El desafío es simplemente "generar dígitos consecutivos de pi". El punto decimal no es un dígito. 3141...es eso: dígitos consecutivos de pi.
orlp
1
Sería mejor si el número impreso fuera Pi para que no haya espacio entre los dígitos, por ejemplo. Sería aún mejor si incluyera el punto decimal.

Respuestas:

7

CJam - 48

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

Esto calcula π como 2 * suma (k! / (2k + 1) !!) con mayor y mayor precisión y en cada paso imprime un montón de dígitos desde donde se quedó.

Puede probar en línea una versión modificada que solo realiza 8 iteraciones (bucle externo) e imprime 512 dígitos, o usar el intérprete de Java para la cosa real. En mi computadora portátil llega a 16384 dígitos en aproximadamente 6 segundos.

Nota: este programa consume mucha memoria; una versión con mejor comportamiento pero un poco más larga es:

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

Explicación:

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 renunció porque SE es MALO
fuente
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

Implementación de http://www.cs.ox.ac.uk/jeremy.gibbons/publications/spigot.pdf .

orlp
fuente
Golpéame
Esto es genial. Sin embargo, esperaba que los dígitos estuvieran todos en una línea. En otras palabras, que la salida se parecería a Pi.
2
@Lembik Cambié mi respuesta: 7 bytes más, pero ahora todo en una línea.
orlp
5

GolfScript (81 caracteres)

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

Demostración en línea (eso es mucho más lento que un escritorio razonable y tiene cambios de código triviales para recorrer un número finito de veces).

Por supuesto, he usado el algoritmo de espita que mencioné en un comentario anterior, pero me tomó un tiempo jugarlo a mi satisfacción. El algoritmo presentado en el artículo de Gibbons es (pseudocódigo)

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
}

El GolfScript anterior es equivalente a (pseudocódigo)

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
}

que guarda algunos caracteres en la inicialización y en la gestión de la pila.

Peter Taylor
fuente
4

Pyth - 87 85 bytes

Otra traducción de http://www.cs.ox.ac.uk/jeremy.gibbons/publications/spigot.pdf . Iba a hacer Python pero @orlp me ganó, así que hice Pyth. Lo suficientemente pequeño como para caber en un tweet.

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

Da salida a stdout, aunque en pasos intermitentes debido al búfer de impresión que proviene de la configuración end=""en la impresión. Actualmente no imprimo el punto decimal ya que la especificación dice "dígitos consecutivos". Son las tareas las que están matando mi puntaje.

=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

Pruébalo aquí . (Nota: dado que el intérprete en línea solo da resultados completos, el bucle infinito está desactivado, por lo que solo imprime los primeros 100, lo que aumenta el tamaño del código. Para probar infinito, descargue el intérprete local).

Sincronización

En mi micro instancia de computación en la nube de Google, de acuerdo con el tiempo de GNU que tomó: real: 0m2.062spor lo tanto, obviamente es lo suficientemente rápido.

Maltysen
fuente
3

Scala, 599 bytes

El siguiente código es un puerto directo del código Pascal del Apéndice 2 del Algoritmo A Spigot para los Dígitos de Pi . Claramente, se ha hecho muy poco golf. El código genera 10,000 dígitos en menos de 10 segundos piSpigot(10000)y, si uno tiene memoria infinita, se puede parametrizar para generar muchos dígitos, pero no infinito. No estoy seguro de si esto está cumpliendo las limitaciones del problema, así que por favor envíe sus comentarios.

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
fuente
55
Creo que el requisito de producir dígitos hasta el infinito significa que debe usar un algoritmo de transmisión en lugar de uno que tome un parámetro n. Véase, por ejemplo, cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf
Peter Taylor el
La memoria infinita y el tiempo infinito deberían dar un número infinito de dígitos.
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<

Pruébalo en línea!

Esto es límite en términos del límite de tiempo. 10,000 dígitos toman alrededor de 11 segundos en mi computadora portátil, pero estoy seguro de que debe haber una PC "razonable" que pueda hacerlo más rápido que eso.

Sin embargo, si lo está probando en TIO, tenga en cuenta que no devolverá nada hasta que alcance el límite de tiempo de 60 segundos, ya que el algoritmo está diseñado para seguir funcionando para siempre. Sin embargo, para entonces tendrás más de 10,000 dígitos.

Estoy usando el algoritmo de espita Jeremy Gibbons, que creo que es el mismo que la mayoría de las otras respuestas aquí. Sin embargo, tenga en cuenta que esto depende de que el intérprete tenga celdas de memoria de precisión arbitrarias, y la única implementación que conozco que admite es PyFunge .

Explicación

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
fuente