Sebagai lanjutan dari estimasi Monte Carlo tentang Pi , tantangan ini adalah menghasilkan kode terpendek untuk Pi konstan. Kecuali di sini, kode Anda harus menampilkan digit pi berturut-turut selamanya.

Ini adalah kode golf, jadi pengiriman terpendek (dalam byte) menang kecuali bahwa ia harus menampilkan 10.000 digit pertama dalam waktu kurang dari 10 detik pada PC yang masuk akal dan tidak boleh diakhiri.

Anda tidak dapat menggunakan built-in untuk fungsi Pi atau trigonometri.

Menghapus batas keras pada ukuran kode.

CJam - 48

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

Ini menghitung π sebagai 2 * jumlah (k! / (2k + 1) !!) dengan presisi yang lebih besar dan lebih besar dan pada setiap langkah mencetak sekelompok angka dari tempat sebelumnya.

Anda dapat mencoba online versi modifikasi yang hanya melakukan 8 (loop luar) iterasi dan mencetak 512 digit, atau menggunakan penerjemah java untuk hal yang nyata. Di laptop saya, ia mencapai 16384 digit dalam waktu sekitar 6 detik.

Catatan: program ini sangat haus akan memori; versi yang berperilaku lebih baik tetapi sedikit lebih lama adalah:

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

Penjelasan:

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 byte

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

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

GolfScript (81 karakter)

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

Demo online (itu jauh lebih lambat dari desktop yang masuk akal, dan memiliki perubahan kode sepele untuk mengulang beberapa kali hingga).

Saya, tentu saja, menggunakan algoritma keran yang saya sebutkan di komentar sebelumnya, tetapi butuh beberapa saat untuk menyesuaikannya dengan kepuasan saya. Algoritma seperti yang disajikan dalam makalah Gibbons adalah (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
}

GolfScript di atas setara dengan (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
}

yang menyimpan beberapa karakter dalam inisialisasi dan manajemen tumpukan.

Pyth - 87 85 byte

Terjemahan lain dari http://www.cs.ox.ac.uk/jeremy.gibbons/publications/spigot.pdf . Saya akan melakukan Python tetapi @orlp mengalahkan saya untuk itu, jadi saya melakukan Pyth. Cukup kecil untuk muat dalam tweet.

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

Ini memberikan output ke stdout, meskipun dalam langkah-langkah intermiten karena buffer cetak yang berasal dari pengaturan end=""cetak. Saat ini saya tidak mencetak titik desimal karena spec mengatakan "digit berurutan". Ini adalah tugas yang membunuh nilaiku.

=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

Coba di sini . (Catatan: Karena penerjemah online hanya memberikan hasil yang selesai, infinite loop keluar, sehingga hanya mencetak 100 yang menambah ukuran kode. Untuk mencoba infinite, unduh penerjemah lokal.)

Pengaturan waktu

Di google cloud saya menghitung instance mikro, menurut gnu waktu yang dibutuhkan: real: 0m2.062sjadi itu jelas cukup cepat.

Scala, 599 byte

Kode di bawah ini adalah port langsung dari kode Pascal dari Lampiran 2 dari Algoritma Spigot untuk Digit Pi . Jelas sangat sedikit golf belum dilakukan. Kode tidak menghasilkan 10.000 digit dalam waktu kurang dari 10 detik dengan piSpigot(10000)dan jika seseorang memiliki memori tak terbatas dapat diparameterisasi untuk menghasilkan banyak digit, tetapi tidak terbatas. Saya tidak yakin apakah ini memenuhi kendala masalah, jadi silakan berikan umpan balik.

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 byte

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<

Cobalah online!

Ini adalah batas dalam hal timelimit. 10.000 digit memakan waktu sekitar 11 detik di laptop saya, tapi saya yakin pasti ada PC yang "masuk akal" yang bisa melakukannya lebih cepat dari itu.

Namun, jika Anda mencobanya di TIO, perhatikan bahwa itu tidak akan mengembalikan apa pun hingga mencapai batas waktu 60 detik, karena algoritma ini dirancang untuk terus berjalan selamanya. Pada saat itu Anda akan memiliki lebih dari 10.000 digit.

Saya menggunakan algoritma keran Jeremy Gibbons, yang menurut saya sama dengan sebagian besar jawaban lain di sini. Namun, perhatikan bahwa ini bergantung pada juru bahasa yang memiliki sel-sel memori presisi yang sewenang-wenang, dan satu-satunya implementasi yang saya ketahui yang mendukungnya adalah PyFunge .

Penjelasan

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.