Bagaimana cara saya menentukan apakah perhitungan pi saya akurat?

Saya mencoba berbagai metode untuk mengimplementasikan program yang memberikan angka pi secara berurutan. Saya mencoba metode seri Taylor , tetapi terbukti konvergen sangat lambat (ketika saya membandingkan hasil saya dengan nilai online setelah beberapa waktu). Lagi pula, saya mencoba algoritma yang lebih baik.

Jadi, ketika menulis program saya terjebak pada masalah, seperti semua algoritma: Bagaimana saya tahu bahwa nangka yang saya hitung akurat?

Karena saya pemegang rekor dunia saat ini untuk digit pi terbanyak, saya akan menambahkan dua sen saya :

Kecuali jika Anda benar-benar membuat rekor dunia baru, praktik yang umum adalah hanya memverifikasi angka yang dihitung terhadap nilai yang diketahui. Jadi itu cukup sederhana.

Bahkan, saya memiliki halaman web yang mencantumkan snippet of digit untuk tujuan memverifikasi perhitungan terhadap mereka: http://www.numberworld.org/digits/Pi/

Tetapi ketika Anda masuk ke wilayah rekor dunia, tidak ada yang bisa dibandingkan.

Secara historis, pendekatan standar untuk memverifikasi bahwa digit yang dihitung benar adalah untuk menghitung ulang digit menggunakan algoritma kedua. Jadi, jika salah satu perhitungan memburuk, angka pada akhirnya tidak akan cocok.

Ini biasanya lebih dari dua kali lipat jumlah waktu yang dibutuhkan (karena algoritma kedua biasanya lebih lambat). Tapi itu satu-satunya cara untuk memverifikasi angka yang dihitung setelah Anda berkeliaran di wilayah yang belum dipetakan dengan angka yang belum pernah dihitung sebelumnya dan rekor dunia baru.

Kembali pada hari-hari di mana superkomputer mengatur catatan, dua algoritma AGM yang umum digunakan:

• Algoritma Gauss – Legendre
• Algoritma Borneo

Ini adalah kedua O(N log(N)^2)algoritma yang cukup mudah diimplementasikan.

Namun, saat ini, segalanya agak berbeda. Dalam tiga rekor dunia terakhir, alih-alih melakukan dua perhitungan, kami hanya melakukan satu perhitungan menggunakan rumus yang paling cepat dikenal ( Formula Chudnovsky ):

Algoritma ini jauh lebih sulit untuk diterapkan, tetapi jauh lebih cepat daripada algoritma AGM.

Kemudian kami memverifikasi angka biner menggunakan rumus BBP untuk ekstraksi digit .

Rumus ini memungkinkan Anda untuk menghitung angka biner acak tanpa menghitung semua angka sebelumnya. Jadi ini digunakan untuk memverifikasi beberapa digit biner terkomputasi. Oleh karena itu jauh lebih cepat daripada perhitungan penuh.

Keuntungan dari ini adalah:

1. Hanya satu perhitungan mahal yang dibutuhkan.

Kerugiannya adalah:

1. Implementasi dari Diperlukan formula Bailey – Borwein-Plouffe (BBP).
2. Langkah tambahan diperlukan untuk memverifikasi konversi radix dari biner ke desimal.

_{Saya telah membahas beberapa detail mengapa memverifikasi beberapa digit terakhir menyiratkan bahwa semua digit itu benar. Tetapi mudah untuk melihat ini karena kesalahan perhitungan akan merambat ke digit terakhir.}

Sekarang langkah terakhir ini (memverifikasi konversi) sebenarnya cukup penting. Salah satu pemegang rekor dunia sebelumnya benar-benar memanggil kami karena ini, pada awalnya, saya tidak memberikan deskripsi yang cukup tentang cara kerjanya.

Jadi saya telah mengambil cuplikan ini dari blog saya:

N = # of decimal digits desired
p = 64-bit prime number

Hitung A menggunakan basis 10 aritmatika dan B menggunakan aritmatika biner.

Jika A = B, maka dengan "probabilitas sangat tinggi", konversi sudah benar.

Untuk bacaan lebih lanjut, lihat posting blog saya Pi - 5 Triliun Digit .

Tidak diragukan lagi, untuk keperluan Anda (yang saya asumsikan hanyalah latihan pemrograman), hal terbaik adalah memeriksa hasil Anda terhadap daftar digit pi di web.

Dan bagaimana kita tahu bahwa nilai-nilai itu benar? Yah, saya bisa mengatakan bahwa ada cara-ilmu komputer-y cara untuk membuktikan bahwa implementasi suatu algoritma adalah benar.

Lebih pragmatis, jika orang yang berbeda menggunakan algoritma yang berbeda, dan mereka semua setuju untuk (memilih angka) seribu (juta, apa pun) tempat desimal, yang akan memberi Anda perasaan hangat kabur bahwa mereka melakukannya dengan benar.

Secara historis, William Shanks menerbitkan pi ke 707 tempat desimal pada tahun 1873. Pria yang malang, dia membuat kesalahan mulai dari tempat desimal ke-528.

Sangat menarik, pada 1995 sebuah algoritma diterbitkan yang memiliki properti yang akan secara langsung menghitung digit ke-n (basis 16) pi tanpa harus menghitung semua digit sebelumnya !

Akhirnya, saya harap algoritma awal Anda bukan pi/4 = 1 - 1/3 + 1/5 - 1/7 + ...Itu mungkin yang paling sederhana untuk diprogram, tetapi juga salah satu cara paling lambat untuk melakukannya. Lihatlah artikel pi di Wikipedia untuk pendekatan yang lebih cepat.

Anda bisa menggunakan banyak pendekatan dan melihat apakah mereka bertemu dengan jawaban yang sama. Atau ambil sebagian dari jaring. Algoritma Chudnovsky biasanya digunakan sebagai metode penghitungan pi yang sangat cepat. http://www.craig-wood.com/nick/articles/pi-chudnovsky/

Seri Taylor adalah salah satu cara untuk memperkirakan pi. Seperti dicatat itu konvergen perlahan.

Jumlah parsial dari seri Taylor dapat ditunjukkan berada dalam beberapa pengganda dari istilah berikutnya yang jauh dari nilai sebenarnya dari pi.

Cara lain mendekati pi memiliki cara yang sama untuk menghitung kesalahan maks.

Kami tahu ini karena kami bisa membuktikannya secara matematis.

Anda dapat mencoba komputasi sin(pi/2)(atau cos(pi/2)dalam hal ini) menggunakan seri daya (cukup) konvergen cepat untuk dosa dan cos. (Bahkan lebih baik: gunakan berbagai rumus penggandaan untuk menghitung lebih dekat x=0untuk konvergensi yang lebih cepat.)

BTW, lebih baik daripada menggunakan seri untuk tan(x)is, dengan komputasi katakanlah cos(x)sebagai kotak hitam (misalnya Anda bisa menggunakan seri taylor seperti di atas) adalah melakukan pencarian root melalui Newton. Tentu saja ada algoritma yang lebih baik di luar sana, tetapi jika Anda tidak ingin memverifikasi berton-ton ini sudah cukup (dan itu tidak terlalu sulit untuk diterapkan, dan Anda hanya perlu sedikit kalkulus untuk memahami mengapa ia bekerja.)