Apakah mungkin mendapatkan 0 dengan mengurangi dua angka floating point yang tidak sama?

131

Apakah mungkin mendapatkan pembagian dengan 0 (atau tak terhingga) dalam contoh berikut?

public double calculation(double a, double b)
{
     if (a == b)
     {
         return 0;
     }
     else
     {
         return 2 / (a - b);
     }
}

Dalam kasus normal, tentu saja tidak. Tetapi bagaimana jika adan bsangat dekat, dapat (a-b)menyebabkan 0ketepatan perhitungan?

Perhatikan bahwa pertanyaan ini untuk Java, tapi saya pikir itu akan berlaku untuk sebagian besar bahasa pemrograman.

Thirler
sumber
49
Saya harus mencoba semua kombinasi ganda, itu akan memakan waktu :)
Thirler
3
@Thirler terdengar seperti waktu untuk menggunakan JUnit Testing kepada saya!
Matt Clark
7
@ Benebrain, tebakan saya adalah bahwa angka literal Anda 2.000 dll berisi banyak desimal untuk diwakili oleh float. Jadi yang terakhir tidak akan diwakili oleh angka yang digunakan sebenarnya dalam perbandingan.
Thirler
4
@Thirler mungkin. 'Anda tidak dapat benar-benar menjamin bahwa nomor yang Anda tetapkan untuk float atau dobel adalah tepat'
guness
4
Perhatikan saja bahwa mengembalikan 0 dalam kasus itu dapat menyebabkan ambiguitas yang sulit di-debug, jadi pastikan Anda benar-benar ingin mengembalikan 0 alih-alih melempar pengecualian atau mengembalikan NaN.
m0skit0

Jawaban:

132

Di Jawa, a - btidak pernah sama dengan 0jika a != b. Ini karena Java mengamanatkan operasi floating point IEEE 754 yang mendukung angka denormalized. Dari spec :

Secara khusus, bahasa pemrograman Java membutuhkan dukungan nomor floating-point yang didenormalkan IEEE 754 dan underflow bertahap, yang membuatnya lebih mudah untuk membuktikan sifat-sifat yang diinginkan dari algoritma numerik tertentu. Operasi floating-point tidak "flush to zero" jika hasil yang dihitung adalah angka yang dinormalkan.

Jika FPU bekerja dengan angka yang didenormalkan , mengurangi angka yang tidak sama tidak akan pernah menghasilkan nol (tidak seperti penggandaan), lihat juga pertanyaan ini .

Untuk bahasa lain, itu tergantung. Dalam C atau C ++, misalnya, dukungan IEEE 754 adalah opsional.

Yang mengatakan, adalah mungkin untuk ekspresi 2 / (a - b)meluap, misalnya dengan a = 5e-308dan b = 4e-308.

nwellnhof
sumber
4
Namun OP ingin tahu tentang 2 / (ab). Bisakah ini dijamin terbatas?
Taemyr
Terima kasih atas jawabannya, saya menambahkan tautan ke wikipedia untuk penjelasan angka yang didenormalkan.
Thirler
3
@ Taemyr Lihat hasil edit saya. Divisi ini sebenarnya bisa meluap.
nwellnhof
@Taemyr (a,b) = (3,1)=> 2/(a-b) = 2/(3-1) = 2/2 = 1Apakah ini benar dengan IEEE floating point, saya tidak tahu
Cole Johnson
1
@DrewDormann IEEE 754 juga opsional untuk C99. Lihat Lampiran F standar.
nwellnhof
50

Sebagai solusinya, bagaimana dengan yang berikut ini?

public double calculation(double a, double b) {
     double c = a - b;
     if (c == 0)
     {
         return 0;
     }
     else
     {
         return 2 / c;
     }
}

Dengan begitu Anda tidak bergantung pada dukungan IEEE dalam bahasa apa pun.

malarres
sumber
6
Hindari masalah dan sederhanakan tes sekaligus. Aku suka.
Joshua
11
-1 Jika a=b, Anda tidak boleh kembali 0. Membagi dengan 0di IEEE 754 membuat Anda tak terbatas, tidak terkecuali. Anda menghindari masalah, jadi kembali 0adalah bug yang menunggu untuk terjadi. Pertimbangkan 1/x + 1. Jika x=0, itu menghasilkan 1, bukan nilai yang benar: infinity.
Cole Johnson
5
@ColeJohnson jawaban yang benar juga tidak terbatas (kecuali Anda menentukan dari sisi mana batas berasal, sisi kanan = + inf, sisi kiri = -inf, tidak ditentukan = tidak terdefinisi atau NaN).
Nick T
12
@ChrisHayes: Ini adalah jawaban yang valid untuk pertanyaan yang mengakui bahwa pertanyaan tersebut mungkin merupakan masalah XY: meta.stackexchange.com/questions/66377/what-is-the-xy-problem
slebetman
17
@ColeJohnson Kembali 0tidak benar-benar masalah. Inilah yang dilakukan OP dalam pertanyaan. Anda bisa meletakkan pengecualian atau apa pun yang sesuai untuk situasi di bagian blok itu. Jika Anda tidak suka kembali 0, itu seharusnya kritik terhadap pertanyaan itu. Tentu saja, melakukan seperti yang dilakukan OP tidak menjamin downvote untuk jawabannya. Pertanyaan ini tidak ada hubungannya dengan perhitungan lebih lanjut setelah fungsi yang diberikan selesai. Untuk semua yang Anda tahu, persyaratan program harus dikembalikan 0.
jpmc26
25

Anda tidak akan mendapatkan pembagian dengan nol terlepas dari nilainya a - b, karena pembagian floating point dengan 0 tidak menghasilkan pengecualian. Ia mengembalikan tak terhingga.

Sekarang, satu-satunya cara a == bmengembalikan true adalah jika adan bmengandung bit yang sama persis. Jika mereka berbeda sedikit saja, perbedaan di antara mereka tidak akan menjadi 0.

EDIT:

Seperti yang dikatakan Batsyeba dengan benar, ada beberapa pengecualian:

  1. "Bukan angka yang membandingkan" salah dengan dirinya sendiri tetapi akan memiliki pola bit yang identik.

  2. -0.0 didefinisikan untuk membandingkan true dengan +0.0, dan pola bit mereka berbeda.

Jadi jika keduanya adan bini Double.NaN, Anda akan mencapai klausa lain, tetapi karena NaN - NaNjuga kembali NaN, Anda tidak akan membaginya dengan nol.

Eran
sumber
11
Eran; tidak sepenuhnya benar. "Bukan angka yang membandingkan" salah dengan dirinya sendiri tetapi akan memiliki pola bit yang identik. Juga -0.0 didefinisikan untuk membandingkan true dengan +0.0, dan pola bit mereka berbeda.
Batsyeba
1
@Bathsheba Saya tidak mempertimbangkan kasus khusus ini. Terima kasih atas komentarnya.
Eran
2
@Ran, titik yang sangat baik bahwa pembagian dengan 0 akan mengembalikan tak terhingga di titik mengambang. Menambahkannya ke pertanyaan.
Thirler
2
@Prashant tetapi pembagian tidak akan terjadi dalam kasus ini, karena a == b akan mengembalikan true.
Eran
3
Sebenarnya Anda bisa mendapatkan pengecualian FP untuk pembagian dengan nol, ini merupakan opsi yang ditentukan oleh standar IEEE-754, meskipun mungkin bukan itu yang dimaksud kebanyakan orang dengan "pengecualian";)
Voo
17

Tidak ada kasus di mana pembagian dengan nol dapat terjadi di sini.

The SMT Solver Z3 mendukung IEEE tepat aritmatika floating point. Mari kita minta Z3 untuk menemukan angka adan bsedemikian rupa sehingga a != b && (a - b) == 0:

(set-info :status unknown)
(set-logic QF_FP)
(declare-fun b () (FloatingPoint 8 24))
(declare-fun a () (FloatingPoint 8 24))
(declare-fun rm () RoundingMode)
(assert
(and (not (fp.eq a b)) (fp.eq (fp.sub rm a b) +zero) true))
(check-sat)

Hasilnya adalah UNSAT. Tidak ada angka seperti itu.

String SMTLIB di atas juga memungkinkan Z3 untuk memilih mode pembulatan sewenang-wenang ( rm). Ini berarti bahwa hasilnya berlaku untuk semua mode pembulatan yang mungkin (yang ada lima). Hasilnya juga mencakup kemungkinan bahwa salah satu variabel dalam permainan mungkin NaNatau tidak terbatas.

a == bdiimplementasikan sebagai fp.eqkualitas sehingga +0fdan -0fmembandingkan sama. Perbandingan dengan nol diimplementasikan menggunakan fp.eqjuga. Karena pertanyaannya ditujukan untuk menghindari pembagian dengan nol, ini adalah perbandingan yang tepat.

Jika tes kesetaraan diimplementasikan menggunakan persamaan bitwise, +0fdan -0fakan menjadi cara untuk membuat a - bnol. Versi sebelumnya yang salah dari jawaban ini berisi detail mode tentang kasus itu untuk yang penasaran.

Z3 Online belum mendukung teori FPA. Hasil ini diperoleh dengan menggunakan cabang tidak stabil terbaru. Itu dapat direproduksi menggunakan .NET bindings sebagai berikut:

var fpSort = context.MkFPSort32();
var aExpr = (FPExpr)context.MkConst("a", fpSort);
var bExpr = (FPExpr)context.MkConst("b", fpSort);
var rmExpr = (FPRMExpr)context.MkConst("rm", context.MkFPRoundingModeSort());
var fpZero = context.MkFP(0f, fpSort);
var subExpr = context.MkFPSub(rmExpr, aExpr, bExpr);
var constraintExpr = context.MkAnd(
        context.MkNot(context.MkFPEq(aExpr, bExpr)),
        context.MkFPEq(subExpr, fpZero),
        context.MkTrue()
    );

var smtlibString = context.BenchmarkToSMTString(null, "QF_FP", null, null, new BoolExpr[0], constraintExpr);

var solver = context.MkSimpleSolver();
solver.Assert(constraintExpr);

var status = solver.Check();
Console.WriteLine(status);

Menggunakan Z3 untuk menjawab pertanyaan mengambang IEEE bagus karena sulit untuk mengabaikan kasus-kasus (seperti NaN, -0f, +-inf) dan Anda dapat mengajukan pertanyaan yang sewenang-wenang. Tidak perlu menafsirkan dan mengutip spesifikasi. Anda bahkan dapat mengajukan pertanyaan campuran mengambang dan bilangan bulat seperti "apakah int log2(float)algoritma khusus ini benar?".

usr
sumber
Bisakah Anda menambahkan tautan ke SMT Solver Z3 dan tautan ke juru bahasa online? Meskipun jawaban ini tampaknya benar-benar sah, seseorang dapat berpikir bahwa hasil ini salah.
AL
12

Fungsi yang disediakan memang dapat mengembalikan tak terhingga:

public class Test {
    public static double calculation(double a, double b)
    {
         if (a == b)
         {
             return 0;
         }
         else
         {
             return 2 / (a - b);
         }
    }    

    /**
     * @param args
     */
    public static void main(String[] args) {
        double d1 = Double.MIN_VALUE;
        double d2 = 2.0 * Double.MIN_VALUE;
        System.out.println("Result: " + calculation(d1, d2)); 
    }
}

Outputnya adalah Result: -Infinity.

Ketika hasil pembagian adalah besar untuk disimpan dalam dobel, infinity dikembalikan bahkan jika penyebutnya bukan nol.

D Krueger
sumber
6

Dalam implementasi floating-point yang sesuai dengan IEEE-754, setiap tipe floating-point dapat menyimpan angka dalam dua format. Satu ("dinormalisasi") digunakan untuk sebagian besar nilai floating-point, tetapi angka terkecil kedua yang dapat diwakilinya hanya sedikit lebih besar dari yang terkecil, sehingga perbedaan di antara keduanya tidak dapat diwakili dalam format yang sama. Format lain ("dinormalkan") hanya digunakan untuk angka yang sangat kecil yang tidak dapat diwakili dalam format pertama.

Sirkuit untuk menangani format floating-point yang didenormalkan secara efisien mahal, dan tidak semua prosesor memasukkannya. Beberapa prosesor menawarkan pilihan antara memiliki operasi pada angka yang sangat kecil jauh lebih lambat daripada operasi pada nilai-nilai lain, atau meminta prosesor menganggap angka yang terlalu kecil untuk format yang dinormalisasi menjadi nol.

Spesifikasi Java menyiratkan bahwa implementasi harus mendukung format denormalized, bahkan pada mesin yang melakukannya akan membuat kode berjalan lebih lambat. Di sisi lain, ada kemungkinan bahwa beberapa implementasi mungkin menawarkan opsi untuk memungkinkan kode berjalan lebih cepat dengan imbalan penanganan nilai yang sedikit ceroboh yang untuk sebagian besar tujuan terlalu kecil untuk diperhitungkan (dalam kasus di mana nilai terlalu kecil untuk diperhitungkan, itu dapat menjengkelkan memiliki perhitungan dengan mereka membutuhkan waktu sepuluh kali selama perhitungan itu penting, sehingga dalam banyak situasi praktis flush-to-zero lebih berguna daripada aritmatika lambat tapi akurat).

supercat
sumber
6

Dahulu sebelum IEEE 754, sangat mungkin bahwa a! = B tidak menyiratkan ab! = 0 dan sebaliknya. Itu adalah salah satu alasan untuk membuat IEEE 754 di tempat pertama.

Dengan IEEE 754 hampir dijamin. Kompiler C atau C ++ diizinkan untuk melakukan operasi dengan presisi lebih tinggi dari yang dibutuhkan. Jadi jika a dan b bukan variabel tetapi ekspresi, maka (a + b)! = C tidak menyiratkan (a + b) - c! = 0, karena a + b dapat dihitung sekali dengan presisi lebih tinggi, dan sekali tanpa presisi yang lebih tinggi.

Banyak FPU dapat dialihkan ke mode di mana mereka tidak mengembalikan angka dinormalkan tetapi ganti dengan 0. Dalam mode itu, jika a dan b adalah angka normal kecil di mana perbedaannya lebih kecil dari angka normalisasi terkecil tetapi lebih besar dari 0, a ! = b juga tidak menjamin a == b.

"Jangan pernah membandingkan angka titik apung" adalah pemrograman pemujaan kargo. Di antara orang-orang yang memiliki mantra "Anda membutuhkan epsilon", sebagian besar tidak tahu bagaimana memilih epsilon dengan benar.

gnasher729
sumber
2

Saya dapat memikirkan sebuah kasus di mana Anda mungkin dapat menyebabkan ini terjadi. Berikut adalah sampel analog pada basis 10 - sungguh, ini akan terjadi pada basis 2, tentu saja.

Angka titik apung disimpan lebih atau kurang dalam notasi ilmiah - yaitu, alih-alih melihat 35.2, angka yang disimpan akan lebih seperti 3.52e2.

Bayangkan demi kenyamanan bahwa kita memiliki unit floating point yang beroperasi di basis 10 dan memiliki 3 digit akurasi. Apa yang terjadi ketika Anda mengurangi 9,99 dari 10,0?

1,00e2-9,99e1

Shift untuk memberi masing-masing nilai eksponen yang sama

1,00e2-0,999e2

Membulatkan menjadi 3 digit

1,00e2-1,00e2

Uh oh!

Apakah ini bisa terjadi pada akhirnya tergantung pada desain FPU. Karena kisaran eksponen untuk double sangat besar, perangkat keras harus membulatkannya secara internal pada beberapa titik, tetapi dalam kasus di atas, hanya 1 digit tambahan secara internal akan mencegah masalah.

Keldor314
sumber
1
Register yang memegang operan selaras untuk pengurangan diminta untuk memegang dua bit tambahan, yang disebut "bit penjaga", untuk menangani situasi ini. Dalam skenario di mana pengurangan akan menyebabkan pinjaman dari bit yang paling signifikan, baik besarnya operan yang lebih kecil harus melebihi setengah dari operan yang lebih besar (menyiratkan bahwa itu hanya dapat memiliki satu bit ekstra presisi) atau kalau tidak hasilnya harus setidaknya setengah besarnya operan yang lebih kecil (menyiratkan bahwa itu hanya akan membutuhkan hanya satu bit lagi, ditambah informasi yang cukup untuk memastikan pembulatan yang benar).
supercat
1
"Apakah ini bisa terjadi pada akhirnya tergantung pada desain FPU" Tidak, itu tidak dapat terjadi karena definisi Java mengatakan itu tidak bisa. Desain FPU tidak ada hubungannya dengan itu.
Pascal Cuoq
@PascalCuoq: Perbaiki saya jika saya salah, tetapi strictfptidak diaktifkan, mungkin saja perhitungan menghasilkan nilai yang terlalu kecil untuk doubletetapi akan cocok dengan nilai floating-point presisi yang diperluas.
supercat
@supercat Tidak adanya strictfphanya memengaruhi nilai "hasil antara", dan saya mengutip dari docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.4 . adan bmerupakan doublevariabel, bukan hasil antara, jadi nilainya adalah nilai presisi ganda, sehingga merupakan kelipatan 2 ^ -1074. Pengurangan dua nilai presisi ganda ini adalah kelipatan dari 2 ^ -1074, sehingga rentang eksponen yang lebih luas mengubah properti bahwa selisihnya adalah 0 iff a == b.
Pascal Cuoq
@supercat Ini masuk akal - Anda hanya perlu satu bit ekstra untuk melakukan ini.
Keldor314
1

Anda seharusnya tidak pernah membandingkan pelampung atau dobel untuk kesetaraan; karena, Anda tidak dapat benar-benar menjamin bahwa nomor yang Anda tetapkan untuk float atau dobel adalah tepat.

Untuk membandingkan mengapung untuk persamaan, Anda perlu memeriksa apakah nilainya "cukup dekat" dengan nilai yang sama:

if ((first >= second - error) || (first <= second + error)
aviad
sumber
6
"Seharusnya tidak pernah" agak kuat, tetapi umumnya ini saran yang bagus.
Mark Pattison
1
Meskipun Anda benar, abs(first - second) < error(atau <= error) lebih mudah dan lebih ringkas.
glglgl
3
Meskipun benar dalam kebanyakan kasus ( tidak semua ), tidak benar-benar menjawab pertanyaan.
milleniumbug
4
Menguji angka floating-point untuk kesetaraan cukup sering berguna. Tidak ada yang waras tentang membandingkan dengan epsilon yang belum dipilih dengan cermat, dan bahkan lebih tidak waras tentang membandingkan dengan epsilon ketika seseorang menguji kesetaraan.
tmyklebu
1
Jika Anda mengurutkan array pada kunci floating-point, saya dapat menjamin bahwa kode Anda tidak akan berfungsi jika Anda mencoba menggunakan trik membandingkan angka floating-point dengan epsilon. Karena jaminan bahwa a == b dan b == c menyiratkan a == c tidak ada lagi. Untuk tabel hash, masalah yang sama persis. Ketika kesetaraan tidak transitif, algoritme Anda akan rusak.
gnasher729
1

Pembagian dengan nol tidak ditentukan, karena batas dari bilangan positif cenderung hingga tak terbatas, terbatas dari bilangan negatif cenderung tak hingga negatif.

Tidak yakin apakah ini C ++ atau Java karena tidak ada tag bahasa.

double calculation(double a, double b)
{
     if (a == b)
     {
         return nan(""); // C++

         return Double.NaN; // Java
     }
     else
     {
         return 2 / (a - b);
     }
}
Khaled.K
sumber
1

Masalah intinya adalah bahwa representasi komputer dari ganda (alias float, atau bilangan real dalam bahasa matematika) salah ketika Anda memiliki "terlalu banyak" desimal, misalnya ketika Anda berurusan dengan ganda yang tidak dapat ditulis sebagai nilai numerik ( pi atau hasil 1/3).

Jadi a == b tidak dapat dilakukan dengan nilai ganda a dan b, bagaimana Anda berurusan dengan a == b ketika a = 0,333 dan b = 1/3? Bergantung pada OS Anda vs FPU vs angka vs bahasa versus hitungan 3 setelah 0, Anda akan memiliki benar atau salah.

Pokoknya jika Anda melakukan "perhitungan nilai ganda" pada komputer, Anda harus berurusan dengan akurasi, jadi alih-alih melakukan a==b, Anda harus melakukannya absolute_value(a-b)<epsilon, dan epsilon relatif terhadap apa yang Anda modelkan pada waktu itu dalam algoritma Anda. Anda tidak dapat memiliki nilai epsilon untuk semua perbandingan ganda Anda.

Singkatnya, ketika Anda mengetik a == b, Anda memiliki ekspresi matematika yang tidak dapat diterjemahkan pada komputer (untuk setiap angka floating point).

PS: hum, semua yang saya jawab di sini kurang lebih dalam tanggapan dan komentar orang lain.

Jean Davy
sumber
1

Berdasarkan tanggapan @malarres dan komentar @Taemyr, inilah kontribusi kecil saya:

public double calculation(double a, double b)
{
     double c = 2 / (a - b);

     // Should not have a big cost.
     if (isnan(c) || isinf(c))
     {
         return 0; // A 'whatever' value.
     }
     else
     {
         return c;
     }
}

Maksud saya adalah mengatakan: cara termudah untuk mengetahui apakah hasil pembagian adalah nan atau inf sebenarnya untuk melakukan pembagian.

Orace
sumber