Selamat Hari Pi semuanya! Tanpa alasan sama sekali, saya mencoba membuat estimator Pi Carlo yang sesingkat mungkin dari Monte Carlo. Bisakah kita membuat satu yang bisa muat dalam tweet?
Untuk memperjelas, apa yang ada dalam pikiran saya adalah pendekatan khas menggambar titik acak dari satuan kuadrat dan menghitung rasio yang termasuk dalam lingkaran satuan. Jumlah sampel dapat berupa kode keras atau tidak. Jika Anda melakukan hardcode pada mereka, Anda harus menggunakan setidaknya 1000 sampel. Hasilnya dapat dikembalikan atau dicetak sebagai titik mengambang, titik tetap atau angka rasional.
Tidak ada fungsi trigonometri atau konstanta Pi, harus merupakan pendekatan Monte Carlo.
Ini adalah kode golf, jadi pengiriman terpendek (dalam byte) menang.
sumber
((0..4e9).map{rand**2+rand**2<1}.to_s.sub(/./,"$1.")
map
memberi Anda arraytrue
danfalse
?.filter{...}.size
harus bekerja.Jawaban:
80386 kode mesin,
4038 byteHexdump kode:
Cara mendapatkan kode ini (dari bahasa assembly):
Ini adalah fungsi menggunakan
fastcall
konvensi pemanggilan MS (jumlah iterasi diteruskan dalam registerecx
). Ini mengembalikan hasil dalamst
register.Hal-hal menyenangkan tentang kode ini:
rdrand
- hanya 3 byte untuk menghasilkan angka acak!D
) dengan jari-jari kuadrat (2^32
) dilakukan secara otomatis - bendera carry berisi hasilnya.sumber
eax
; yangmul
kelipatan perintah itu dengan sendirinya dan menempatkan bagian tinggi diedx
; bagian rendah dalameax
dibuang.Matlab / Oktaf, 27 byte
Saya tahu sudah ada jawaban Matlab / Oktaf, tapi saya mencoba pendekatan saya sendiri. Saya menggunakan fakta bahwa integral
4/(1+x^2)
antara 0 dan 1 adalah pi.sumber
R, 40 (atau 28 atau 24 menggunakan metode lain)
Python 2, 56
Satu lagi Python, jika numpy diperbolehkan, tetapi sangat mirip dengan Matlab / Oktaf:
sumber
Mathematica,
424039 byte (atau 31/29?)Saya punya tiga solusi semuanya pada 42 byte:
Mereka semua adalah fungsi yang tidak disebutkan namanya yang mengambil jumlah sampel dan
n
mengembalikan rasional mendekati π. Pertama-tama mereka semua menghasilkann
poin di unit square di kuadran positif. Kemudian mereka menentukan jumlah sampel yang terletak di dalam lingkaran satuan, dan kemudian mereka membaginya dengan jumlah sampel dan mengalikannya dengan4
. Satu-satunya perbedaan adalah bagaimana mereka menentukan jumlah sampel di dalam lingkaran unit:Count
dengan syarat ituNorm[p] < 1
.1
dan kemudian mengumpulkan. Ini mengubah angka di dalam lingkaran unit ke1
dan yang di luar0
. Setelah itu saya jumlahkan semuanyaTr
.1.5
, sehingga saya dapat menggunakanRound
bukanCeiling
.Aaaaaand saat menulis ini, terpikir oleh saya bahwa memang ada solusi yang lebih pendek, jika saya hanya mengurangi
2
dan kemudian menggunakanFloor
:atau menyimpan byte lain dengan menggunakan lantai Unicode atau operator langit-langit:
Perhatikan bahwa tiga solusi berbasis pembulatan juga dapat ditulis dengan
Mean
bukanTr
dan tanpa/#
, lagi untuk byte yang sama.Jika pendekatan berbasis Monte Carlo lainnya baik-baik saja (khususnya, yang dipilih Peter), saya dapat melakukan 31 byte dengan memperkirakan integral atau 29 menggunakan integral , kali ini diberikan sebagai angka floating point:
√(1-x2)
1/(1+x2)
sumber
CJam,
27 2322 atau 20 byte2 byte disimpan berkat Runner112, 1 byte disimpan berkat Sp3000
Dibutuhkan jumlah iterasi dari STDIN sebagai input.
Ini lurus ke depan karena mendapat. Ini adalah langkah-langkah utama yang terlibat:
Perluasan kode :
Cobalah online di sini
Jika nilai rata-rata
1/(1+x^2)
juga dianggap sebagai Monte Carlo, maka ini dapat dilakukan dalam 20 byte:Coba di sini
sumber
1dmr
bukanKmrK/
, dan periksa apakah jumlah kuadrat lebih besar dari 1 dengani
alih - alih1>
(saya pikir yang ini sangat pintar) .i
trik benar-benar rapi! Dan sialnya kurangnya dokumentasi untuk1dmr
Python 2,
7775 byteMenggunakan 4000 sampel untuk menghemat byte
1e3
.sumber
...*8000;print a/2e3
.Commodore 64 Basic, 45 byte
Pergantian PETSCII:
─
=SHIFT+E
,/
=SHIFT+N
,┌
=SHIFT+O
Menghasilkan 1000 poin di kuadran pertama; untuk masing-masing, tambahkan kebenaran "x ^ 2 + y ^ 2 <1" ke hitungan berjalan, lalu bagi hitungan dengan 250 untuk mendapatkan
pi
. (Kehadiran tanda minus karena pada C64, "true" = -1.)sumber
(1)
harus dilakukan/
bukan simbol pembagian, itu karakter yang dihasilkan dengan mengetikSHIFT+N
pada keyboard Commodore 64.R/(1)
adalah cara pintas untukRND(1)
, yaitu. + msgstr "menghasilkan angka acak antara 0 dan 1 menggunakan seed RNG saat ini".J, 17 byte
Menghitung nilai rata-rata dari
40000
nilai sampel fungsi4*sqrt(1-sqr(x))
dalam rentang[0,1]
.Dengan mudah
0 o.x
kembalisqrt(1-sqr(x))
.sumber
> <> (Ikan) , 114 byte
Sekarang,> <> tidak memiliki generator angka acak bawaan. Namun ia memiliki fungsi yang mengirimkan pointer ke arah acak. Penghasil angka acak dalam kode saya:
Ini pada dasarnya menghasilkan bit acak yang membentuk angka biner dan kemudian mengonversi angka biner acak itu menjadi desimal.
Sisanya hanyalah poin reguler dalam pendekatan kuadrat.
Penggunaan: ketika Anda menjalankan kode Anda harus memastikan untuk mengisi ulang tumpukan (-v dalam python interpreter) dengan jumlah sampel, misalnya
kembali
sumber
Matlab atau Oktaf 29 byte (terima kasih kepada flawr!)
(Saya tidak yakin apakah <1 baik-baik saja. Saya membacanya harus <= 1. Tapi seberapa besar probabilitas untuk menggambar tepat 1 ...)
Matlab atau Oktaf 31 byte
sumber
mean(sum(rand(2,4e6).^2)<1)*4
.Java, 108 byte
Empat ribu iterasi, menambahkan 0,001 setiap kali titik berada di dalam lingkaran unit. Hal-hal yang cukup mendasar.
Catatan: Ya, saya tahu saya bisa menumpahkan empat byte dengan mengubah
π
ke karakter byte tunggal. Saya suka seperti ini.sumber
Javascript: 62 Bytes
Saya menggunakan jawaban javascript sebelumnya (sekarang dihapus) dan mencukur 5 byte.
sumber
GolfScript (34 karakter)
Demo online
Ini menggunakan titik tetap karena GS tidak benar-benar memiliki titik mengambang. Ini sedikit menyalahgunakan penggunaan titik tetap, jadi jika Anda ingin mengubah jumlah iterasi pastikan itu dua kali kekuatan sepuluh.
Kredit kepada xnor untuk metode Monte Carlo tertentu yang digunakan.
sumber
Python 2,
908581 bytekembali
3.14120037157
misalnya. Jumlah sampel adalah 4782969 (9 ^ 7). Anda bisa mendapatkan pi yang lebih baik dengan 9 ^ 9 tetapi Anda harus bersabar.sumber
range(9**7)
dengan[0]*9**7
atau sesuatu, karena Anda tidak menggunakannyai
. Dan daftarnya tidak terlalu lama untuk mengalami masalah memori.range()
tetapi saya benar-benar lupa trik itu.[0]9**7
bukan sintaks yang valid.Ruby, 39 byte
Salah satu yang menonjol adalah bahwa ini dapat menggunakan
8e5
notasi, yang membuatnya dapat diperpanjang hingga ~ 8e9 sampel dalam jumlah byte program yang sama.sumber
Perl 6 , 33 byte
Cobalah online!
Ini adalah fungsi yang mengambil jumlah sampel sebagai argumen.
sumber
Scala,
877766 bytesumber
1000
dengan8000
dan250d
dengan2e4
Anda berdua menghemat satu byte dan menambah jumlah sampel dengan faktor 8.Bash Murni, 65 byte
Mengambil parameter baris perintah tunggal yang dikalikan dengan 4 untuk memberikan jumlah sampel. Bash arithmetic adalah bilangan bulat saja, jadi rasional adalah output. Ini dapat disalurkan ke
bc -l
untuk divisi terakhir:sumber
Joe ,
2019 byteCatatan: jawaban ini tidak bersaing, karena versi 0.1.2, yang menambahkan keacakan, dirilis setelah tantangan ini.
Dinamakan fungsi F:
Fungsi yang tidak disebutkan namanya:
Keduanya mengambil jumlah sampel sebagai argumen dan mengembalikan hasilnya. Bagaimana mereka bekerja?
Contoh berjalan:
sumber
dc, 59 karakter (spasi kosong diabaikan)
Saya mengujinya pada Plan 9 dan OpenBSD, jadi saya bayangkan ini akan bekerja di Linux (GNU?)
dc
.Penjelasan demi baris:
i
jika 1 lebih besar dari jumlah kuadratnya] dalam registeru
.x
1] di registeri
.u
, menambah registerm
, dan kemudian menjalankan registerz
jika registerm
lebih besar dari registern
] dalam registerz
.Atur skala ke 5 poin desimal.
z
.x
(jumlah hit) dengan registern
(jumlah poin), kalikan hasilnya dengan 4, dan cetak.Namun, saya curang:
Program ini membutuhkan persediaan float acak antara 0 dan 1.
Pemakaian:
Uji coba:
Sekarang dengan lebih sedikit kecurangan (100 byte)
Seseorang menunjukkan bahwa saya dapat memasukkan prng sederhana.
http://en.wikipedia.org/wiki/RANDU
Tidak disatukan
Uji coba:
sumber
Pyth, 19
Berikan jumlah iterasi yang diinginkan sebagai input.
Demonstrasi
Karena Pyth tidak memiliki fungsi "Angka mengambang acak", saya harus berimprovisasi. Program memilih dua bilangan bulat positif acak kurang dari input, kuadrat, jumlah, dan dibandingkan dengan input kuadrat. Ini dilakukan beberapa kali sama dengan input, kemudian hasilnya dikalikan dengan 4 dan dibagi dengan input.
Dalam berita terkait, saya akan menambahkan operasi nomor floating point acak ke Pyth segera. Namun, program ini tidak menggunakan fitur itu.
Jika kita menafsirkan "Hasilnya dapat dikembalikan atau dicetak sebagai titik mengambang, titik tetap atau angka rasional." secara bebas, kemudian mencetak pembilang dan penyebut dari fraksi yang dihasilkan harus cukup. Dalam hal itu:
Pyth, 18
Ini adalah program yang identik, dengan operasi pembagian titik mengambang (
c
) dihapus.sumber
Julia, 37 byte
Jumlah sampel adalah 65536 (= 4 ^ 8).
Varian yang sedikit lebih panjang: fungsi dengan jumlah sampel
s
sebagai satu-satunya argumen:sumber
C, 130 byte
Tidak Disatukan:
sumber
f()
. Kompiler apa yang Anda gunakan? Lihat tio.run/##Pc49C4JAHIDx3U9xGMG9ZdYgwWkgtNbQ1BZ6L/UHO8M07hA/…Sebenarnya , 14 byte (tidak bersaing)
Cobalah online!
Solusi ini tidak bersaing karena bahasa tersebut mengesampingkan tantangan. Jumlah sampel diberikan sebagai input (bukan kode keras).
Penjelasan:
sumber
Racket 63 byte
Menggunakan metode jawaban bahasa R oleh @Matt:
Tidak Disatukan:
Pengujian:
Output (fraksi):
Sebagai desimal:
sumber
Fortran (GFortran) ,
8483 byteCobalah online!
Kode ini sangat buruk aja. Ini akan gagal jika gfortran memutuskan untuk menginisialisasi variabel
A
dengan nilai lain kemudian 0 (yang terjadi 50% dari kompilasi, kira-kira) dan, jikaA
diinisialisasi sebagai 0, itu akan selalu menghasilkan urutan acak yang sama untuk seed yang diberikan. Kemudian, nilai yang sama untuk Pi dicetak selalu.Ini adalah program yang jauh lebih baik:
Fortran (GFortran) ,
10099 byteCobalah online!
(Satu byte disimpan di setiap versi; terima kasih Penguino).
sumber
Japt , 26 atau 18 byte
Cobalah online!
Analog dengan jawaban Pengoptimal , terutama hanya mencoba mempelajari Japt.
Mengambil jumlah iterasi untuk dijalankan sebagai input implisit
U
.Jika
1/(1+x^2)
diizinkan (alih-alih dua random terpisah), maka kita dapat mencapai 18 byte dengan logika yang sama.sumber
Mh
menghitung sisi miring daripada melakukannya sendiri ;-) Selain itu, Anda dapat menggunakanx
untuk mengambil jumlah array, daripada mengurangi dengan menambahkan:o x@MhMr Mr)<1Ã*4/U
Mh
seperti itu, terima kasih! Jawaban dua-acak Anda hampir sependek jawaban saya dengan hanya satu acak, itu cukup keren. Saya akanx
ingat, saya cenderung menggunakan pengurangan banyak saat mencoba golf, jadi ini akan sangat berguna.F #, 149 byte
Cobalah online!
Sejauh yang saya bisa tahu, untuk melakukan ini total berjalan di F # lebih pendek untuk membuat array angka dan menggunakan
Seq.sumBy
metode daripada menggunakanfor..to..do
blok.Apa yang dilakukan kode ini yaitu membuat kumpulan angka floating-point dari 1 hingga
s
, melakukan fungsifun x->...
untuk jumlah elemen dalam koleksi, dan menjumlahkan hasilnya. Adas
elemen dalam koleksi, jadi tes acak dilakukans
kali. Angka-angka aktual dalam koleksi diabaikan (fun x->
, tetapix
tidak digunakan).Ini juga berarti bahwa aplikasi harus terlebih dahulu membuat dan mengisi array, dan kemudian beralih di atasnya. Jadi itu mungkin dua kali lebih lambat dari
for..to..do
loop. Dan dengan penggunaan array penciptaan memori di wilayah O (f ** k)!Untuk tes yang sebenarnya itu sendiri, alih-alih menggunakan
if then else
pernyataan apa yang dilakukannya adalah menghitung jarak (q()+q()|>Math.Sqrt
) dan membulatkannya ke bawahMath.Floor
. Jika jarak di dalam lingkaran, itu akan dibulatkan ke 0. Jika jarak di luar lingkaran itu akan dibulatkan ke 1.Seq.sumBy
Metode kemudian akan total hasil ini.Perhatikan bahwa yang
Seq.sumBy
telah dijumlahkan bukanlah titik di dalam lingkaran, tetapi titik di luarnya . Jadi untuk hasilnya dibutuhkans
(ukuran sampel kami) dan kurangi total dari itu.Tampaknya juga bahwa mengambil ukuran sampel sebagai parameter lebih pendek daripada mengkodekan nilainya. Jadi saya selingkuh sedikit ...
sumber
Haskell,
11611411096 byteKarena berurusan dengan
import System.Random; r=randoms(mkStdGen 2)
akan mengambil terlalu banyak byte yang berharga, saya menghasilkan daftar angka acak tak terbatas dengan generator kongruensi linear yang beberapa orang katakan hampir kuat secara kriptografis:,x↦x*9+1 mod 8^9
yang oleh Teorema Hull-Dobell memiliki periode penuh8^9
.g
menghasilkan4
jika titik angka acak berada di dalam lingkaran untuk pasangan angka acak[0..8^9-1]
karena ini menghilangkan perkalian dalam rumus yang digunakan.Pemakaian:
Cobalah online!
sumber
Perl 5, 34 byte
Jumlah sampel diambil dari stdin. Membutuhkan
-p
.Berfungsi karena:
Cobalah online!
sumber