Pertanyaan Kode Golf: Rumus Leibniz untuk Pi


Saya baru-baru ini diposting salah satu pertanyaan kode papan tulis wawancara favorit saya di "Apa pendapat pemrograman Anda yang lebih kontroversial", yang menulis fungsi yang menghitung Pi menggunakan Rumus Leibniz.

Ini dapat didekati dengan beberapa cara yang berbeda, dan kondisi keluar membutuhkan sedikit pemikiran, jadi saya pikir itu mungkin membuat pertanyaan golf kode yang menarik. Kemenangan kode terpendek!

Mengingat bahwa Pi dapat diperkirakan menggunakan fungsi 4 * (1 - 1/3 + 1/5 - 1/7 + ...) dengan lebih banyak istilah yang memberikan akurasi lebih tinggi, tulis fungsi yang menghitung Pi ke dalam 0,00001.

Sunting: 3 Januari 2008

Seperti yang disarankan dalam komentar saya mengubah kondisi keluar menjadi dalam 0,00001 karena itulah yang saya maksudkan (akurasi 5 desimal jauh lebih sulit karena pembulatan dan jadi saya tidak ingin menanyakannya dalam sebuah wawancara, sedangkan dalam 0,00001 adalah lebih mudah untuk memahami dan mengimplementasikan kondisi keluar).

Juga, untuk menjawab komentar, saya kira maksud saya adalah bahwa solusinya harus menghitung jumlah iterasi, atau periksa ketika itu sudah cukup, tetapi tidak ada yang mencegah Anda dari pra-menghitung jumlah iterasi dan menggunakan nomor itu. Saya benar-benar mengajukan pertanyaan yang menarik untuk melihat apa yang akan dihasilkan oleh orang-orang.


31


asal


Jawaban:


J, 14 karakter

4*-/%>:+:i.1e6

Penjelasan

  • 1e6 adalah nomor 1 diikuti oleh 6 nol (1000000).
  • i.y menghasilkan yang pertama y nomor non negatif.
  • +: adalah fungsi yang menggandakan setiap elemen dalam argumen daftar.
  • >: adalah fungsi yang bertambah oleh masing-masing elemen dalam argumen daftar.

Jadi, ekspresinya >:+:i.1e6 menghasilkan satu juta bilangan ganjil pertama:

1 3 5 7 ...

  • % adalah operator timbal balik (pembilang "1" dapat dihilangkan).
  • -/ melakukan jumlah alternatif dari setiap elemen dalam argumen daftar.

Jadi, ekspresinya -/%>:+:i.1e6 menghasilkan jumlah alternatif dari timbal balik dari satu juta bilangan ganjil pertama:

1 - 1/3 + 1/5 - 1/7 + ...

  • 4* adalah perkalian dengan empat. Jika Anda mengalikan dengan empat jumlah sebelumnya, Anda memiliki π.

Itu dia! J adalah bahasa yang kuat untuk matematika.


Edit: sejak menghasilkan 9! (362880) istilah untuk jumlah alternatif cukup untuk memiliki 5 ketepatan angka desimal, dan karena rumus Leibniz dapat ditulis juga dengan cara ini:

4 - 4/3 + 4/5 - 4/7 + ...

... Anda bisa menulis lebih pendek, 12 karakter versi program:

-/4%>:+:i.9!

61



Bahasa: Brainfuck, Char count: 51/59

Apakah ini dihitung? =]

Karena tidak ada angka floating-point di Brainfuck, itu cukup sulit untuk membuat divisi bekerja dengan baik. Grr.

Tanpa baris baru (51):

+++++++[>+++++++<-]>++.-----.+++.+++.---.++++.++++.

Dengan baris baru (59):

+++++++[>+++++++>+<<-]>++.-----.+++.+++.---.++++.++++.>+++.

37



Perl

26 karakter

Hanya 26 fungsi, 27 untuk menghitung, 31 untuk mencetak. Dari komentar ke jawaban ini.

sub _{$-++<1e6&&4/$-++-&_}       # just the sub
sub _{$-++<1e6&&4/$-++-&_}_      # compute
sub _{$-++<1e6&&4/$-++-&_}say _  # print

28 karakter

28 hanya komputer, 34 untuk mencetak. Dari komentar. Perhatikan bahwa versi ini tidak dapat menggunakan 'katakan'.

$.=.5;$\=2/$.++-$\for 1..1e6        # no print
$.=.5;$\=2/$.++-$\for$...1e6;print  # do print, with bonus obfuscation

36 karakter

36 hanya komputer, 42 untuk mencetak. Pengambilan Hudson pada penataan ulang sepihak, dari komentar.

$/++;$\+=8/$//($/+2),$/+=4for$/..1e6
$/++;$\+=8/$//($/+2),$/+=4for$/..1e6;print

Tentang hitungan iterasi: sejauh memori matematika saya pergi, 400000 cukup terbukti akurat hingga 0,00001. Tapi sejuta (atau serendah 8e5) sebenarnya membuat ekspansi desimal benar-benar cocok dengan 5 tempat pecahan, dan itu jumlah karakter yang sama jadi saya terus itu.


24



Ruby, 33 karakter

(0..1e6).inject{|a,b|2/(0.5-b)-a}

23



Versi C # lainnya:

(60 karakter)

4*Enumerable.Range(0, 500000).Sum(x => Math.Pow(-1, x)/(2*x + 1));  // = 3,14159

20



52 karakter dalam Python:

print 4*sum(((-1.)**i/(2*i+1)for i in xrange(5**8)))

(51 menjatuhkan 'x' dari xrange.)

36 karakter dalam Oktaf (atau Matlab):

l=0:5^8;disp((-1).^l*(4./(2.*l+1))')

(jalankan "format panjang;" untuk menunjukkan semua angka signifikan.) Menghilangkan 'disp' kita mencapai 30 karakter:

octave:5> l=0:5^8;(-1).^l*(4./(2.*l+1))'
ans = 3.14159009359631

14



Oracle SQL 73 karakter

select -4*sum(power(-1,level)/(level*2-1)) from dual connect by level<1e6

13



Bahasa: C, jumlah Char: 71

float p;main(i){for(i=1;1E6/i>5;i+=2)p-=(i%4-2)*4./i;printf("%g\n",p);}

Bahasa: C99, Jumlah Char: 97 (termasuk diperlukan baris baru)

#include <stdio.h>
float p;int main(){for(int i=1;1E6/i>5;i+=2)p-=(i%4-2)*4./i;printf("%g\n",p);}

Saya harus mencatat bahwa versi di atas (yang sama) melacak apakah iterasi tambahan akan mempengaruhi hasilnya sama sekali. Dengan demikian, ia melakukan sejumlah operasi minimum. Untuk menambahkan lebih banyak digit, ganti 1E6 dengan 1E(num_digits+1) atau 4E5 dengan 4E(num_digits) (tergantung pada versinya). Untuk program lengkap, %g mungkin perlu diganti. float mungkin perlu diubah menjadi double demikian juga.

Bahasa: C, jumlah Char: 67 (lihat catatan)

double p,i=1;main(){for(;i<1E6;i+=4)p+=8/i/(i+2);printf("%g\n",p);}

Versi ini menggunakan versi modifikasi dari algoritma yang diposting, seperti yang digunakan oleh beberapa jawaban lainnya. Juga, tidak begitu bersih / efisien sebagai dua solusi pertama, karena memaksa 100 000 iterasi daripada mendeteksi ketika iterasi menjadi tidak berarti.

Bahasa: C, Char count: 24 (curang))

main(){puts("3.14159");}

Tidak berfungsi dengan jumlah digit> 6, sekalipun.


10



Haskell

Saya mendapatkannya hingga 34 karakter:

foldl subtract 4$map(4/)[3,5..9^6]

Ungkapan ini menghasilkan 3.141596416935556 ketika dievaluasi.

Edit: inilah versi yang agak lebih pendek (pada 33 karakter) yang menggunakan foldl1, bukan foldl:

foldl1 subtract$map(4/)[1,3..9^6]

Edit 2: 9 ^ 6, bukan 10 ^ 6. Satu harus ekonomis;)

Edit 3: Diganti dengan foldl 'dan foldl1' dengan lipatan dan foldl1 masing-masing — sebagai hasil dari Edit 2, itu tidak lagi meluap. Terima kasih kepada ShreevatsaR untuk memperhatikan ini.


10



23 karakter dalam MATLAB:

a=1e6;sum(4./(1-a:4:a))

10



F #:

Mencoba # 1:

let pi = 3.14159

Curang? Tidak, kemenangannya dengan gaya!

Mencoba # 2:


let pi =
    seq { 0 .. 100 }
    |> Seq.map (fun x -> float x)
    |> Seq.fold (fun x y -> x + (Math.Pow(-1.0, y)/(2.0 * y + 1.0))) 0.0
    |> (fun x -> x * 4.0)


9