Relevansi titik tetap dan perhitungan presisi arbitrer

10

Saya melihat sangat sedikit perpustakaan / paket komputasi non-floating point. Mengingat berbagai ketidakakuratan representasi floating point, muncul pertanyaan mengapa tidak ada beberapa bidang di mana akurasi yang meningkat ini sebanding dengan seluk-beluk bekerja dengan fixed-point.

Apakah ada kesulitan besar dalam menggunakan, katakanlah, pemecah nilai eigen titik tetap? Seberapa lambat / cepat, tidak akurat / akuratnya mereka?

Terkait: ini dan ini

floating-point numerics Milind R
sumber
Milind R, terima kasih atas pertanyaan Anda. Saya pikir pertanyaan Anda menarik, tetapi mungkin tidak sesuai untuk situs ini. Saya mendorong Anda untuk melihat situs FAQ untuk panduan. Ketika saya melihat pertanyaan Anda, saya mendapat kesan bahwa itu adalah awal dari kata-kata kasar, meskipun saya pikir unsur-unsur dari pertanyaan yang sesuai dengan situs ada. Perlu bertanya apakah ada banyak aplikasi aritmatika integer dan aritmatika titik tetap dalam ilmu komputasi, dan meminta perbandingan aritmatika tersebut dengan floating point. Saya mendorong untuk mengedit posting Anda.
Geoff Oxberry
Ya itu lahir dari kata-kata kasar, tapi saya menyebutnya sebagai mencari pembenaran untuk status quo. Pertanyaan saya, seperti yang dapat Anda duga, adalah tentang mengapa kita tidak dapat memiliki perubahan besar menuju bilangan bulat dan matematika titik tetap dalam angka intensif. Bisakah Anda mengeditnya atas nama saya? Saya benar-benar mencoba, tetapi saya tidak tahu bagaimana pertanyaan saya tidak sesuai.
Milind R
5
Saya pikir ada jawaban teknis yang objektif untuk ini: jika Anda menjalankan hampir semua perhitungan ilmiah (katakanlah, penyelesaian linear), jumlah bit yang diperlukan untuk penyimpanan yang tepat tumbuh secara eksponensial dalam waktu. Dengan demikian, dukungan kuat untuk ketidaktelitian diperlukan untuk pekerjaan yang bermanfaat.
Geoffrey Irving
@MilindR: Komunitas geometri komputasi telah tertarik pada perhitungan bilangan real yang sangat berkinerja dan tepat pada saat yang sama. Saya kira semua masalah praktis yang relevan bagi Anda dapat diamati dalam bidang penelitian ini. Contoh yang bisa Anda cari adalah perpustakaan LEDA.
shuhalo
@ GeoffreyIrving Bagaimana dengan nol dalam matriks segitiga? Mereka tidak bisa disimpan sebagai sesuatu yang selain tidak tepat rawan kesalahan floating point?
Milind R

Jawaban:

5

Penggunaan aritmatika titik tetap dapat sesuai dalam kondisi tertentu. Umumnya untuk komputasi ilmiah (setidaknya dalam arti bahwa kebanyakan orang memikirkannya) itu tidak tepat karena kebutuhan untuk mengekspresikan rentang dinamis besar yang dihadapi. Anda menyebutkan masalah nilai eigen sebagai contoh, tetapi sangat sering dalam sains, orang tertarik pada nilai eigen terkecil dari sebuah matriks (katakanlah, dalam menghitung keadaan dasar sistem kuantum). Keakuratan nilai eigen kecil umumnya akan cukup memburuk relatif terhadap nilai eigen besar jika Anda menggunakan titik tetap. Jika matriks Anda berisi entri yang bervariasi berdasarkan rasio besar, nilai eigen kecil mungkin sama sekali tidak dapat diekspresikan dalam presisi kerja. Ini adalah masalah dengan representasi angka; argumen ini berlaku terlepas dari bagaimana Anda melakukan perhitungan perantara. Anda mungkin dapat menentukan skala untuk menerapkan hasil yang dihitung, tetapi sekarang Anda baru saja menemukan titik mengambang. Mudah untuk membuat matriks yang elemen-elemennya berperilaku baik, tetapi nilai eigennya berperilaku sangat buruk (sepertiMatriks Wilkinson , atau bahkan matriks dengan entri yang sepenuhnya bilangan bulat ). Contoh-contoh ini tidak se-patologis kelihatannya, dan banyak masalah di ujung tombak sains melibatkan matriks yang berperilaku sangat buruk, jadi menggunakan titik tetap dalam konteks ini adalah Ide Buruk (TM).

Anda mungkin berpendapat bahwa Anda mengetahui besarnya hasil dan Anda ingin tidak membuang bit pada eksponen, jadi mari kita bicara tentang perantara. Menggunakan titik tetap umumnya akan memperburuk efek pembatalan dan pembulatan katastropik kecuali Anda benar-benar berusaha keras untuk bekerja dalam presisi yang lebih tinggi. Penalti kinerja akan sangat besar, dan saya akan menduga bahwa menggunakan representasi floating point dengan lebar bit mantissa yang sama akan lebih cepat dan lebih akurat.

Satu area di mana titik tetap dapat bersinar adalah di area tertentu dari komputasi geometris. Terutama jika Anda membutuhkan aritmatika yang tepat atau mengetahui rentang dinamis semua angka sebelumnya, titik tetap memungkinkan Anda memanfaatkan semua bit dalam representasi Anda. Sebagai contoh, misalkan Anda ingin menghitung persimpangan dua garis, dan entah bagaimana titik akhir dari dua garis tersebut dinormalisasi untuk duduk di unit square. Dalam hal ini, titik persimpangan dapat direpresentasikan dengan lebih banyak bit presisi daripada menggunakan angka floating point yang setara (yang akan membuang bit pada eksponen). Sekarang, hampir dapat dipastikan bahwa bilangan antara yang diperlukan dalam perhitungan ini perlu dihitung dengan presisi yang lebih tinggi, atau setidaknya dilakukan dengan sangat hati-hati (seperti ketika membagi produk dari dua angka dengan angka lain, Anda harus sangat berhati-hati tentang hal itu ). Dalam hal ini, titik tetap lebih menguntungkan dari sudut pandang representasi daripada dari sudut pandang komputasi, dan saya akan melangkah lebih jauh dengan mengatakan ini secara umum benar ketika Anda dapat menetapkan batas atas dan bawah yang pasti pada rentang dinamis dari output algoritma Anda. . Ini jarang terjadi.

Dulu saya berpikir bahwa representasi floating point kasar atau tidak akurat (mengapa membuang bit pada eksponen ?!). Tetapi seiring berjalannya waktu saya menyadari bahwa ini adalah salah satu representasi terbaik untuk bilangan real. Hal-hal di alam muncul pada skala log, sehingga data nyata akhirnya mencakup sejumlah besar eksponen. Juga untuk mencapai akurasi relatif setinggi mungkin, diperlukan pengerjaan skala log, membuat pelacakan eksponen lebih alami. Satu-satunya pesaing lain untuk representasi "alami" adalah indeks tingkat simetris . Namun, penambahan dan pengurangan jauh lebih lambat dalam representasi itu, dan tidak memiliki dukungan perangkat keras dari IEEE 754. Sejumlah besar pemikiran dimasukkan ke dalam standar floating point., dengan pilar aljabar linear numerik. Saya pikir dia tahu apa representasi angka yang "benar".

Victor Liu
sumber
4

Sebagai contoh mengapa aritmatika / aritmatika titik pasti sangat jarang digunakan, pertimbangkan ini:

  • Dalam metode elemen hingga, seperti pada hampir setiap metode lain yang digunakan dalam komputasi ilmiah, kita sampai pada sistem linier atau nonlinier yang hanya merupakan perkiraan terhadap dunia nyata. Misalnya, dalam FEM, sistem linier untuk menyelesaikan hanya merupakan perkiraan terhadap persamaan diferensial parsial asli (yang mungkin, itu sendiri, hanya merupakan perkiraan dari dunia nyata). Jadi mengapa berusaha keras untuk menyelesaikan sesuatu yang hanya merupakan perkiraan?

  • Sebagian besar algoritma yang kami gunakan saat ini bersifat iteratif: metode Newton, Conjugate Gradients, dll. Kami mengakhiri iterasi ini setiap kali kami puas bahwa keakuratan iteratif yang mendekati solusi masalah sudah cukup. Dengan kata lain, kami mengakhiri sebelum kami memiliki solusi yang tepat. Seperti sebelumnya, mengapa menggunakan aritmatika yang tepat untuk skema iteratif ketika kita tahu bahwa kita hanya menghitung perkiraan?

Wolfgang Bangerth
sumber
Memang sulit untuk mengakuinya, tapi ya, jawaban Anda pada dasarnya menyalibkan penggunaan komputasi yang tepat dalam skala besar. Saya kira saya tidak akan melihat bagian belakang floatdalam waktu dekat.
Milind R
@ MilindR: Saya tidak yakin apa yang Anda tuju. Anda tampaknya memiliki palu dan frustrasi karena tidak ada yang memiliki paku atau berpikir bahwa palu adalah alat yang berguna. Tapi itu bukan karena kami tidak menyukai Anda - kami telah memikirkan masalah ini untuk waktu yang lama dan hanya memutuskan bahwa obeng yang kami miliki adalah alat yang tepat. Saya tidak menemukan frustrasi tentang hal itu (kecuali jika Anda memiliki palu) karena itu hanya pendekatan pragmatis - mengapa menggunakan aritmatika yang tepat ketika kita hanya melakukan perkiraan?
Wolfgang Bangerth
Ini membuat frustasi karena masalah yang normal bisa dikondisikan sangat buruk sehingga tidak bisa dipecahkan. Juga karena ideal presisi arbitrer tampak begitu menjanjikan, dibandingkan dengan sifat tidak tepat dari titik apung mulai dari menyimpan nilai hingga menghasilkannya.
Milind R
Masalahnya adalah bahwa kesalahan pembulatan sangat sulit untuk dianalisis. Saya menyadari ini pada hari saya mulai belajar analisis numerik dan aljabar linear numerik. Jadi sebuah sistem yang sepenuhnya menghindari masalah, menjadikan pengkondisian sebagai non-isu, harusnya membawa dunia dengan badai, bukan? adalah pemikirannya. Tentu saja saya memahami batasannya, tetapi mereka lebih seperti iritasi, daripada pelanggar transaksi. Jenis seperti meningkatnya kesulitan dalam menurunkan transistor dalam prosesor. Ya itu sulit untuk dianalisis, tetapi Intel masih melakukannya.
Milind R
1
Jika suatu masalah begitu buruk sehingga sulit untuk dipecahkan, maka solusinya tidak stabil untuk gangguan. Itu masalah dengan masalah aslinya, bukan representasi floating point. Ya, mungkin Anda bisa mendapatkan solusi untuk masalah menggunakan representasi yang tepat. Tetapi solusinya tidak stabil dan kemungkinan besar tidak akan ada hubungannya dengan apa yang sebenarnya Anda cari. Anda menggonggong pohon yang salah jika Anda berpikir bahwa representasi angka adalah masalahnya.
Wolfgang Bangerth
3

Jika Anda melihat perpustakaan ini untuk pembulatan yang benar: CRlibm , Anda akan melihat dalam dokumentasi bahwa secara umum, algoritma harus terbukti akurat (dengan bukti beralasan). Mengapa? Stabilitas dan kecepatan konvergensi hasil suatu fungsi tidak memiliki jawaban "satu ukuran untuk semua". Singkatnya, ada "tidak ada makan siang gratis" - Anda harus bekerja untuk membuktikan bahwa alasan Anda benar. Ini disebabkan oleh perilaku fungsi yang dimodelkan, bukan perangkat keras yang mendasari (apakah Anda menggunakan unit integer atau floating point, meskipun ya, keduanya memiliki "gotcha", seperti overflow / underflow, angka denormal, dll.) Bahkan jika hasilnya Anda mencari konvergen ke integer, algoritma yang digunakan untuk menemukan hasilnya belum tentu sangat stabil.

Eigen adalah pustaka C ++ yang memiliki berbagai algoritma untuk menyelesaikan matriks, masing-masing dengan sifat yang berbeda. Halaman ini berisi tabel yang membahas trade-offs kecepatan vs akurasi untuk berbagai algoritma yang digunakan untuk memecahkan matriks. Saya menduga perpustakaan Eigen dapat melakukan apa yang Anda inginkan. :-)

mda
sumber
Terima kasih .. Link sangat informatif, dan bagus. Tetapi bukankah penggunaan titik tetap bersama dengan batasan terbatas menghasilkan hasil yang lebih akurat? Karena representasi itu sendiri tepat untuk memulai, tidak seperti floating point?
Milind R
1
Saya sarankan Anda menyerang masalah Anda dari sudut pandang lain. Dalam pengantar logika, Anda belajar bahwa ada tiga bagian untuk solusi masalah: definisi, alasan, dan kesimpulan / hasil. Anda mungkin (karena kebanyakan dari kita) sangat terbiasa bekerja sebagian besar pada langkah "definisi" pemecahan masalah - biasanya Anda dapat "mendefinisikan" masalah Anda; Namun, jika Anda menjadi frustrasi, kadang-kadang Anda menemui jenis masalah yang lebih sulit yang membutuhkan lebih banyak pekerjaan di bagian "penalaran".
mda
Saya hanya samar-samar mengerti Anda ... Saya tidak bisa melihat di mana saya bisa "mendefinisikan" masalah ini, alasannya sangat penting.
Milind R
Beberapa tahun kemudian, saya benar-benar mengerti Anda :-)
Milind R
2

Untuk beberapa contoh bagus di mana aritmatika presisi tinggi berguna dalam matematika, lihat buku Mathematics by Experiment oleh Jonathan Borwein dan David Bailey. Ada juga sekuel ini , yang belum saya baca.

David Ketcheson
sumber