Solusi untuk kesalahan pembulatan floating point

Dalam membangun aplikasi yang berhubungan dengan banyak perhitungan matematis, saya telah menemui masalah bahwa angka-angka tertentu menyebabkan kesalahan pembulatan.

Meskipun saya mengerti bahwa floating point tidak tepat , masalahnya adalah bagaimana cara saya menangani angka yang tepat untuk memastikan bahwa ketika perhitungan dilakukan pada mereka, floating point rounding tidak menyebabkan masalah?

Ada tiga pendekatan mendasar untuk membuat jenis numerik alternatif yang bebas dari pembulatan titik mengambang. Tema umum dengan ini adalah bahwa mereka menggunakan bilangan bulat matematika sebagai gantinya dalam berbagai cara.

Rasional

Mewakili angka sebagai bagian keseluruhan dan angka rasional dengan pembilang dan penyebut. Jumlahnya 15.589akan direpresentasikan sebagai w: 15; n: 589; d:1000.

Ketika ditambahkan ke 0,25 (yaitu w: 0; n: 1; d: 4), ini melibatkan menghitung LCM, dan kemudian menambahkan dua angka. Ini berfungsi baik untuk banyak situasi, meskipun dapat menghasilkan angka yang sangat besar ketika Anda bekerja dengan banyak angka rasional yang relatif prima satu sama lain.

Titik pasti

Anda memiliki seluruh bagian, dan bagian desimal. Semua angka dibulatkan (ada kata itu - tetapi Anda tahu di mana itu) dengan presisi itu. Misalnya, Anda bisa memiliki titik tetap dengan 3 titik desimal. 15.589+ 0.250menjadi menambahkan 589 + 250 % 1000untuk bagian desimal (dan kemudian semua carry ke seluruh bagian). Ini berfungsi sangat baik dengan database yang ada. Seperti disebutkan, ada pembulatan tetapi Anda tahu di mana itu dan dapat menentukannya sedemikian rupa sehingga lebih tepat daripada yang dibutuhkan (Anda hanya mengukur sampai 3 titik desimal, jadi buatlah tetap 4).

Mengambang titik tetap

Menyimpan nilai dan presisi. 15.589disimpan sebagai 15589untuk nilai dan 3untuk presisi, sementara 0.25disimpan sebagai 25dan 2. Ini dapat menangani presisi sewenang-wenang. Saya percaya inilah yang digunakan oleh internal BigDecimal Java (belum melihatnya baru-baru ini). Pada titik tertentu, Anda ingin mengeluarkannya dari format ini dan menampilkannya - dan itu mungkin melibatkan pembulatan (sekali lagi, Anda mengontrol di mana itu berada).

Setelah Anda menentukan pilihan untuk representasi, Anda bisa menemukan perpustakaan pihak ketiga yang ada yang menggunakan ini, atau menulis sendiri. Saat menulis sendiri, pastikan untuk mengujinya dan pastikan Anda melakukan perhitungan dengan benar.

Jika nilai floating point memiliki masalah pembulatan, dan Anda tidak ingin harus mengalami masalah pembulatan, secara logis mengikuti bahwa satu-satunya tindakan adalah tidak menggunakan nilai floating point.

Sekarang pertanyaannya menjadi, "bagaimana saya melakukan matematika yang melibatkan nilai-nilai non-integer tanpa variabel floating point?" Jawabannya adalah dengan tipe data presisi arbitrer . Perhitungannya lebih lambat karena harus diimplementasikan dalam perangkat lunak, bukan dalam perangkat keras, tetapi akurat. Anda tidak mengatakan bahasa apa yang Anda gunakan, jadi saya tidak bisa merekomendasikan paket, tetapi ada pustaka presisi sewenang-wenang yang tersedia untuk sebagian besar bahasa pemrograman populer.

Aritmatika titik apung biasanya cukup tepat (15 digit desimal untuk a double) dan cukup fleksibel. Masalah muncul ketika Anda melakukan matematika yang secara signifikan mengurangi jumlah digit ketepatan. Berikut ini beberapa contohnya:

• Pembatalan pada pengurangan:, 1234567890.12345 - 1234567890.12300hasilnya 0.0045hanya memiliki dua digit desimal presisi. Ini menyerang setiap kali Anda mengurangi dua angka yang sama besarnya.

• Menelan presisi: 1234567890.12345 + 0.123456789012345dievaluasi hingga 1234567890.24691, sepuluh digit terakhir dari operan kedua hilang.

• Perkalian: Jika Anda mengalikan dua angka 15 digit, hasilnya memiliki 30 digit yang perlu disimpan. Tetapi Anda tidak dapat menyimpannya, sehingga 15 bit terakhir hilang. Ini sangat menjengkelkan bila dikombinasikan dengan sqrt()(seperti pada sqrt(x*x + y*y): Hasilnya hanya akan memiliki 7,5 digit presisi.

Ini adalah perangkap utama yang perlu Anda waspadai. Dan begitu Anda menyadarinya, Anda dapat mencoba merumuskan matematika Anda dengan cara yang menghindari mereka. Sebagai contoh, jika Anda perlu menambah nilai berulang-ulang dalam satu lingkaran, jangan lakukan ini:

for(double f = f0; f < f1; f += df) {

Setelah beberapa iterasi, bagian yang lebih besar fakan menelan presisi df. Lebih buruk lagi, kesalahan akan bertambah, mengarah ke situasi kontraintuitif yang lebih kecil dfdapat menyebabkan hasil keseluruhan yang lebih buruk. Lebih baik tulis ini:

for(int i = 0; i < (f1 - f0)/df; i++) {
    double f = f0 + i*df;

Karena Anda menggabungkan kenaikan dalam satu perkalian tunggal, hasilnya fakan tepat hingga 15 digit desimal.

Ini hanya contoh, ada cara lain untuk menghindari kehilangan presisi karena alasan lain. Tetapi sudah banyak yang membantu untuk berpikir tentang besarnya nilai-nilai yang terlibat, dan untuk membayangkan apa yang akan terjadi jika Anda mengerjakan matematika Anda dengan pena dan kertas, membulatkan ke jumlah digit tetap setelah setiap langkah.

Cara memastikan bahwa Anda tidak memiliki masalah: Pelajari tentang masalah aritmatika floating-point, atau pekerjakan seseorang yang memiliki masalah, atau gunakan akal sehat.

Masalah pertama adalah presisi. Dalam banyak bahasa Anda memiliki "float" dan "double" (singkatan ganda untuk "double precision"), dan dalam banyak kasus "float" memberi Anda presisi sekitar 7 digit, sementara double memberi Anda 15. Akal sehat adalah bahwa jika Anda memiliki situasi di mana presisi mungkin menjadi masalah, 15 digit jauh lebih baik daripada 7 digit. Dalam banyak situasi yang sedikit bermasalah, menggunakan "ganda" berarti Anda berhasil, dan "melayang" berarti Anda tidak melakukannya. Katakanlah kapitalisasi pasar perusahaan adalah 700 miliar dolar. Hasilkan ini dalam float, dan bit terendah adalah $ 65536. Sebutkan menggunakan ganda, dan bit terendah adalah sekitar 0,012 sen. Jadi kecuali Anda benar-benar tahu apa yang Anda lakukan, Anda menggunakan double, bukan float.

Masalah kedua lebih merupakan masalah prinsip. Jika Anda melakukan dua perhitungan berbeda yang harus memberikan hasil yang sama, mereka sering tidak melakukannya karena kesalahan pembulatan. Dua hasil yang harus sama akan "hampir sama". Jika dua hasil berdekatan, maka nilai sebenarnya mungkin sama. Atau mungkin juga tidak. Anda harus mengingatnya dan harus menulis dan menggunakan fungsi yang mengatakan "x jelas lebih besar dari y" atau "x jelas lebih kecil dari y" atau "x dan y mungkin sama".

Masalah ini menjadi jauh lebih buruk jika Anda menggunakan pembulatan, misalnya "bulat x ke bilangan bulat terdekat". Jika Anda mengalikan 120 * 0,05, hasilnya harus 6, tetapi yang Anda dapatkan adalah "beberapa angka sangat dekat dengan 6". Jika Anda kemudian "membulatkan ke bilangan bulat terdekat", "angka yang sangat dekat dengan 6" mungkin "sedikit kurang dari 6" dan dibulatkan menjadi 5. Dan perhatikan bahwa tidak masalah seberapa presisi yang Anda miliki. Tidak masalah seberapa dekat dengan 6 hasil Anda, asalkan kurang dari 6.

Dan ketiga, beberapa masalah sulit . Itu berarti tidak ada aturan yang cepat dan mudah. Jika kompiler Anda mendukung "long double" dengan lebih presisi Anda dapat menggunakan "long double" dan melihat apakah ada bedanya. Jika tidak ada bedanya, berarti Anda baik-baik saja, atau Anda memiliki masalah yang sangat rumit. Jika itu membuat perbedaan yang Anda harapkan (seperti perubahan pada desimal ke-12) maka Anda cenderung baik-baik saja. Jika itu benar-benar mengubah hasil Anda, maka Anda memiliki masalah. Meminta bantuan.

Kebanyakan orang membuat kesalahan ketika mereka melihat dua kali lipat mereka menjerit BigDecimal, padahal sebenarnya mereka baru saja memindahkan masalah ke tempat lain. Dobel memberi Tanda bit: 1 bit, Lebar eksponen: 11 bit. Presisi signifikan dan signifikan: 53 bit (52 disimpan secara eksplisit). Karena sifat ganda, semakin besar interger Anda kehilangan akurasi relatif. Untuk menghitung akurasi relatif yang kami gunakan di sini adalah di bawah.

Keakuratan relatif ganda dalam perhitungan kami menggunakan foluma 2 ^ E <= abs (X) <2 ^ (E + 1)

epsilon = 2 ^ (E-10)% Untuk pelampung 16-bit (setengah presisi)

 Accuracy Power | Accuracy -/+| Maximum Power | Max Interger Value
 2^-1           | 0.5         | 2^51          | 2.2518E+15
 2^-5           | 0.03125     | 2^47          | 1.40737E+14
 2^-10          | 0.000976563 | 2^42          | 4.39805E+12
 2^-15          | 3.05176E-05 | 2^37          | 1.37439E+11
 2^-20          | 9.53674E-07 | 2^32          | 4294967296
 2^-25          | 2.98023E-08 | 2^27          | 134217728
 2^-30          | 9.31323E-10 | 2^22          | 4194304
 2^-35          | 2.91038E-11 | 2^17          | 131072
 2^-40          | 9.09495E-13 | 2^12          | 4096
 2^-45          | 2.84217E-14 | 2^7           | 128
 2^-50          | 8.88178E-16 | 2^2           | 4

Dengan kata lain Jika Anda menginginkan Akurasi +/- 0,5 (atau 2 ^ -1), ukuran maksimum angka tersebut adalah 2 ^ 52. Lebih besar dari ini dan jarak antara angka floating point lebih besar dari 0,5.

Jika Anda menginginkan keakuratan +/- 0,0005 (sekitar 2 ^ -11), ukuran maksimum angka tersebut adalah 2 ^ 42. Lebih besar dari ini dan jarak antara angka floating point lebih besar dari 0,0005.

Saya tidak bisa memberikan jawaban yang lebih baik dari ini. Pengguna akan perlu mencari tahu presisi apa yang mereka inginkan ketika melakukan perhitungan yang diperlukan dan nilai unit mereka (Meter, Kaki, Inci, mm, cm). Untuk sebagian besar kasus, float akan cukup untuk simulasi sederhana tergantung pada skala dunia yang ingin Anda tiru.

Meskipun itu sesuatu yang bisa dikatakan, jika Anda hanya ingin mensimulasikan dunia 100 meter kali 100 meter, Anda akan memiliki suatu tempat dalam urutan akurasi dekat 2 ^ -45. Ini bahkan tidak membahas bagaimana FPU modern di dalam cpu akan melakukan perhitungan di luar ukuran tipe asli dan hanya setelah perhitungan selesai mereka akan membulatkan (tergantung pada mode pembulatan FPU) ke ukuran tipe asli.