Mengapa mengubah jumlah pesanan mengembalikan hasil yang berbeda?

Mengapa mengubah jumlah pesanan mengembalikan hasil yang berbeda?

23.53 + 5.88 + 17.64 = 47.05

23.53 + 17.64 + 5.88 = 47.050000000000004

Kedua Java dan JavaScript mengembalikan hasil yang sama.

Saya mengerti bahwa, karena cara angka floating point direpresentasikan dalam biner, beberapa bilangan rasional ( seperti 1/3 - 0,333333 ... ) tidak dapat direpresentasikan secara tepat.

Mengapa hanya mengubah urutan elemen mempengaruhi hasilnya?

Mungkin pertanyaan ini bodoh, tetapi mengapa hanya mengubah urutan elemen mempengaruhi hasilnya?

Ini akan mengubah titik di mana nilai dibulatkan, berdasarkan besarnya mereka. Sebagai contoh dari jenis hal yang kita lihat, mari kita berpura-pura bahwa alih-alih binary floating point, kita menggunakan tipe floating point desimal dengan 4 digit signifikan, di mana setiap penambahan dilakukan pada presisi "tak terbatas" dan kemudian dibulatkan menjadi nomor representatif terdekat. Berikut ini dua jumlah:

1/3 + 2/3 + 2/3 = (0.3333 + 0.6667) + 0.6667
                = 1.000 + 0.6667 (no rounding needed!)
                = 1.667 (where 1.6667 is rounded to 1.667)

2/3 + 2/3 + 1/3 = (0.6667 + 0.6667) + 0.3333
                = 1.333 + 0.3333 (where 1.3334 is rounded to 1.333)
                = 1.666 (where 1.6663 is rounded to 1.666)

Kami bahkan tidak perlu non-integer untuk ini menjadi masalah:

10000 + 1 - 10000 = (10000 + 1) - 10000
                  = 10000 - 10000 (where 10001 is rounded to 10000)
                  = 0

10000 - 10000 + 1 = (10000 - 10000) + 1
                  = 0 + 1
                  = 1

Ini menunjukkan kemungkinan yang lebih jelas bahwa bagian yang penting adalah kita memiliki jumlah digit signifikan yang terbatas - bukan jumlah desimal yang terbatas . Jika kita selalu bisa menjaga jumlah tempat desimal yang sama, maka setidaknya dengan penambahan dan pengurangan, kita akan baik-baik saja (asalkan nilainya tidak meluap). Masalahnya adalah ketika Anda mencapai angka yang lebih besar, informasi yang lebih kecil hilang - 10001 dibulatkan menjadi 10.000 dalam kasus ini. (Ini adalah contoh masalah yang dicatat Eric Lippert dalam jawabannya .)

Penting untuk dicatat bahwa nilai pada baris pertama dari sisi kanan adalah sama dalam semua kasus - jadi meskipun penting untuk memahami bahwa angka desimal Anda (23.53, 5.88, 17.64) tidak akan direpresentasikan persis seperti doublenilai, itu hanya masalah karena masalah yang ditunjukkan di atas.

Inilah yang terjadi dalam biner. Seperti yang kita ketahui, beberapa nilai floating-point tidak dapat direpresentasikan secara tepat dalam biner, bahkan jika mereka dapat direpresentasikan secara tepat dalam desimal. 3 angka ini hanyalah contoh dari fakta itu.

Dengan program ini saya menampilkan representasi heksadesimal dari setiap angka dan hasil dari setiap penambahan.

public class Main{
   public static void main(String args[]) {
      double x = 23.53;   // Inexact representation
      double y = 5.88;    // Inexact representation
      double z = 17.64;   // Inexact representation
      double s = 47.05;   // What math tells us the sum should be; still inexact

      printValueAndInHex(x);
      printValueAndInHex(y);
      printValueAndInHex(z);
      printValueAndInHex(s);

      System.out.println("--------");

      double t1 = x + y;
      printValueAndInHex(t1);
      t1 = t1 + z;
      printValueAndInHex(t1);

      System.out.println("--------");

      double t2 = x + z;
      printValueAndInHex(t2);
      t2 = t2 + y;
      printValueAndInHex(t2);
   }

   private static void printValueAndInHex(double d)
   {
      System.out.println(Long.toHexString(Double.doubleToLongBits(d)) + ": " + d);
   }
}

The printValueAndInHexMetode ini hanya pembantu hex-printer.

Outputnya adalah sebagai berikut:

403787ae147ae148: 23.53
4017851eb851eb85: 5.88
4031a3d70a3d70a4: 17.64
4047866666666666: 47.05
--------
403d68f5c28f5c29: 29.41
4047866666666666: 47.05
--------
404495c28f5c28f6: 41.17
4047866666666667: 47.050000000000004

4 angka pertama adalah x, y, z, dan s's representasi heksadesimal. Dalam representasi floating point IEEE, bit 2-12 mewakili eksponen biner , yaitu skala angka. (Bit pertama adalah bit tanda, dan bit yang tersisa untuk mantissa .) Eksponen yang diwakili sebenarnya adalah angka biner minus 1023.

Eksponen untuk 4 angka pertama diekstraksi:

    sign|exponent
403 => 0|100 0000 0011| => 1027 - 1023 = 4
401 => 0|100 0000 0001| => 1025 - 1023 = 2
403 => 0|100 0000 0011| => 1027 - 1023 = 4
404 => 0|100 0000 0100| => 1028 - 1023 = 5

Set tambahan pertama

Angka kedua ( y) besarnya lebih kecil. Saat menambahkan dua angka ini untuk mendapatkan x + y, 2 bit terakhir dari angka kedua ( 01) digeser keluar dari jangkauan dan tidak termasuk dalam perhitungan.

Penambahan kedua menambah x + ydan zdan menambahkan dua angka dari skala yang sama.

Set tambahan kedua

Di sini, x + zterjadi dulu. Mereka memiliki skala yang sama, tetapi mereka menghasilkan angka yang lebih tinggi dalam skala:

404 => 0|100 0000 0100| => 1028 - 1023 = 5

Penambahan kedua menambahkan x + zdan y, dan sekarang 3 bit dijatuhkan dari yuntuk menambahkan angka ( 101). Di sini, harus ada putaran ke atas, karena hasilnya adalah angka floating point berikutnya: 4047866666666666untuk set tambahan pertama vs 4047866666666667untuk set tambahan kedua. Kesalahan itu cukup signifikan untuk ditampilkan dalam cetakan total.

Kesimpulannya, berhati-hatilah saat melakukan operasi matematika pada nomor IEEE. Beberapa representasi tidak tepat, dan mereka menjadi lebih tidak eksak ketika skalanya berbeda. Tambahkan dan kurangi angka dengan skala yang sama jika Anda bisa.

Jawaban Jon tentu saja benar. Dalam kasus Anda kesalahan tidak lebih besar dari kesalahan yang Anda akumulasikan dengan melakukan operasi floating point sederhana. Anda punya skenario di mana dalam satu kasus Anda mendapatkan kesalahan nol dan dalam kasus lain Anda mendapatkan kesalahan kecil; itu sebenarnya bukan skenario yang menarik. Pertanyaan yang bagus adalah: adakah skenario di mana mengubah urutan perhitungan berubah dari kesalahan kecil menjadi kesalahan relatif besar? Jawabannya jelas, ya.

Pertimbangkan misalnya:

x1 = (a - b) + (c - d) + (e - f) + (g - h);

vs.

x2 = (a + c + e + g) - (b + d + f + h);

vs.

x3 = a - b + c - d + e - f + g - h;

Jelas dalam aritmatika yang tepat mereka akan sama. Sangat menyenangkan untuk mencoba menemukan nilai untuk a, b, c, d, e, f, g, h sehingga nilai x1 dan x2 dan x3 berbeda dengan jumlah yang besar. Lihat apakah Anda dapat melakukannya!

Ini sebenarnya mencakup lebih dari sekadar Java dan Javascript, dan kemungkinan akan memengaruhi bahasa pemrograman apa pun menggunakan floats atau doubles.

Dalam memori, floating point menggunakan format khusus sepanjang garis IEEE 754 (konverter memberikan penjelasan yang jauh lebih baik daripada yang saya bisa).

Ngomong-ngomong, ini konverter float.

http://www.h-schmidt.net/FloatConverter/

Hal tentang urutan operasi adalah "kehalusan" operasi.

Baris pertama Anda menghasilkan 29,41 dari dua nilai pertama, yang memberi kita 2 ^ 4 sebagai eksponen.

Baris kedua Anda menghasilkan 41,17 yang memberi kita 2 ^ 5 sebagai eksponen.

Kami kehilangan angka yang signifikan dengan meningkatkan eksponen, yang kemungkinan akan mengubah hasilnya.

Cobalah mencentang bit terakhir pada ujung kanan dan kiri untuk 41.17 dan Anda dapat melihat bahwa sesuatu sebagai "tidak signifikan" seperti 1/2 ^ 23 eksponen akan cukup untuk menyebabkan perbedaan floating point ini.

Sunting: Bagi Anda yang ingat angka signifikan, ini akan termasuk dalam kategori itu. 10 ^ 4 + 4999 dengan angka signifikan 1 akan menjadi 10 ^ 4. Dalam hal ini, angka signifikan jauh lebih kecil, tetapi kita dapat melihat hasilnya dengan 0,00000000004 yang melekat padanya.

Angka floating point direpresentasikan menggunakan format IEEE 754, yang menyediakan ukuran bit spesifik untuk mantissa (secara signifikan). Sayangnya ini memberi Anda sejumlah 'blok pembangun fraksional' untuk dimainkan, dan nilai fraksional tertentu tidak dapat direpresentasikan secara tepat.

Apa yang terjadi dalam kasus Anda adalah bahwa dalam kasus kedua, penambahan mungkin berjalan ke beberapa masalah presisi karena urutan penambahan dievaluasi. Saya belum menghitung nilainya, tetapi bisa jadi misalnya bahwa 23,53 + 17,64 tidak dapat diwakili secara tepat, sedangkan 23,53 + 5,88 bisa.

Sayangnya itu adalah masalah yang diketahui yang harus Anda tangani.

Saya percaya itu ada hubungannya dengan urutan evaulasi. Sementara jumlah secara alami sama di dunia matematika, di dunia biner bukannya A + B + C = D, itu

A + B = E
E + C = D(1)

Jadi ada langkah sekunder di mana angka floating point bisa turun.

Ketika Anda mengubah urutan,

A + C = F
F + B = D(2)