Dans la continuité de l'estimateur de Monte Carlo de Pi, ce défi consiste à produire le code le plus court pour la constante Pi. Sauf qu'ici, votre code doit produire des chiffres consécutifs de pi pour toujours.

Il s'agit du code golf, donc la soumission la plus courte (en octets) gagne, sauf qu'elle doit sortir les 10 000 premiers chiffres en moins de 10 secondes sur un PC raisonnable et ne doit jamais se terminer.

Vous ne pouvez pas utiliser de fonctions intégrées pour Pi ou trig.

Suppression de la limite stricte sur la taille du code.

CJam - 48

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

Cela calcule π comme 2 * somme (k! / (2k + 1) !!) avec une précision de plus en plus grande et à chaque étape imprime un tas de chiffres d'où il s'était arrêté.

Vous pouvez essayer en ligne une version modifiée qui ne fait que 8 itérations (boucle externe) et imprime 512 chiffres, ou utiliser l' interpréteur java pour la vraie chose. Sur mon ordinateur portable, il atteint 16384 chiffres en environ 6 secondes.

Remarque: ce programme est très gourmand en mémoire; une version mieux comportée mais légèrement plus longue est:

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

Explication:

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 octets

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

Implémentation de http://www.cs.ox.ac.uk/jeremy.gibbons/publications/spigot.pdf .

GolfScript (81 caractères)

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

Démonstration en ligne (qui est beaucoup plus lente qu'un ordinateur de bureau raisonnable et a des changements de code triviaux pour boucler un nombre fini de fois).

J'ai, bien sûr, utilisé l'algorithme de spigot que j'ai mentionné dans un commentaire précédent, mais il m'a fallu un certain temps pour le jouer à ma satisfaction. L'algorithme tel que présenté dans l'article de Gibbons est (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
}

Le GolfScript ci-dessus est équivalent à (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
}

ce qui enregistre certains caractères dans l'initialisation et dans la gestion de la pile.

Pyth - 87 85 octets

Une autre traduction de http://www.cs.ox.ac.uk/jeremy.gibbons/publications/spigot.pdf . J'allais faire Python mais @orlp m'a battu, alors j'ai fait Python. Assez petit pour tenir dans un tweet.

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

Il donne la sortie à stdout, bien que par étapes intermittentes en raison du tampon d'impression qui provient de la configuration end=""de l'impression. Je n'imprime actuellement pas la virgule décimale car la spécification dit "chiffres consécutifs". Ce sont les affectations qui tuent mon 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

Essayez-le ici . (Remarque: Étant donné que l'interpréteur en ligne ne donne que des résultats complets, la boucle infinie est désactivée, il n'imprime donc que les 100 premiers, ce qui augmente la taille du code. Pour essayer l'infini, téléchargez l'interpréteur local.)

Horaire

Sur ma micro-instance de Google Cloud Compute, selon le temps GNU qu'il a fallu: real: 0m2.062sil est donc évidemment assez rapide.

Scala, 599 octets

Le code ci-dessous est un port direct du code Pascal de l'annexe 2 de A Spigot Algorithm for the Digits of Pi . Il est clair que très peu de golf a encore été fait. Le code génère 10 000 chiffres en moins de 10 secondes avec piSpigot(10000)et si l'un a une mémoire infinie, il peut être paramétré pour générer de nombreux chiffres, mais pas infini. Je ne sais pas si cela répond aux contraintes du problème, veuillez donc fournir des commentaires.

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 octets

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<

Essayez-le en ligne!

C'est limite en termes de délai. 10 000 chiffres prennent environ 11 secondes sur mon ordinateur portable, mais je suis sûr qu'il doit y avoir un PC "raisonnable" qui pourrait le faire plus rapidement que cela.

Cependant, si vous l'essayez sur TIO, notez qu'il ne retournera rien tant qu'il n'aura pas atteint le délai de 60 secondes, car l'algorithme est conçu pour continuer indéfiniment. À ce moment-là, vous aurez bien plus de 10 000 chiffres.

J'utilise l'algorithme de broche Jeremy Gibbons, qui je pense est le même que la plupart des autres réponses ici. Cependant, notez que cela repose sur l'interpréteur ayant des cellules de mémoire de précision arbitraire, et la seule implémentation que je connaisse qui prend en charge c'est PyFunge .

Explication

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.