Pertanyaan Apakah matematika floating point rusak?


Pertimbangkan kode berikut:

0.1 + 0.2 == 0.3  ->  false
0.1 + 0.2         ->  0.30000000000000004

Mengapa ketidakakuratan ini terjadi?


2259
2018-02-25 21:39


asal


Jawaban:


Biner titik mengambang matematika seperti ini. Dalam kebanyakan bahasa pemrograman, ini didasarkan pada Standar IEEE 754. JavaScript menggunakan representasi titik mengambang 64-bit, yang sama dengan Java double. Inti permasalahannya adalah angka-angka tersebut diwakili dalam format ini sebagai angka keseluruhan dikali dua; bilangan rasional (seperti 0.1, yang mana 1/10) yang penyebutnya bukan kekuatan dua tidak dapat diwakili dengan tepat.

Untuk 0.1 dalam standar binary64 format, representasi dapat ditulis persis seperti

  • 0.1000000000000000055511151231257827021181583404541015625 dalam desimal, atau
  • 0x1.999999999999ap-4 di Notasi hexfloat C99.

Sebaliknya, bilangan rasional 0.1, yang mana 1/10, dapat ditulis persis seperti

  • 0.1 dalam desimal, atau
  • 0x1.99999999999999...p-4 dalam analog notasi C99 hexfloat, di mana ... mewakili urutan 9 yang tak berujung.

Konstanta 0.2 dan 0.3 dalam program Anda juga akan menjadi perkiraan untuk nilai-nilai mereka yang sebenarnya. Itu terjadi yang paling dekat double untuk 0.2 lebih besar dari bilangan rasional 0.2 tapi itu yang paling dekat double untuk 0.3 lebih kecil dari bilangan rasional 0.3. Jumlah dari 0.1 dan 0.2 angin menjadi lebih besar dari bilangan rasional 0.3 dan karenanya tidak setuju dengan konstanta dalam kode Anda.

Perawatan yang cukup komprehensif dari masalah aritmatika floating-point Apa yang Setiap Ilmuwan Komputer Harus Ketahui Tentang Aritmatika Titik-Mengambang. Untuk penjelasan yang mudah dicerna, lihat floating-point-gui.de.


1718
2018-04-18 11:52



Perspektif Desainer Perangkat Keras

Saya percaya saya harus menambahkan perspektif perancang perangkat keras untuk ini karena saya mendesain dan membuat perangkat keras floating point. Mengetahui asal-usul kesalahan dapat membantu dalam memahami apa yang terjadi dalam perangkat lunak, dan pada akhirnya, saya harap ini membantu menjelaskan alasan mengapa kesalahan titik mengambang terjadi dan tampaknya terakumulasi dari waktu ke waktu.

1. Ikhtisar

Dari perspektif teknik, sebagian besar operasi floating point akan memiliki beberapa elemen kesalahan karena perangkat keras yang melakukan perhitungan floating point hanya diperlukan untuk memiliki kesalahan kurang dari satu setengah dari satu unit di tempat terakhir. Oleh karena itu, banyak perangkat keras akan berhenti pada ketepatan yang hanya diperlukan untuk menghasilkan kesalahan kurang dari setengah dari satu unit di tempat terakhir untuk operasi tunggal yang sangat bermasalah dalam pembagian floating point. Apa yang merupakan operasi tunggal tergantung pada berapa banyak operan yang dibutuhkan unit. Untuk sebagian besar, itu dua, tetapi beberapa unit mengambil 3 atau lebih operan. Karena itu, tidak ada jaminan bahwa operasi berulang akan menghasilkan kesalahan yang diinginkan karena kesalahan bertambah seiring waktu.

2. Standar

Sebagian besar prosesor mengikuti IEEE-754 standar tetapi beberapa menggunakan denormalized, atau standar yang berbeda . Sebagai contoh, ada mode denormalized di IEEE-754 yang memungkinkan representasi angka floating point yang sangat kecil dengan mengorbankan presisi. Akan tetapi, berikut ini akan mencakup mode normalisasi IEEE-754 yang merupakan mode operasi yang umum.

Dalam standar IEEE-754, perancang perangkat keras diperbolehkan nilai kesalahan / epsilon selama itu kurang dari satu setengah dari satu unit di tempat terakhir, dan hasilnya hanya harus kurang dari satu setengah dari satu unit di terakhir tempat untuk satu operasi. Ini menjelaskan mengapa ketika ada operasi berulang, kesalahan bertambah. Untuk presisi ganda IEEE-754, ini adalah bit ke-54, karena 53 bit digunakan untuk merepresentasikan bagian numerik (dinormalisasi), juga disebut mantissa, dari angka floating point (misalnya 5.3 dalam 5.3e5). Bagian selanjutnya membahas lebih detail tentang penyebab kesalahan perangkat keras pada berbagai operasi floating point.

3. Penyebab Kesalahan Pembulatan di Divisi

Penyebab utama kesalahan dalam pembagian floating point adalah pembagian algoritma yang digunakan untuk menghitung hasil bagi. Sebagian besar sistem komputer menghitung pembagian menggunakan perkalian dengan invers, terutama di Z=X/Y, Z = X * (1/Y). Pembagian dihitung secara iterasi yaitu setiap siklus menghitung beberapa bit hasil bagi sampai ketepatan yang diinginkan tercapai, yang untuk IEEE-754 adalah apa saja dengan kesalahan kurang dari satu unit di tempat terakhir. Tabel timbal balik Y (1 / Y) dikenal sebagai tabel pilihan bagi-bagi (QST) dalam pembagian yang lambat, dan ukuran dalam bit dari tabel pilihan bagi hasil biasanya adalah lebar radix, atau sejumlah bit dari hasil bagi dihitung dalam setiap iterasi, ditambah beberapa bit penjaga. Untuk standar IEEE-754, presisi ganda (64-bit), itu akan menjadi ukuran radix dari pembagi, ditambah beberapa bit penjaga k, di mana k>=2. Jadi misalnya, Tabel Pemilihan Quotient khas untuk pembagi yang menghitung 2 bit dari hasil bagi pada suatu waktu (radix 4) akan menjadi 2+2= 4 bit (ditambah beberapa bit opsional).

3.1 Pembulatan Divisi Error: Approximation of Reciprocal

Kebalikan apa yang ada dalam tabel pilihan bagi penerima bergantung pada metode pembagian: pembagian lambat seperti divisi SRT, atau divisi cepat seperti divisi Goldschmidt; setiap entri dimodifikasi sesuai dengan algoritma pembagian dalam upaya untuk menghasilkan kesalahan yang serendah mungkin. Bagaimanapun juga, semua timbal balik adalah perkiraan dari timbal balik yang sebenarnya dan memperkenalkan beberapa elemen kesalahan. Kedua pembagian lambat dan metode pembagian cepat menghitung hasil bagi secara iteratif, yaitu beberapa jumlah bit hasil bagi dihitung setiap langkah, kemudian hasilnya dikurangi dari dividen, dan pembagi mengulangi langkah-langkah sampai kesalahan kurang dari setengah dari satu unit di tempat terakhir. Metode pembelahan lambat menghitung jumlah digit yang tetap dari hasil bagi di setiap langkah dan biasanya lebih murah untuk dibangun, dan metode pembagian cepat menghitung jumlah digit variabel per langkah dan biasanya lebih mahal untuk dibangun. Bagian terpenting dari metode pembagian adalah sebagian besar dari mereka bergantung pada penggandaan berulang oleh suatu perkiraan dari timbal balik, sehingga mereka rentan terhadap kesalahan.

4. Kesalahan Pembulatan dalam Operasi Lain: Pemotongan

Penyebab lain dari kesalahan pembulatan di semua operasi adalah mode pemotongan yang berbeda dari jawaban akhir yang IEEE-754 memungkinkan. Ada truncate, bulat ke nol, bulat-ke-terdekat (standar), round-down, dan round-up. Semua metode memperkenalkan elemen kesalahan kurang dari satu unit di tempat terakhir untuk satu operasi. Seiring waktu dan operasi berulang, pemotongan juga menambahkan secara kumulatif ke kesalahan yang dihasilkan. Kesalahan pemotongan ini sangat bermasalah dalam eksponensial, yang melibatkan beberapa bentuk perkalian berulang.

5. Operasi Berulang

Karena perangkat keras yang melakukan penghitungan titik apung hanya perlu menghasilkan hasil dengan kesalahan kurang dari satu setengah dari satu unit di tempat terakhir untuk satu operasi, kesalahan akan tumbuh selama operasi berulang jika tidak ditonton. Ini adalah alasan bahwa dalam perhitungan yang memerlukan kesalahan terbatas, ahli matematika menggunakan metode seperti menggunakan putaran ke terdekat bahkan digit di tempat terakhir dari IEEE-754, karena, seiring waktu, kesalahan lebih cenderung membatalkan satu sama lain, dan Aritmatika Interval dikombinasikan dengan variasi IEEE 754 pembulatan mode untuk memprediksi kesalahan pembulatan, dan memperbaikinya. Karena kesalahan relatifnya yang rendah dibandingkan dengan mode pembulatan lainnya, putaran ke digit genap terdekat (di tempat terakhir), adalah mode pembulatan default IEEE-754.

Perhatikan bahwa mode pembulatan default, bulat-ke-terdekat bahkan digit di tempat terakhir, menjamin kesalahan kurang dari setengah dari satu unit di tempat terakhir untuk satu operasi. Menggunakan pemotongan, pembulatan, dan pembulatan saja dapat mengakibatkan kesalahan yang lebih besar dari setengah dari satu unit di tempat terakhir, tetapi kurang dari satu unit di tempat terakhir, sehingga mode ini tidak disarankan kecuali mereka digunakan dalam Aritmatika Interval.

6. Ringkasan

Singkatnya, alasan mendasar untuk kesalahan dalam operasi floating point adalah kombinasi pemotongan dalam perangkat keras, dan pemotongan timbal balik dalam kasus pembagian. Karena standar IEEE-754 hanya membutuhkan kesalahan kurang dari satu setengah dari satu unit di tempat terakhir untuk operasi tunggal, kesalahan floating point selama operasi berulang akan bertambah kecuali diperbaiki.


490
2018-02-25 21:43



Ketika Anda mengkonversi 0,1 atau 1/10 ke basis 2 (biner), Anda mendapatkan pola berulang setelah titik desimal, seperti mencoba untuk mewakili 1/3 dalam basis 10. Nilai tidak tepat, dan karena itu Anda tidak dapat melakukan matematika yang tepat dengan menggunakan metode floating point normal.


356
2017-11-20 02:39



Sebagian besar jawaban di sini menjawab pertanyaan ini dalam istilah teknis yang sangat kering. Saya ingin membahas hal ini dalam pengertian yang bisa dimengerti oleh manusia normal.

Bayangkan Anda sedang mencoba mengiris pizza. Anda memiliki pemotong pizza robot yang dapat memotong irisan pizza persis setengah. Ini dapat membagi dua pizza utuh, atau dapat membagi dua irisan yang sudah ada, tetapi dalam kasus apa pun, separuh selalu tepat.

Pemotong pizza itu memiliki gerakan yang sangat halus, dan jika Anda mulai dengan pizza utuh, kemudian mengurangi separuhnya, dan terus mengurangi separuh potongan terkecil setiap kali, Anda dapat melakukan separuh-separuh 53 kali sebelum irisan terlalu kecil bahkan untuk kemampuan presisi tinggi. Pada saat itu, Anda tidak dapat lagi memotong bagian yang sangat tipis itu, tetapi harus memasukkan atau mengecualikannya seperti apa adanya.

Sekarang, bagaimana Anda memotong semua irisan sedemikian rupa sehingga akan menambahkan hingga sepersepuluh (0,1) atau seperlima (0,2) pizza? Benar-benar memikirkannya, dan cobalah menyelesaikannya. Anda bahkan dapat mencoba menggunakan pizza sungguhan, jika Anda memiliki pemotong pizza presisi mistis di tangan. :-)


Programer yang paling berpengalaman, tentu saja, tahu jawaban yang sebenarnya, yaitu bahwa tidak ada cara untuk mengumpulkan satu tepat sepersepuluh atau kelima pizza menggunakan irisan tersebut, tidak peduli seberapa halus Anda mengirisnya. Anda dapat melakukan pendekatan yang cukup bagus, dan jika Anda menambahkan aproksimasi 0,1 dengan perkiraan 0,2, Anda mendapatkan aproksimasi yang cukup baik sebesar 0,3, tetapi masih saja, sebuah perkiraan.

Untuk angka presisi ganda (yang merupakan ketepatan yang memungkinkan Anda membagi dua porsi pizza Anda 53 kali), angka yang segera kurang dan lebih besar dari 0,1 adalah 0,09999999999999999167332731531132594682276248931884765625 dan 0,1000000000000000055511151231257827021181583404541015625. Yang terakhir ini sedikit lebih dekat dengan 0,1 dari yang sebelumnya, sehingga parser numerik akan, diberi masukan 0,1, mendukung yang terakhir.

(Perbedaan antara kedua angka tersebut adalah "potongan terkecil" yang harus kita putuskan untuk dimasukkan, yang memperkenalkan bias ke atas, atau tidak termasuk, yang memperkenalkan bias ke bawah. Istilah teknis untuk potongan terkecil adalah ulp.)

Dalam kasus 0,2, angka-angka semuanya sama, hanya ditingkatkan oleh faktor 2. Sekali lagi, kami mendukung nilai yang sedikit lebih tinggi dari 0,2.

Perhatikan bahwa pada kedua kasus, perkiraan untuk 0,1 dan 0,2 memiliki bias sedikit ke atas. Jika kita menambahkan cukup banyak bias ini, mereka akan mendorong nomor tersebut lebih jauh dan lebih jauh dari apa yang kita inginkan, dan faktanya, dalam kasus 0,1 + 0,2, bias cukup tinggi sehingga jumlah yang dihasilkan tidak lagi menjadi angka terdekat. 0,3.

Secara khusus, 0,1 + 0,2 benar-benar 0,1000000000000000055511151231257827021181583404541015625 + 0,200000000000000011102230246251565404236316680908203125 = 0,3000000000000000444089209850062616169452667236328125, sedangkan angka terdekat ke 0,3 sebenarnya 0,299999999999999988897769753748434595763683319091796875.


P.S. Beberapa bahasa pemrograman juga menyediakan pemotong pizza yang bisa potong irisan menjadi persepuluhan yang tepat. Meskipun pemotong pizza seperti itu jarang terjadi, jika Anda memiliki akses ke salah satu, Anda harus menggunakannya ketika sangat penting untuk bisa mendapatkan tepat sepersepuluh atau seperlima potongan.

(Awalnya diposting di Quora.)


225
2018-02-25 21:41



Kesalahan pembulatan titik mengambang. 0,1 tidak dapat direpresentasikan secara akurat dalam basis-2 seperti dalam basis-10 karena faktor prima yang hilang dari 5. Sama seperti 1/3 mengambil jumlah digit tak terbatas untuk mewakili dalam desimal, tetapi "0,1" dalam basis-3, 0,1 mengambil jumlah digit tak terbatas dalam basis-2 di mana tidak dalam basis-10. Dan komputer tidak memiliki jumlah memori yang tak terbatas.


199
2018-04-09 12:25



Selain jawaban yang benar lainnya, Anda mungkin ingin mempertimbangkan penskalaan nilai Anda untuk menghindari masalah dengan aritmatika floating-point.

Sebagai contoh:

var result = 1.0 + 2.0;     // result === 3.0 returns true

... dari pada:

var result = 0.1 + 0.2;     // result === 0.3 returns false

Ekspresi 0.1 + 0.2 === 0.3 kembali false dalam JavaScript, tetapi untungnya aritmatika bilangan bulat dalam floating-point tepat, sehingga kesalahan representasi desimal dapat dihindari dengan penskalaan.

Sebagai contoh praktis, untuk menghindari masalah floating-point di mana akurasi adalah yang terpenting, dianjurkan1 untuk menangani uang sebagai integer yang mewakili jumlah sen: 2550 sen bukan 25.50 dolar.


1 Douglas Crockford: JavaScript: Bagian-bagian yang Baik: Lampiran A - Bagian Mengerikan (halaman 105).


98
2018-02-23 17:15



Jawaban saya cukup panjang, jadi saya membaginya menjadi tiga bagian. Karena pertanyaannya adalah tentang matematika floating point, saya telah menekankan pada apa yang sebenarnya dilakukan oleh mesin. Saya juga membuatnya khusus untuk menggandakan (64 bit) presisi, tetapi argumen berlaku sama untuk setiap aritmatika floating point.

Pembukaan

Sebuah IEEE 754 presisi ganda format floating-point biner (binary64) angka mewakili sejumlah formulir

value = (-1) ^ s * (1.m51m50... m2m1m0)2 * 2e-1023

dalam 64 bit:

  • Bit pertama adalah menandatangani sedikit: 1 jika jumlahnya negatif, 0 jika tidak1.
  • 11 bit berikutnya adalah eksponen, yang mana mengimbangi oleh 1023. Dengan kata lain, setelah membaca bit eksponen dari angka presisi ganda, 1023 harus dikurangkan untuk mendapatkan kekuatan dua.
  • Sisa 52 bit adalah significand (atau mantissa). Di mantissa, sebuah 'tersirat' 1. selalu2 dihilangkan karena bit paling signifikan dari nilai biner apa pun 1.

1 - IEEE 754 memungkinkan untuk konsep a bertanda nol - +0 dan -0 diperlakukan berbeda: 1 / (+0) infinity positif; 1 / (-0) adalah infinity negatif. Untuk nilai nol, bit mantissa dan eksponen semuanya nol. Catatan: nilai nol (+0 dan -0) secara eksplisit tidak digolongkan sebagai denormal2.

2 - Ini bukan kasusnya angka denormal, yang memiliki eksponen offset nol (dan tersirat 0.). Rentang nomor presisi ganda denormal adalah dmnt ≤ | x | ≤ dmaks, dimana Dmnt (Angka nol nol terkecil) adalah 2-1023 - 51 (≈ 4,94 * 10-324) dan dmaks (angka denormal terbesar, di mana mantissa seluruhnya terdiri dari 1s) adalah 2-1023 + 1 - 2-1023 - 51 (≈ 2,225 * 10-308).


Mengubah nomor presisi ganda menjadi biner

Banyak konverter daring tersedia untuk mengonversi nomor titik presisi ganda ke biner (mis. Di binaryconvert.com), tapi di sini adalah beberapa contoh kode C # untuk mendapatkan representasi IEEE 754 untuk nomor presisi ganda (saya memisahkan tiga bagian dengan titik dua (:):

public static string BinaryRepresentation(double value)
{
    long valueInLongType = BitConverter.DoubleToInt64Bits(value);
    string bits = Convert.ToString(valueInLongType, 2);
    string leadingZeros = new string('0', 64 - bits.Length);
    string binaryRepresentation = leadingZeros + bits;

    string sign = binaryRepresentation[0].ToString();
    string exponent = binaryRepresentation.Substring(1, 11);
    string mantissa = binaryRepresentation.Substring(12);

    return string.Format("{0}:{1}:{2}", sign, exponent, mantissa);
}

Sampai pada intinya: pertanyaan asli

(Lewati ke bagian bawah untuk versi TL; DR)

Cato Johnston (pertanyaan penanya) bertanya mengapa 0,1 + 0,2! = 0,3.

Ditulis dalam biner (dengan titik dua yang memisahkan ketiga bagian), representasi IEEE 754 dari nilai adalah:

0.1 => 0:01111111011:1001100110011001100110011001100110011001100110011010
0.2 => 0:01111111100:1001100110011001100110011001100110011001100110011010

Perhatikan bahwa mantissa terdiri dari digit berulang 0011. Ini adalah kunci mengapa ada kesalahan pada perhitungan - 0,1, 0,2 dan 0,3 tidak dapat diwakili dalam biner tepat di sebuah terbatas jumlah bit biner lebih dari 1/9, 1/3 atau 1/7 dapat diwakili secara tepat dalam digit desimal.

Mengubah eksponen menjadi desimal, menghapus offset, dan menambahkan kembali yang tersirat 1 (dalam tanda kurung siku), 0,1 dan 0,2 adalah:

0.1 = 2^-4 * [1].1001100110011001100110011001100110011001100110011010
0.2 = 2^-3 * [1].1001100110011001100110011001100110011001100110011010

Untuk menambahkan dua angka, eksponen harus sama, yaitu:

0.1 = 2^-3 *  0.1100110011001100110011001100110011001100110011001101(0)
0.2 = 2^-3 *  1.1001100110011001100110011001100110011001100110011010
sum = 2^-3 * 10.0110011001100110011001100110011001100110011001100111

Karena jumlahnya bukan dari bentuk 2n * 1. {bbb} kita meningkatkan eksponen dengan satu dan menggeser desimal (biner) titik untuk mendapatkan:

sum = 2^-2 * 1.0011001100110011001100110011001100110011001100110011(1)

Sekarang ada 53 bit di mantissa (yang ke 53 berada dalam tanda kurung persegi pada baris di atas). Defaultnya mode pembulatan untuk IEEE 754 adalah 'Membulatkan ke Terdekat'- yaitu jika nomor x jatuh di antara dua nilai Sebuah dan b, nilai di mana bit paling signifikan adalah nol yang dipilih.

a = 2^-2 * 1.0011001100110011001100110011001100110011001100110011
x = 2^-2 * 1.0011001100110011001100110011001100110011001100110011(1)
b = 2^-2 * 1.0011001100110011001100110011001100110011001100110100

Perhatikan itu Sebuah dan b hanya berbeda di bagian terakhir; ...0011 + 1 = ...0100. Dalam hal ini, nilai dengan bit nol paling signifikan adalah b, jadi jumlahnya adalah:

sum = 2^-2 * 1.0011001100110011001100110011001100110011001100110100

TL; DR

Penulisan 0.1 + 0.2 dalam representasi biner IEEE 754 (dengan titik dua yang memisahkan ketiga bagian) dan membandingkannya 0.3, ini (saya telah menaruh bit yang berbeda dalam tanda kurung siku):

0.1 + 0.2 => 0:01111111101:0011001100110011001100110011001100110011001100110[100]
0.3       => 0:01111111101:0011001100110011001100110011001100110011001100110[011]

Dikonversi kembali ke desimal, nilai-nilai ini adalah:

0.1 + 0.2 => 0.300000000000000044408920985006...
0.3       => 0.299999999999999988897769753748...

Perbedaannya persis 2-54, yaitu ~ 5.5511151231258 × 10-17 - tidak signifikan (untuk banyak aplikasi) jika dibandingkan dengan nilai aslinya.

Membandingkan beberapa bit terakhir dari angka floating point secara inheren berbahaya, seperti orang yang membaca yang terkenal "Apa yang Setiap Ilmuwan Komputer Harus Ketahui Tentang Aritmatika Titik-Mengambang"(yang mencakup semua bagian utama dari jawaban ini) akan tahu.

Sebagian kalkulator menggunakan tambahan digit penjaga untuk mengatasi masalah ini, yaitu bagaimana caranya 0.1 + 0.2 akan memberi 0.3: beberapa bit terakhir dibulatkan.


80
2018-03-16 05:27