Komputasi digit angka terpotong dari kekuatan pi

12

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.

orlp
sumber
Apakah fungsi trigonometri lain yang dapat digunakan untuk menghitung pi, tetapi tidak harus secara langsung, seperti arctangent atau imajiner logaritma juga dilarang? Juga, apakah ada batas atas n yang bisa gagal setelahnya?
FryAmTheEggman
@FryAmTheEggman Jika fungsi trigonometri tersebut dapat menghitung digit pi yang sewenang-wenang, maka ya itu dilarang. Program Anda harus bekerja secara teori untuk n apa pun , tetapi dimaafkan jika runtime atau memori menjadi terlalu tinggi.
orlp

Jawaban:

4

Python - 191 Bytes

t=i=1L;k=n=input();f=2000*20**n;A=range(n+1)
for k in range(2,n):A=[(A[j-1]+A[j+1])*j>>1for j in range(n-k+1)];f*=k
while k:k=(1-~i*n%4)*f/A[1]/i**n;t+=k;i+=2
print sum(map(int,`t`[-n-4:-4]))

~ 4x versi lebih cepat - 206 byte

t=i=1L;k=n=input();f=2000*20**n;A=[0,1]+[0]*n
for k in range(1,n):
 f*=k
 for j in range(-~n/2-k+1):A[j]=j*A[j-1]+A[j+1]*(j+2-n%2)
while k:k=(1-~i*n%4)*f/A[1]/i**n;t+=k;i+=2
print sum(map(int,`t`[-n-4:-4]))

Input diambil dari stdin. Output untuk n = 5000 membutuhkan sekitar 14 detik dengan skrip kedua (atau 60 detik dengan yang pertama).


Penggunaan sampel:

$ echo 1 | python pi-trunc.py
1

$ echo 2 | python pi-trunc.py
14

$ echo 3 | python pi-trunc.py
6

$ echo 4 | python pi-trunc.py
13

$ echo 5 | python pi-trunc.py
24

$ echo 50 | python pi-trunc.py
211

$ echo 500 | python pi-trunc.py
2305

$ echo 5000 | python pi-trunc.py
22852

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 :

Misalkan T 1, k = 1 untuk semua k = 1..n

Nilai T selanjutnya diberikan oleh relasi rekurensi:

T n + 1, k = 1/2 [ (k - 1) T n, k-1 + (k + 1) T n, k + 1 ]

A n kemudian diberikan oleh T n, 1

(lihat juga: A185414 )

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.

primo
sumber
1
Penjelasan hebat dari matematika di balik jawaban Anda.
Logic Knight
3

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.

from decimal import*
d=Decimal
N=input()
getcontext().prec=2*N
j=d(1)
h=d(2)
f=h*h
g=j/h
a=j
b=j/h.sqrt()
t=j/f
p=j
for i in bin(N)[2:]:e=a;a,b=(a+b)/h,(a*b).sqrt();c=e-a;t-=c*c*p;p+=p
k=a+b
l=k*k/f/t
print sum(map(int,`l**N`.split('.')[1][:N]))

Beberapa tes:

$ echo 1 | python soln.py
1
$ echo 3 | python soln.py
6
$ echo 5 | python soln.py
24
$ echo 500 | python soln.py
2305
$ echo 5000 | python soln.py
22852

Kode yang tidak dipisahkan:

from decimal import *
d = Decimal

N = input()
getcontext().prec = 2 * N

# constants:
one = d(1)
two = d(2)
four = two*two
half = one/two

# initialise:
a = one
b = one / two.sqrt()
t = one / four
p = one

for i in bin(N)[2:] :
    temp = a;
    a, b = (a+b)/two, (a*b).sqrt();
    pterm = temp-a;
    t -= pterm*pterm * p;
    p += p

ab = a+b
pi = ab*ab / four / t
print sum(map(int, `pi ** N`.split('.')[1][:N]))
Ksatria Logika
sumber
Baris 8, Anda dapat mengubah a=jdan p=jke a=p=jiirc. Mungkin.
Elias Benevedes
Terima kasih. Ada lebih banyak optimisasi golf untuk kode ini, tetapi tidak akan kompetitif tanpa penulisan ulang menggunakan algoritma tanpa Desimal.
Logic Knight
1

Pyth, 33

s<>j^u+/*GHhyHy^TyQr*TQ0ZQT_y*QQQ

Berdasarkan jawaban ini oleh isaacg . Mungkin bisa bermain golf lebih banyak. Lambat.

s<>j            Digit sum of...
  ^                 
    u               Evaluate pi = 2 + 1/3*(2 + 2/5*(2 + 3/7*(2 + 4/9*(2 + ...))))
      +
        /
          *GH
          hyH
        y^TyQ       Except we generate a large integer containing 2n digits,
                    rather than a fraction.
      r*TQ0         Experimentally verified that 10*n iterations will give enough
                    precision for 2n digits (# digits correct grows faster than 2n).
      Z
    Q               To the nth power.
  T_y*QQQ         Get the last 2n^2 digits (all the fractional digits) and get the
                  first n fractional digits.
orlp
sumber
1
Jawaban ini benar-benar membutuhkan setidaknya penjelasan yang cukup untuk membenarkan bahwa ia menghitung angka yang cukup untuk mendapatkan jawaban yang benar.
Peter Taylor
@ PeterTaylor saya akan menambahkan penjelasan besok, baru saja akan pergi tidur.
orlp
Setiap iterasi menghasilkan satu bit yang benar (lihat Lampiran A ). 2n digit harus membutuhkan ~ 6.64n iterasi.
primo