Ketimpangan disebabkan oleh ketidaktepatan float

15

Paling tidak di Jawa, jika saya menulis kode ini:

float a = 1000.0F;
float b = 0.00004F;
float c = a + b + b;
float d = b + b + a;
boolean e = c == d;

nilai e akan . Saya percaya ini disebabkan oleh kenyataan bahwa pelampung sangat terbatas dalam cara merepresentasikan angka secara akurat. Tapi saya tidak mengerti mengapa hanya mengubah posisi dapat menyebabkan ketimpangan ini.fSebuahlseSebuah

Saya mengurangi s menjadi satu di kedua baris 3 dan 4 seperti di bawah ini, namun nilai menjadi :betrue

float a = 1000.0F;
float b = 0.00004F;
float c = a + b;
float d = b + a;
boolean e = c == d;

Apa yang sebenarnya terjadi pada baris 3 dan 4? Mengapa operasi penambahan dengan pelampung tidak asosiatif?

Terima kasih sebelumnya.

Zeta dikenal
sumber
16
Seperti yang ditunjukkan oleh contoh Anda, penambahan floating point bersifat komutatif. Tapi itu tidak asosiatif.
Yuval Filmus
1
Saya mendorong Anda untuk mencari definisi dasar. Perhatikan juga bahwa kompiler mem-parsing as ( r + s ) + t (penambahan terkait ke kiri). r+s+t(r+s)+t
Yuval Filmus
2
Untuk cara yang mudah untuk melihat mengapa ini harus terjadi, pertimbangkan Xjumlah yang sangat besar dan jumlah Yyang sangat kecil, sedemikian rupa X + Y = X. Di sini, X + Y + -Xakan menjadi nol. Tetapi X + -X + Yakan Y.
David Schwartz
1
@ J ... Dan Apa Yang Harus Diketahui Setiap Programmer Tentang Aritmatika Floating-Point .
Gilles 'SANGAT berhenti menjadi jahat'

Jawaban:

20

Dalam implementasi floating point tipikal, hasil dari satu operasi dihasilkan seolah-olah operasi dilakukan dengan ketepatan tak terbatas, dan kemudian dibulatkan ke angka floating-point terdekat.

Bandingkan dan b + a : Hasil setiap operasi yang dilakukan dengan ketepatan tak terbatas adalah sama, oleh karena itu hasil ketepatan tak terhingga identik ini dibulatkan dengan cara yang sama. Dengan kata lain, penambahan floating-point bersifat komutatif.Sebuah+bb+Sebuah

Ambil : b adalah angka floating-point. Dengan angka floating point biner , 2 b juga merupakan angka floating-point (eksponen lebih besar satu), jadi b + b ditambahkan tanpa kesalahan pembulatan. Kemudian sebuah ditambahkan ke tepat nilai b + b . Hasilnya adalah tepat nilai 2 b + a , dibulatkan ke terdekat angka floating-point.b+b+Sebuahb2bb+bSebuahb+b2b+Sebuah

Ambil : a + b ditambahkan, dan akan ada kesalahan pembulatan r , sehingga kami mendapatkan hasil yang + b + r . Menambahkan b , dan hasilnya adalah tepat nilai 2 b + a + r , dibulatkan ke terdekat angka floating-point.Sebuah+b+bSebuah+brSebuah+b+rb2b+Sebuah+r

Jadi dalam satu kasus, , bulat. Dalam kasus lain, 2 b + a + r , bulat.2b+Sebuah2b+Sebuah+r

PS. Apakah untuk dua angka tertentu dan b kedua perhitungan memberikan hasil yang sama atau tidak tergantung pada angka, dan pada kesalahan pembulatan dalam perhitungan a + b , dan biasanya sulit diprediksi. Menggunakan presisi tunggal atau ganda tidak membuat perbedaan pada masalah pada prinsipnya, tetapi karena kesalahan pembulatan berbeda, akan ada nilai-nilai a dan b di mana dalam presisi tunggal hasilnya sama dan dalam presisi ganda tidak, atau sebaliknya. Presisi akan jauh lebih tinggi, tetapi masalah bahwa dua ekspresi secara matematis sama tetapi tidak sama dalam aritmatika floating-point tetap sama.SebuahbSebuah+b

PPS. Dalam beberapa bahasa, aritmatika titik apung dapat dilakukan dengan presisi lebih tinggi atau rentang angka yang lebih tinggi daripada yang diberikan oleh pernyataan aktual. Dalam hal ini, akan jauh lebih mungkin (tetapi masih tidak dijamin) bahwa kedua jumlah memberikan hasil yang sama.

PPPS. Sebuah komentar bertanya apakah kita harus bertanya apakah angka floating point sama atau tidak sama sekali. Tentu saja jika Anda tahu apa yang Anda lakukan. Misalnya, jika Anda mengurutkan array, atau mengimplementasikan set, Anda mendapatkan masalah besar jika Anda ingin menggunakan beberapa gagasan "kira-kira sama". Dalam antarmuka pengguna grafis, Anda mungkin perlu menghitung ulang ukuran objek jika ukuran objek telah berubah - Anda membandingkan oldSize == newSize untuk menghindari perhitungan ulang itu, mengetahui bahwa dalam praktiknya Anda hampir tidak pernah memiliki ukuran yang hampir sama, dan program Anda benar bahkan jika ada perhitungan ulang yang tidak perlu.

gnasher729
sumber
Dalam kasus khusus ini, b menjadi periodik ketika dikonversi ke biner, jadi ada kesalahan pembulatan di mana-mana.
André Souza Lemos
1
@ AndréSouzaLemos bdalam jawaban ini bukan 0,00004, itu yang Anda dapatkan setelah konversi dan pembulatan.
Alexey Romanov
"Dalam implementasi floating point yang khas, hasil dari satu operasi dihasilkan seolah-olah operasi dilakukan dengan ketepatan tak terbatas, dan kemudian dibulatkan ke angka floating-point terdekat." - yang sebenarnya diamanatkan oleh spesifikasi, banyak yang membuat saya kecewa ketika saya mencoba untuk benar-benar menerapkan ini dalam hal gerbang logika (simulator hanya bisa menangani bus 64-bit).
John Dvorak
Pertanyaan naif: Apakah pengujian untuk kesetaraan float pernah masuk akal? Mengapa sebagian besar bahasa pemrograman memungkinkan aa == b menguji di mana keduanya atau satu merupakan float?
curious_cat
Definisi yang relevan dari Wikipedia: " Mesin Epsilon memberikan batas atas pada kesalahan relatif karena pembulatan dalam aritmatika titik mengambang."
Blackhawk
5

Format titik mengambang biner yang didukung oleh komputer pada dasarnya mirip dengan notasi ilmiah desimal yang digunakan oleh manusia.

Angka floating-point terdiri dari tanda, mantissa (lebar tetap), dan eksponen (lebar tetap), seperti ini:

+/-  1.0101010101 × 2^12345
sign   ^mantissa^     ^exp^

Notasi ilmiah reguler memiliki format yang serupa:

+/- 1.23456 × 10^99

Jika kita melakukan aritmatika dalam notasi ilmiah dengan presisi terbatas, pembulatan setelah setiap operasi, maka kita mendapatkan semua efek buruk yang sama dengan binary floating point.


Contoh

Sebagai ilustrasi, misalkan kita menggunakan tepat 3 digit setelah titik desimal.

a = 99990 = 9.999 × 10^4
b =     3 = 3.000 × 10^0

(a + b) + b

Sekarang kami menghitung:

c = a + b
  = 99990 + 3      (exact)
  = 99993          (exact)
  = 9.9993 × 10^4  (exact)
  = 9.999 × 10^4.  (rounded to nearest)

Pada langkah selanjutnya, tentu saja:

d = c + b
  = 99990 + 3 = ...
  = 9.999 × 10^4.  (rounded to nearest)

Karenanya (a + b) + b = 9,999 × 10 4 .

(b + b) + a

Tetapi jika kami melakukan operasi dalam urutan yang berbeda:

e = b + b
  = 3 + 3  (exact)
  = 6      (exact)
  = 6.000 × 10^0.  (rounded to nearest)

Selanjutnya kami menghitung:

f = e + a
  = 6 + 99990      (exact)
  = 99996          (exact)
  = 9.9996 × 10^4  (exact)
  = 1.000 × 10^5.  (rounded to nearest)

Karenanya (b + b) + a = 1.000 × 10 5 , yang berbeda dari jawaban kami yang lain.

Nayuki
sumber
5

Java menggunakan representasi titik mengambang biner IEEE 754, yang mendedikasikan 23 digit biner untuk mantissa, yang dinormalisasi untuk memulai dengan digit signifikan pertama (dihilangkan, untuk menghemat ruang).

0,0000410=0,00000000000000101001111100010110101100010001110001101101000111 ...2=[1.]01001111100010110101100010001110001101101000111 ...2×2-15

100010+0,0000410=1111101000.00000000000000101001111100010110101100010001110001101101000111 ...2=[1.]11110100000000000000000101001111100010110101100010001110001101101000111 ...2×29

Bagian merah adalah mantisa, karena mereka sebenarnya diwakili (sebelum pembulatan).

(100010+0,0000410)+0,0000410(0,0000410+0,0000410)+100010

André Souza Lemos
sumber
0

Kami baru-baru ini mengalami masalah pembulatan serupa. Jawaban yang disebutkan di atas benar, namun cukup teknis.

Saya menemukan berikut ini menjadi penjelasan yang bagus tentang mengapa kesalahan pembulatan ada. http://csharpindepth.com/Articles/General/FloatingPoint.aspx

TLDR: floating point biner tidak dapat dipetakan secara akurat ke floating point desimal. Ini menyebabkan ketidakakuratan yang dapat bertambah selama operasi matematika.

Contoh menggunakan angka mengambang desimal: 1/3 + 1/3 + 1/3 biasanya akan sama dengan 1. Namun, dalam desimal: 0,333333 + 0,333333 + 0,333333 tidak pernah persis sama dengan 1,000000

Hal yang sama terjadi ketika melakukan operasi matematika pada desimal biner.

Freek Sanders
sumber