Apa yang menyebabkan kesalahan pembulatan floating point?

Saya menyadari bahwa aritmatika floating point memiliki masalah presisi. Saya biasanya mengatasinya dengan beralih ke representasi angka desimal tetap, atau hanya dengan mengabaikan kesalahan.

Namun, saya tidak tahu apa penyebab ketidaktepatan ini. Mengapa ada begitu banyak masalah pembulatan dengan angka float?

Ini karena beberapa fraksi membutuhkan jumlah tempat yang sangat besar (atau bahkan tak terbatas) untuk diekspresikan tanpa pembulatan. Ini berlaku untuk notasi desimal sebanyak untuk biner atau lainnya. Jika Anda membatasi jumlah tempat desimal yang akan digunakan untuk perhitungan Anda (dan menghindari membuat perhitungan dalam notasi pecahan), Anda harus membulatkan bahkan ekspresi sederhana seperti 1/3 + 1/3. Alih-alih menulis 2/3 sebagai hasilnya Anda harus menulis 0,33333 + 0,33333 = 0,66666 yang tidak identik dengan 2/3.

Dalam hal komputer jumlah digit dibatasi oleh sifat teknis dari register memori dan CPU-nya. Notasi biner yang digunakan secara internal menambah beberapa kesulitan. Komputer biasanya tidak dapat mengekspresikan angka dalam notasi pecahan, meskipun beberapa bahasa pemrograman menambahkan kemampuan ini, yang memungkinkan masalah-masalah tersebut dihindari pada tingkat tertentu.

Apa Yang Harus Diketahui Setiap Ilmuwan Komputer Tentang Aritmatika Titik Apung

Terutama, kesalahan pembulatan berasal dari fakta bahwa tak terhingga dari semua bilangan real tidak mungkin diwakili oleh memori terbatas komputer , apalagi sepotong kecil memori seperti variabel floating point tunggal , begitu banyak angka yang disimpan hanyalah perkiraan dari jumlah yang harus mereka wakili.

Karena hanya ada sejumlah nilai yang bukan perkiraan, dan operasi apa pun antara perkiraan dan angka lainnya menghasilkan perkiraan, kesalahan pembulatan hampir tidak bisa dihindari .

Yang penting adalah untuk menyadari ketika mereka cenderung menyebabkan masalah dan mengambil langkah-langkah untuk mengurangi risiko .

Selain David Goldberg , Apa Yang Harus Diketahui Setiap Ilmuwan Komputer Tentang Aritmatika Titik Apung (diterbitkan ulang oleh Sun / Oracle sebagai lampiran dari Panduan Perhitungan Numerik mereka ), yang disebutkan oleh thorsten , jurnal ACCU yang kelebihan beban sangat bagus serangkaian artikel oleh Richard Harris tentang Floating Point Blues .

Seri dimulai dengan

• Anda Akan Harus Berpikir! dalamKelebihan # 99( pdf , p5-10):

Komputasi numerik memiliki banyak jebakan. Richard Harris mulai mencari peluru perak.

Naga kesalahan numerik tidak sering terbangun dari tidurnya, tetapi jika didekati secara tidak hati-hati, ia akan kadang-kadang menimbulkan kerusakan yang sangat besar pada perhitungan programmer yang tidak waspada.

Sedemikian rupa sehingga beberapa programmer, setelah kebetulan di hutan aritmetika titik apung IEEE 754, menyarankan rekan-rekan mereka untuk tidak bepergian di tanah yang adil itu.

Dalam seri artikel ini kita akan menjelajahi dunia komputasi numerik, kontras aritmatika floating point dengan beberapa teknik yang telah diusulkan sebagai pengganti yang lebih aman untuk itu. Kita akan belajar bahwa wilayah naga memang sangat jauh dan bahwa secara umum kita harus melangkah dengan hati-hati jika kita takut perhatiannya yang menghancurkan.

Richard mulai dengan menjelaskan taksonomi bilangan real, rasional, irasional, aljabar, dan transendental. Dia kemudian menjelaskan representasi IEEE754, sebelum melanjutkan ke kesalahan pembatalan dan urutan masalah eksekusi.

Jika Anda membaca tidak lebih dalam dari ini, Anda akan memiliki landasan yang sangat baik dalam masalah yang terkait dengan angka floating point.

Namun jika Anda ingin tahu lebih banyak, ia melanjutkan

• Mengapa Fixed Point Tidak Akan Menyembuhkan Blues Floating Point Anda dalamKelebihan # 100( pdf , p15-22)
• Mengapa Rasional Tidak Akan Menyembuhkan Blues Floating Point Anda diOverload # 101( pdf , p9-13)
• Mengapa Aljabar Komputer Tidak Akan Menyembuhkan Blues Floating Point Anda diOverload # 102( pdf , p9-14).
• Mengapa Aritmatika Interval Tidak Akan Menyembuhkan Blues Floating Point Anda diOverload 103( pdf , p19-24)

Dia kemudian beralih untuk mencoba membantu Anda menyembuhkan Blues Kalkulus Anda

• Mengapa [Masukkan Algoritma Di Sini] Tidak Akan Menyembuhkan Blues Kalkulus Anda diOverload 104( pdf , p22-24).
• Mengapa Perbedaan Hingga Tidak akan Menyembuhkan Blues Kalkulus Anda diOverload 105( pdf , p5-12).
• Mengapa Perkiraan Polinomial Tidak Akan Menyembuhkan Blues Kalkulus Anda diOverload 106( pdf , p16-25).
• Mengapa Aljabar Komputer Tidak akan Menyembuhkan Blues Kalkulus Anda diOverload 107( pdf , p15-20).

dan terakhir namun tidak kalah pentingnya, ada

• Mengapa Diferensiasi Otomatis Tidak Akan Menyembuhkan Blues Kalkulus Anda diOverload 108( pdf , p4-11).

Seluruh seri artikel layak untuk dilihat, dan total 66 halaman, mereka masih lebih kecil dari 77 halaman dari makalah Goldberg .

Sementara seri ini mencakup banyak hal yang sama, saya menemukan itu lebih mudah diakses daripada kertas Goldberg . Saya juga merasa lebih mudah untuk memahami bagian-bagian yang lebih kompleks dari kertas setelah membaca artikel Richards sebelumnya dan setelah artikel-artikel awal, Richard bercabang ke banyak bidang menarik yang tidak disentuh oleh kertas Goldberg.

Seperti yang dikatakan oleh ak dalam komentar:

Sebagai penulis artikel-artikel itu saya ingin menyebutkan bahwa saya telah membuat versi interaktifnya di blog saya www.thusspakeak.com dimulai dengan thusspakeak.com/ak/2013/06 .

Nah, thorsten memiliki tautan pasti . Saya akan menambahkan:

Setiap bentuk representasi akan memiliki beberapa kesalahan pembulatan untuk beberapa nomor. Cobalah untuk mengekspresikan 1/3 dalam floating point IEEE, atau dalam desimal. Tidak ada yang bisa melakukannya dengan akurat. Ini melampaui menjawab pertanyaan Anda, tetapi saya telah menggunakan aturan praktis ini dengan sukses:

• Menyimpan nilai yang dimasukkan pengguna dalam desimal (karena mereka hampir pasti memasukkannya dalam representasi desimal - sangat sedikit pengguna akan menggunakan biner atau hex). Dengan begitu Anda selalu memiliki representasi yang dimasukkan oleh pengguna.
• Jika Anda harus menyimpan fraksi yang dimasukkan pengguna, simpan pembilang dan penyebut (juga dalam desimal)
• Jika Anda memiliki sistem dengan banyak unit ukuran untuk jumlah yang sama (seperti Celsius / Fahrenheit), dan pengguna dapat memasukkan keduanya, simpan nilai yang mereka masukkan dan unit tempat mereka memasukkannya. Jangan mencoba mengonversi dan menyimpan sebagai satu representasi, kecuali Anda dapat melakukannya tanpa kehilangan presisi / akurasi. Gunakan nilai yang tersimpan dan unit dalam semua perhitungan.
• Menyimpan nilai yang dihasilkan mesin dalam titik mengambang IEEE (ini dapat berupa angka yang dihasilkan oleh perangkat pengukuran elektronik, seperti sensor analog dengan konverter A / D, atau hasil perhitungan yang tidak dilingkari). Perhatikan bahwa ini tidak berlaku jika Anda membaca sensor melalui koneksi serial dan itu sudah memberi Anda nilai dalam format desimal (mis. 18,2 C).
• Simpan total yang dapat dilihat pengguna, dll., Dalam desimal (seperti saldo rekening bank). Bulatkan dengan tepat, tetapi gunakan nilai itu sebagai nilai definitif untuk semua perhitungan di masa depan.

Apa yang tampaknya belum disebutkan sejauh ini adalah konsep dari algoritma yang tidak stabil dan masalah yang dikondisikan . Saya akan membahas yang pertama, karena tampaknya menjadi perangkap yang lebih sering untuk numeric pemula.

Pertimbangkan perhitungan kekuatan rasio emas (timbal balik) φ=0.61803…; salah satu cara yang mungkin dilakukan adalah dengan menggunakan rumus rekursi φ^n=φ^(n-2)-φ^(n-1), dimulai dengan φ^0=1dan φ^1=φ. Jika Anda menjalankan rekursi ini di lingkungan komputasi favorit Anda dan membandingkan hasilnya dengan kekuatan yang dievaluasi secara akurat, Anda akan menemukan erosi lambat dari angka-angka penting. Inilah yang terjadi misalnya di Mathematica :

ph = N[1/GoldenRatio];  
Nest[Append[#1, #1[[-2]] - #1[[-1]]] & , {1, ph}, 50] - ph^Range[0, 51]  
{0., 0., 1.1102230246251565*^-16, -5.551115123125783*^-17, 2.220446049250313*^-16, 
-2.3592239273284576*^-16, 4.85722573273506*^-16, -7.147060721024445*^-16, 
1.2073675392798577*^-15, -1.916869440954372*^-15, 3.1259717037102064*^-15, 
-5.0411064211886014*^-15, 8.16837916750579*^-15, -1.3209051907825398*^-14, 
2.1377864756200182*^-14, -3.458669982359108*^-14, 5.596472721011714*^-14, 
-9.055131861349097*^-14, 1.465160458236081*^-13, -2.370673237795176*^-13, 
3.835834102607072*^-13, -6.206507137114341*^-13, 1.004234127360273*^-12, 
-1.6248848342954435*^-12, 2.6291189633497825*^-12, -4.254003796798193*^-12, 
6.883122762265558*^-12, -1.1137126558640235*^-11, 1.8020249321541067*^-11, 
-2.9157375879969544*^-11, 4.717762520172237*^-11, -7.633500108148015*^-11, 
1.23512626283229*^-10, -1.9984762736468268*^-10, 3.233602536479646*^-10, 
-5.232078810126407*^-10, 8.465681346606119*^-10, -1.3697760156732426*^-9, 
2.216344150333856*^-9, -3.5861201660070964*^-9, 5.802464316340953*^-9, 
-9.388584482348049*^-9, 1.5191048798689004*^-8, -2.457963328103705*^-8, 
3.9770682079726053*^-8, -6.43503153607631*^-8, 1.0412099744048916*^-7, 
-1.6847131280125227*^-7, 2.725923102417414*^-7, -4.4106362304299367*^-7, 
7.136559332847351*^-7, -1.1547195563277288*^-6}

Hasil yang diklaim φ^41memiliki tanda yang salah, dan bahkan lebih awal, nilai yang dihitung dan aktual untuk φ^39saham tidak memiliki digit yang sama ( 3.484899258054952* ^ - 9 for the computed version against the true value7.071019424062048 *^-9). Algoritma demikian tidak stabil, dan orang tidak boleh menggunakan rumus rekursi ini dalam aritmatika yang tidak tepat. Hal ini disebabkan oleh sifat inheren formula rekursi: ada solusi "peluruhan" dan "tumbuh" untuk rekursi ini, dan mencoba menghitung solusi "peluruhan" dengan solusi maju ketika ada alternatif "tumbuh" solusi yang meminta. untuk kesedihan numerik. Dengan demikian seseorang harus memastikan bahwa algoritma numeriknya stabil.

Sekarang, ke konsep masalah yang tidak terkondisikan : meskipun mungkin ada cara yang stabil untuk melakukan sesuatu secara numerik, mungkin saja masalah yang Anda miliki tidak dapat diselesaikan dengan algoritma Anda. Ini adalah kesalahan dari masalah itu sendiri, dan bukan metode solusinya. Contoh kanonik dalam angka adalah solusi persamaan linear yang melibatkan apa yang disebut "matriks Hilbert":

Matriks adalah contoh kanonik dari matriks yang tidak terkondisikan : mencoba memecahkan suatu sistem dengan matriks Hilbert yang besar mungkin menghasilkan solusi yang tidak akurat.

Berikut ini adalah demonstrasi Mathematica : bandingkan hasil aritmatika yang tepat

Table[LinearSolve[HilbertMatrix[n], HilbertMatrix[n].ConstantArray[1, n]], {n, 2, 12}]
{{1, 1}, {1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 
  1}, {1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1,
   1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 
  1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}}

dan aritmatika yang tidak tepat

Table[LinearSolve[N[HilbertMatrix[n]], N[HilbertMatrix[n].ConstantArray[1, n]]], {n, 2, 12}]
{{1., 1.}, {1., 1., 1.}, {1., 1., 1., 1.}, {1., 1., 1., 1., 1.},  
  {1., 1., 1., 1., 1., 1.}, {1., 1., 1., 1., 1., 1., 1.}, 
  {1., 1., 1., 1., 1., 1., 1., 1.}, {1., 1., 1., 1., 1., 1., 1., 1., 1.},  
  {1., 1., 1., 0.99997, 1.00014, 0.999618, 1.00062, 0.9994, 1.00031, 
  0.999931}, {1., 1., 0.999995, 1.00006, 0.999658, 1.00122, 0.997327, 
  1.00367, 0.996932, 1.00143, 0.999717}, {1., 1., 0.999986, 1.00022, 
  0.998241, 1.00831, 0.975462, 1.0466, 0.94311, 1.04312, 0.981529, 
  1.00342}}

(Jika Anda mencobanya di Mathematica , Anda akan mencatat beberapa pesan kesalahan yang mengingatkan akan kondisi buruk yang muncul.)

Dalam kedua kasus, hanya meningkatkan presisi bukanlah obat; itu hanya akan menunda erosi angka yang tak terelakkan.

Inilah yang mungkin Anda hadapi. Solusinya mungkin sulit: untuk yang pertama, Anda kembali ke papan gambar, atau membaca jurnal / buku / apa pun untuk menemukan jika orang lain telah menemukan solusi yang lebih baik daripada yang Anda miliki; untuk yang kedua, Anda menyerah, atau merumuskan kembali masalah Anda menjadi sesuatu yang lebih bisa ditelusuri.

Saya akan meninggalkan Anda dengan penawaran dari Dianne O'Leary:

Hidup mungkin melemparkan kita beberapa masalah yang tidak terkondisikan, tetapi tidak ada alasan bagus untuk menerima algoritma yang tidak stabil.

karena basis 10 angka desimal tidak dapat dinyatakan dalam basis 2

atau dengan kata lain 1/10 tidak dapat diubah menjadi pecahan dengan kekuatan 2 dalam penyebutnya (yang pada dasarnya adalah angka-angka floating point)

Dalam matematika, ada banyak sekali bilangan rasional. Variabel 32 bit hanya dapat memiliki 2 ³² nilai yang berbeda, dan variabel 64 bit hanya 2 ⁶⁴ nilai. Karena itu, ada banyak bilangan rasional yang tidak memiliki representasi yang tepat.

Kita bisa membuat skema yang memungkinkan kita untuk mewakili 1/3 dengan sempurna, atau 1/100. Ternyata untuk banyak tujuan praktis ini tidak terlalu berguna. Ada satu pengecualian besar: di bidang keuangan, pecahan desimal sering muncul. Itu terutama karena keuangan pada dasarnya adalah aktivitas manusia, bukan aktivitas fisik.

Oleh karena itu, kami biasanya memilih untuk menggunakan binary floating point, dan membulatkan nilai apa pun yang tidak dapat direpresentasikan dalam biner. Namun dalam keuangan, kami terkadang memilih floating point desimal, dan membulatkan nilai ke nilai desimal terdekat.

satu-satunya "masalah pembulatan" yang benar-benar jelas dengan angka floating-point yang saya pikirkan adalah dengan filter rata-rata bergerak:

$$ \ begin {align} y [n] & = \ frac {1} {N} \ jumlah \ limit_ {i = 0} ^ {N-1} x [ni] \ & = y [n-1] + \ frac {1} {N} (x [n] - x [nN]) \ \ end {align} $$

untuk membuat ini bekerja tanpa penumpukan kebisingan, Anda ingin memastikan bahwa $ x [n] $ yang Anda tambahkan dalam sampel saat ini persis sama dengan $ x [nN] $ Anda akan mengurangi $ N $ sampel ke dalam masa depan. jika tidak, maka yang berbeda adalah kotoran kecil yang terjebak di garis penundaan Anda dan tidak akan pernah keluar. itu karena filter rata-rata bergerak ini sebenarnya dibangun dengan IIR yang memiliki kutub yang sedikit stabil pada $ z = 1 $ dan nol yang membatalkannya di dalam. tetapi, ini adalah integrator dan semua omong kosong yang terintegrasi dan tidak sepenuhnya dihapus akan ada dalam jumlah integrator selamanya. di sinilah titik tetap tidak memiliki masalah yang sama dengan angka titik apung.