Diberikan bilangan bulat positif n keluaran jumlah digit n desimal pertama bagian pecahan π n .
Contoh input dan output:
1 → 1
2 → 14
3 → 6
4 → 13
5 → 24
50 → 211
500 → 2305
5000 → 22852
Fungsi internal menghitung digit π atau mengevaluasi seri daya atau fraksi lanjutan tidak diperbolehkan. Celah standar berlaku. Input / output dapat dalam format yang nyaman (stdin, stdout, fungsi in / output, dll).
Kode terpendek dalam byte menang.
code-golf
math
arithmetic
pi
orlp
sumber
sumber
Jawaban:
Python - 191 Bytes
~ 4x versi lebih cepat - 206 byte
Input diambil dari stdin. Output untuk n = 5000 membutuhkan sekitar 14 detik dengan skrip kedua (atau 60 detik dengan yang pertama).
Penggunaan sampel:
Rumus yang digunakan adalah sebagai berikut:
di mana A n adalah n th Alternating Nomor , yang dapat secara formal didefinisikan sebagai jumlah permutasi bolak pada satu set ukuran n (lihat juga: A000111 ). Atau, urutannya dapat didefinisikan sebagai komposisi Bilangan Tangen dan Bilangan Garis Potong ( A 2n = S n , A 2n + 1 = T n ), lebih lanjut tentang itu nanti.
Kecil faktor koreksi c n cepat konvergen ke 1 sebagai n menjadi besar, dan diberikan oleh:
Untuk n = 1 , ini sama dengan mengevaluasi Leibniz Series . Mendekati π sebagai 10 ½ , jumlah istilah yang diperlukan dapat dihitung sebagai:
yang konvergen (dibulatkan ke 17) , meskipun nilai yang lebih kecil dari n membutuhkan lebih banyak.
Untuk perhitungan A n ada beberapa algoritma, dan bahkan rumus eksplisit, tetapi semuanya adalah kuadrat oleh n . Saya awalnya mengkodekan implementasi Algoritma Seidel , tetapi ternyata terlalu lambat untuk praktis. Setiap iterasi membutuhkan jangka tambahan untuk disimpan, dan istilah meningkatkan besarnya sangat cepat (yang "salah" jenis O (n 2 ) ).
Script pertama menggunakan implementasi algoritma yang awalnya diberikan oleh Knuth dan Buckholtz :
Meskipun tidak secara eksplisit dinyatakan, algoritme ini menghitung Bilangan Tangen dan Bilangan Secant secara bersamaan. Script kedua menggunakan variasi dari algoritma ini oleh Brent dan Zimmermann , yang menghitung T atau S , tergantung pada paritas n . Peningkatan kuadrat oleh n / 2 , maka peningkatan kecepatan ~ 4x.
sumber
Python 2, 246 byte
Saya telah mengambil pendekatan yang serupa dengan jawaban saya di Calculate π dengan konvergensi kuadratik . Baris terakhir mengambil kekuatan N pi dan menjumlahkan digit. Tes N = 5000 membutuhkan satu menit atau lebih.
Beberapa tes:
Kode yang tidak dipisahkan:
sumber
a=j
danp=j
kea=p=j
iirc. Mungkin.Pyth, 33
Berdasarkan jawaban ini oleh isaacg . Mungkin bisa bermain golf lebih banyak. Lambat.
sumber