Pi kali e (atau Pai jika Anda suka notasi ambigu) ke 100 tempat desimal adalah:
8.5397342226735670654635508695465744950348885357651149618796011301792286111573308075725638697104739439...
( OIES A019609 ) ( argumen untuk kemungkinan irasionalitas )
Tugas Anda adalah menulis sebuah program yang menghasilkan bilangan bulat positif N, dan menghasilkan Pi * e yang terpotong ke N tempat desimal. misal jika N = 2, maka output seharusnya 8.53
.
Ini adalah masalah optimisasi, sehingga pengiriman yang dapat memberikan output yang benar untuk nilai N tertinggi akan menang.
Untuk memastikan semua kiriman dinilai menggunakan kekuatan komputasi yang sama, kode Anda harus dijalankan pada ideone , menggunakan bahasa apa pun yang mereka dukung. Menurut faq ideone , ada batas waktu 5 detik untuk pengguna yang tidak masuk. Batas 5 detik ini adalah yang harus Anda gunakan, bukan batas 15 detik untuk pengguna yang masuk. (Lihat faq untuk batas lain seperti memori, ukuran kode, dll.)
Khususnya, siapa pun yang tidak masuk ke ideone harus dapat menjalankan program Anda pada ideone untuk semua nilai N dari 1 hingga beberapa Nmax maksimum, dan melihat output yang benar hampir sepanjang waktu . tanpa kesalahan Time limit exceeded
atau Memory limit exceeded
, dll. Pengajuan dengan Nmax terbesar akan menang.
(Apakah waktu sebenarnya yang diperlukan adalah smidge lebih dari 5 detik tidak masalah asalkan ideone tidak memberikan kesalahan. " Hampir sepanjang waktu " didefinisikan sebagai lebih dari 95% waktu untuk setiap N. tertentu)
Detail
- Anda dapat menggunakan metode matematika apa pun yang Anda suka untuk menghitung Pi * e, tetapi Anda tidak dapat meng-hardcode output di luar selusin digit pertama dari Pi, e atau Pi * e .
- Program Anda harus dapat bekerja untuk N apa pun, mengingat sumber daya tidak terbatas.
- Anda dapat menggunakan konstanta built in Pi atau e jika bahasa Anda kebetulan memilikinya.
- Anda tidak boleh mengakses situs web atau sumber daya di luar kode Anda (jika ideone bahkan mengizinkan ini).
- Di luar hardcoding dan mengakses sumber daya eksternal, apa pun yang memungkinkan ideone hampir pasti baik-baik saja.
- Input dan output Anda harus (jelas) bekerja dengan apa pun yang disediakan ideone untuk i / o (hanya stdin / stdout). Tidak apa-apa jika Anda perlu tanda kutip di sekitar input N atau outputnya seperti
ans = ...
, dll. - Harap sertakan tautan ke cuplikan ideone kode Anda dengan Nmax Anda sebagai masukan.
- Jika ada ikatan (kemungkinan hanya jika banyak pengiriman mencapai batas karakter keluaran 64kB) jawaban suara tertinggi menang.
sumber
Jawaban:
Python - 65535
http://ideone.com/knKRhn
Ideone tampaknya tidak
gmpy2
diinstal, yang sangat disayangkan karena setidaknya dua alasan. Satu, karena itu akan membuat perhitungan jauh lebih cepat, dan dua, karena itu membuat formula apa pun yang membutuhkan akar kuadrat presisi yang sewenang-wenang tidak praktis.Rumus saya gunakan untuk π telah terdaftar oleh Ramanujan sebagai Formula (39):
yang konvergen pada tingkat ~ 5,89 digit per term. Sepengetahuan saya, ini adalah seri konvergen tercepat dari jenisnya yang tidak memerlukan evaluasi dari akar kuadrat presisi arbitrer. Formula (44) di koran yang sama (tingkat konvergensi ~ 7.98 digit per istilah) yang paling sering disebut sebagai the Formula Ramanujan.
Rumus yang saya gunakan untuk e adalah jumlah faktorial terbalik. Jumlah istilah yang diperlukan dihitung sebagai Γ -1 ( 10 n ), menggunakan perkiraan yang saya temukan pada mathoverflow . Komponen Lambert W 0 ditemukan menggunakan Metode Newton.
Perhitungan masing-masing penjumlahan ini dilakukan melalui Fast E-function Evalution (lebih dikenal sebagai binary-splitting), yang awalnya dirancang oleh Karatsuba. Metode ini mengurangi penjumlahan ke n istilah menjadi nilai rasional tunggal p / q . Kedua nilai ini kemudian dikalikan untuk menghasilkan hasil akhir.
Pembaruan:
Pembuatan profil mengungkapkan bahwa lebih dari separuh waktu yang dibutuhkan untuk perhitungan dihabiskan di divisi akhir. Hanya sebagian besar log 2 (10 n ) bit q yang diperlukan untuk mendapatkan presisi penuh, jadi saya memotong beberapa sebelumnya. Kode sekarang mengisi buffer output Ideone dalam 3,33s .
Pembaruan 2:
Karena ini adalah tantangan pengoptimalan , saya memutuskan untuk menulis rutin divisi saya sendiri untuk memerangi kelambatan CPython. Implementasi di
divnr
atas menggunakan Divisi Newton-Raphson . Gagasan umum adalah menghitung d = 1 / q · 2 n menggunakan Metode Newton, di mana n adalah jumlah bit yang dibutuhkan oleh hasil, dan menghitung hasilnya sebagai p · d >> n . Runtime sekarang 2.87s - dan ini bahkan tanpa memotong bit sebelum perhitungan; itu tidak perlu untuk metode ini.sumber
PARI / GP: 33000
Ini pada dasarnya adalah program yang diberikan di OEIS , dimodifikasi untuk mengambil input dan memformat output dengan benar. Ini harus berfungsi sebagai garis dasar untuk dikalahkan, jika tidak ada yang lain.
Saya menganggap ini akurat. Saya memeriksanya pada 100 dan 20k melawan OEIS, dan cocok untuk keduanya. Cukup sulit menemukan digit lebih lanjut daring untuk diperiksa.
Untuk 33.000 dibutuhkan sekitar 4,5s, jadi mungkin bisa sedikit menabrak. Saya baru saja bosan mengutak-atik input dan lambat-ass loop / assile / run loop ideone.
Tautan Ideone.com
sumber
Str(floor(frac(x)*10^m)
berjalan ratusan / ribuan kali lebih cepat.Python 3
Karena built in pi dan e tidak memiliki angka yang cukup, saya memutuskan untuk menghitung sendiri.
Tautan IDEOne
Output untuk STDIN = 1000:
sumber
should be able to work for any N, given unlimited resources
aturan. Sebagian besar hasilnya nol di sekitar N = 10000.)NameError: name 'xrange' not defined
.Scala - 1790
IDEOne di http://ideone.com/A2CIto .
Kami menggunakan rumus Wetherfield untuk π (dan kode rumus Machin diangkut secara kasar dari sini ). Kami menghitung e menggunakan seri daya biasa.
sumber