Mengapa angka desimal tidak dapat direpresentasikan secara tepat dalam biner?

Ada beberapa pertanyaan yang diposting ke SO tentang representasi floating-point. Misalnya, angka desimal 0,1 tidak memiliki representasi biner yang tepat, sehingga berbahaya untuk menggunakan operator == untuk membandingkannya dengan angka titik-mengambang lainnya. Saya mengerti prinsip di balik representasi floating-point.

Yang tidak saya mengerti adalah mengapa, dari sudut pandang matematika, apakah angka di sebelah kanan titik desimal lebih "istimewa" daripada angka di sebelah kiri?

Misalnya, angka 61.0 memiliki representasi biner yang tepat karena bagian integral dari angka apa pun selalu tepat. Tetapi angka 6.10 tidak tepat. Yang saya lakukan adalah memindahkan desimal satu tempat dan tiba-tiba saya telah beralih dari Exactopia ke Inexactville. Secara matematis, seharusnya tidak ada perbedaan intrinsik antara kedua angka - mereka hanya angka.

Sebaliknya, jika saya memindahkan desimal satu tempat ke arah lain untuk menghasilkan angka 610, saya masih dalam Exactopia. Saya bisa terus ke arah itu (6100, 610000000, 610000000000000) dan mereka masih tepat, tepat, tepat. Tetapi begitu desimal melewati beberapa ambang batas, angkanya tidak lagi tepat.

Apa yang sedang terjadi?

Sunting: untuk memperjelas, saya ingin menjauh dari diskusi tentang representasi standar industri, seperti IEEE, dan tetap dengan apa yang saya yakini sebagai cara "murni" secara matematis. Dalam basis 10, nilai posisi adalah:

... 1000  100   10    1   1/10  1/100 ...

Dalam biner, mereka akan menjadi:

... 8    4    2    1    1/2  1/4  1/8 ...

Juga tidak ada batasan arbitrer untuk angka-angka ini. Posisi meningkat tanpa batas ke kiri dan ke kanan.

Angka desimal dapat direpresentasikan dengan tepat, jika Anda memiliki ruang yang cukup - tidak hanya dengan mengambang angka titik biner . Jika Anda menggunakan tipe titik desimal mengambang (mis System.Decimal. Dalam. NET), maka banyak nilai yang tidak dapat direpresentasikan secara tepat dalam floating point biner dapat direpresentasikan secara tepat.

Mari kita lihat dengan cara lain - di base 10 yang membuat Anda nyaman, Anda tidak bisa mengekspresikan 1/3 dengan tepat. Ini 0,3333333 ... (berulang). Alasan Anda tidak dapat mewakili 0,1 sebagai angka titik mengambang biner adalah untuk alasan yang persis sama. Anda dapat mewakili 3, dan 9, dan 27 persis - tetapi tidak 1/3, 1/9 atau 1/27.

Masalahnya adalah bahwa 3 adalah bilangan prima yang bukan merupakan faktor 10. Itu bukan masalah ketika Anda ingin mengalikan angka dengan 3: Anda selalu dapat mengalikan bilangan bulat tanpa mengalami masalah. Tetapi ketika Anda membagi dengan angka yang prima dan bukan merupakan faktor basis Anda, Anda dapat mengalami masalah (dan akan melakukannya jika Anda mencoba untuk membagi 1 dengan angka itu).

Meskipun 0,1 biasanya digunakan sebagai contoh paling sederhana dari angka desimal yang tepat yang tidak dapat direpresentasikan secara tepat dalam titik mengambang biner, bisa dibilang 0,2 adalah contoh yang lebih sederhana karena 1/5 - dan 5 adalah bilangan prima yang menyebabkan masalah antara desimal dan biner .

Catatan tambahan untuk menangani masalah representasi terbatas:

Beberapa tipe titik desimal mengambang memiliki ukuran tetap seperti yang System.Decimallainnya java.math.BigDecimal"berukuran besar" - tetapi mereka akan mencapai batas di beberapa titik, apakah itu memori sistem atau ukuran maksimum teoritis suatu array. Namun, ini adalah poin yang sepenuhnya terpisah dengan jawaban utama dari jawaban ini. Bahkan jika Anda memiliki jumlah bit yang benar-benar sewenang-wenang untuk dimainkan, Anda masih tidak bisa mewakili 0,1 desimal persis dalam representasi titik biner mengambang. Bandingkan dengan yang sebaliknya: diberi angka desimal angka acak, Anda dapat dengan tepat menunjukkan angka apa pun yang secara tepat dapat direpresentasikan sebagai titik biner mengambang.

Misalnya, angka 61.0 memiliki representasi biner yang tepat karena bagian integral dari angka apa pun selalu tepat. Tetapi angka 6.10 tidak tepat. Yang saya lakukan adalah memindahkan desimal satu tempat dan tiba-tiba saya telah beralih dari Exactopia ke Inexactville. Secara matematis, seharusnya tidak ada perbedaan intrinsik antara kedua angka - mereka hanya angka .

Mari kita menjauh sejenak dari rincian pangkalan 10 dan 2. Mari kita bertanya - di pangkalan b, angka apa yang telah mengakhiri representasi, dan angka apa yang tidak? Pikiran sesaat memberi tahu kita bahwa angka xmemiliki brepresentasi- terminating jika dan hanya jika ada bilangan bulat nsehingga x b^nmerupakan bilangan bulat.

Jadi, misalnya, x = 11/500memiliki 10-representasi terminating, karena kita dapat memilih n = 3dan kemudian x b^n = 22, integer. Namun x = 1/3tidak, karena apa pun yang nkita pilih kita tidak akan dapat menyingkirkan 3.

Contoh kedua ini mendorong kita untuk berpikir tentang faktor-faktor, dan kita dapat melihat bahwa untuk setiap rasional x = p/q (diasumsikan dalam istilah terendah), kita dapat menjawab pertanyaan dengan membandingkan faktor-faktor utama bdan q. Jika qada faktor prima yang tidak termasuk dalam faktor utama b, kami tidak akan pernah dapat menemukan yang cocok nuntuk menyingkirkan faktor-faktor ini.

Jadi untuk basis 10, di mana pun memiliki faktor utama selain 2 atau 5 tidak akan memiliki representasi terminating.p/qq

Jadi sekarang kembali ke pangkalan 10 dan 2, kita melihat bahwa setiap rasional dengan 10-representasi terminasi akan menjadi bentuk p/qpersis ketika qhanya memiliki 2dan 5s dalam factorisation utamanya; dan nomor yang sama akan memiliki 2-perwakilan terminating tepat ketika qhanya memiliki 2faktorisasi utama.

Tetapi salah satu dari kasus ini adalah bagian dari yang lain! Kapanpun

qhanya ada 2di factorisation utamanya

jelas juga benar itu

qhanya 2s dan 5s dalam factorisation utamanya

atau, dengan kata lain, setiap kali p/qmemiliki 2-representasi p/qterminasi , memiliki 10-representasi terminasi . Namun sebaliknya tidak berlaku - setiap kali qmemiliki 5 di factorisation utamanya, ia akan memiliki 10-representasi terminasi, tetapi bukan 2-representasi terminating. Ini adalah0.1 contoh yang disebutkan oleh jawaban lain.

Jadi di sana kami memiliki jawaban untuk pertanyaan Anda - karena faktor prima dari 2 adalah subset dari faktor prima dari 10, semua angka 2-terminating adalah 10-terminating number, tetapi tidak sebaliknya.Ini bukan tentang 61 lawan 6.1 - ini tentang 10 lawan 2.

Sebagai catatan penutup, jika oleh beberapa orang unik menggunakan (katakanlah) basis 17 tetapi komputer kami menggunakan basis 5, intuisi Anda tidak akan pernah disesatkan oleh ini - tidak akan ada nomor (non-nol, non-integer) yang diakhiri dalam kedua kasus!

Akar (matematika) alasannya adalah bahwa ketika Anda berurusan dengan bilangan bulat, mereka dianggap tak terhingga .

Yang berarti, meskipun jumlahnya tidak terbatas, kita dapat "menghitung" semua item dalam urutan, tanpa melewatkannya. Itu berarti jika kita ingin mendapatkan item di610000000000000 posisi ke-5 dalam daftar, kita dapat mengetahuinya melalui rumus.

Namun, bilangan real tidak terhingga jumlahnya . Anda tidak dapat mengatakan "beri saya nomor sebenarnya di posisi 610000000000000" dan dapatkan kembali jawaban. Alasannya adalah karena, bahkan antara 0dan1 , ada sejumlah nilai yang tak terbatas, ketika Anda mempertimbangkan nilai floating-point. Hal yang sama berlaku untuk setiap dua angka floating point.

Info lebih lanjut:

http://en.wikipedia.org/wiki/Countable_set

http://en.wikipedia.org/wiki/Uncountable_set

Pembaruan: Permintaan maaf saya, sepertinya saya salah menafsirkan pertanyaan. Tanggapan saya adalah mengapa kami tidak dapat mewakili setiap nilai nyata , saya tidak menyadari bahwa floating point secara otomatis diklasifikasikan sebagai rasional.

Untuk mengulangi apa yang saya katakan dalam komentar saya kepada Tn. Skeet: kita dapat mewakili 1/3, 1/9, 1/27, atau rasional dalam notasi desimal. Kami melakukannya dengan menambahkan simbol tambahan. Misalnya, garis di atas angka yang berulang dalam ekspansi desimal angka. Apa yang kita perlukan untuk mewakili angka desimal sebagai urutan angka biner adalah 1) urutan angka biner, 2) titik radix, dan 3) beberapa simbol lain untuk menunjukkan bagian berulang dari urutan.

Notasi kutipan Hehner adalah cara untuk melakukan ini. Dia menggunakan simbol kutipan untuk mewakili bagian berulang dari urutan. Artikel: http://www.cs.toronto.edu/~hehner/ratno.pdf dan entri Wikipedia: http://en.wikipedia.org/wiki/Quote_notation .

Tidak ada yang mengatakan kita tidak bisa menambahkan simbol ke sistem representasi kita, jadi kita dapat mewakili rasional desimal persis menggunakan notasi tanda kutip biner, dan sebaliknya.

BCD - Binary-coded Decimal - representasi adalah tepat. Mereka tidak sangat hemat ruang, tapi itu adalah kompromi yang harus Anda lakukan untuk akurasi dalam kasus ini.

Itu alasan yang sama Anda tidak bisa mewakili 1/3 persis di basis 10, Anda perlu mengatakan 0,33333 (3). Dalam biner itu adalah jenis masalah yang sama tetapi hanya terjadi untuk rangkaian angka yang berbeda.

(Catatan: Saya akan menambahkan 'b' untuk menunjukkan angka biner di sini. Semua angka lainnya diberikan dalam desimal)

Salah satu cara untuk memikirkan hal-hal adalah dalam hal sesuatu seperti notasi ilmiah. Kami terbiasa melihat angka yang dinyatakan dalam notasi ilmiah seperti, 6.022141 * 10 ^ 23. Angka-angka floating point disimpan secara internal menggunakan format yang sama - mantissa dan eksponen, tetapi menggunakan kekuatan dua bukan sepuluh.

61.0 Anda dapat ditulis ulang sebagai 1.90625 * 2 ^ 5, atau 1.11101b * 2 ^ 101b dengan mantissa dan eksponen. Untuk mengalikannya dengan sepuluh dan (memindahkan titik desimal), kita dapat melakukan:

(1.90625 * 2 ^ 5) * (1.25 * 2 ^ 3) = (2.3828125 * 2 ^ 8) = (1.19140625 * 2 ^ 9)

atau dengan mantissa dan eksponen dalam biner:

(1.11101b * 2 ^ 101b) * (1.01b * 2 ^ 11b) = (10.0110001b * 2 ^ 1000b) = (1,00110001b * 2 ^ 1001b)

Perhatikan apa yang kami lakukan di sana untuk mengalikan angka. Kami mengalikan mantisa dan menambahkan eksponen. Kemudian, karena mantissa berakhir lebih dari dua, kami menormalkan hasilnya dengan menabrak eksponen. Ini seperti ketika kita menyesuaikan eksponen setelah melakukan operasi pada angka dalam notasi desimal ilmiah. Dalam setiap kasus, nilai-nilai yang kami kerjakan memiliki representasi terbatas dalam biner, dan nilai-nilai yang dihasilkan oleh operasi perkalian dan penambahan dasar juga menghasilkan nilai-nilai dengan representasi terbatas.

Sekarang, pertimbangkan bagaimana kita akan membagi 61 dengan 10. Kita akan mulai dengan membagi mantra, 1.90625 dan 1.25. Dalam desimal, ini menghasilkan 1,525, angka pendek yang bagus. Tapi apa ini jika kita mengubahnya menjadi biner? Kami akan melakukannya dengan cara biasa - mengurangkan kekuatan terbesar dari dua bila memungkinkan, seperti mengubah desimal bilangan bulat menjadi biner, tetapi kami akan menggunakan kekuatan negatif dua:

1.525 - 1 * 2 ^ 0 -> 1
0,525 - 1 * 2 ^ -1 -> 1
0,025 - 0 * 2 ^ -2 -> 0
0,025 - 0 * 2 ^ -3 -> 0
0,025 - 0 * 2 ^ -4 -> 0
0,025 - 0 * 2 ^ -5 -> 0
0,025 - 1 * 2 ^ -6 -> 1
0,009375 - 1 * 2 ^ -7 -> 1
0,0015625 - 0 * 2 ^ -8 -> 0
0,0015625 - 0 * 2 ^ -9 -> 0
0,0015625 - 1 * 2 ^ -10 -> 1
0,0005859375 - 1 * 2 ^ -11 -> 1
0,00009765625 ...

Uh oh. Sekarang kita dalam masalah. Ternyata 1.90625 / 1.25 = 1.525, adalah pecahan berulang ketika dinyatakan dalam biner: 1.11101b / 1.01b = 1.10000110011 ... b Mesin kami hanya memiliki begitu banyak bit untuk menahan mantissa itu dan karenanya mereka hanya akan membulatkan fraksi dan menganggap nol melebihi titik tertentu. Kesalahan yang Anda lihat ketika Anda membagi 61 dengan 10 adalah perbedaan antara:

1.100001100110011001100110011001100110011 ... b * 2 ^ 10b
dan, katakan:
1.1000011001100110011001100110b * 2 ^ 10b

Pembulatan mantissa inilah yang menyebabkan hilangnya presisi yang kami kaitkan dengan nilai floating point. Bahkan ketika mantissa dapat diekspresikan dengan tepat (misalnya, ketika hanya menambahkan dua angka), kita masih bisa mendapatkan kerugian numerik jika mantissa membutuhkan terlalu banyak digit agar pas setelah menormalkan eksponen.

Kami benar-benar melakukan hal semacam ini sepanjang waktu ketika kami membulatkan angka desimal ke ukuran yang dapat dikelola dan hanya memberikan beberapa digit pertama saja. Karena kami menyatakan hasilnya dalam desimal, rasanya alami. Tetapi jika kita membulatkan desimal dan mengubahnya menjadi basis yang berbeda, itu akan terlihat sama jeleknya dengan desimal yang kita dapatkan karena pembulatan titik mengambang.

Ini pertanyaan yang bagus.

Semua pertanyaan Anda didasarkan pada "bagaimana kami mewakili angka?"

SEMUA angka dapat direpresentasikan dengan representasi desimal atau dengan representasi biner (komplemen 2). Mereka semua !!

TETAPI beberapa (kebanyakan dari mereka) membutuhkan elemen dalam jumlah tak terbatas ("0" atau "1" untuk posisi biner, atau "0", "1" hingga "9" untuk representasi desimal).

Seperti 1/3 dalam representasi desimal (1/3 = 0,3333333 ... <- dengan jumlah tak terbatas "3")

Seperti 0,1 dalam biner (0,1 = 0,00011001100110011 .... <- dengan jumlah tak terbatas "0011")

Semuanya ada dalam konsep itu. Karena komputer Anda hanya dapat mempertimbangkan kumpulan angka terbatas (desimal atau biner), hanya beberapa angka yang dapat direpresentasikan dengan tepat di komputer Anda ...

Dan seperti kata Jon, 3 adalah bilangan prima yang bukan merupakan faktor dari 10, sehingga 1/3 tidak dapat diwakili dengan terbatas jumlah elemen dalam basis 10.

Bahkan dengan aritmatika dengan presisi sewenang-wenang, sistem posisi penomoran dalam basis 2 tidak dapat sepenuhnya menggambarkan 6.1, meskipun dapat mewakili 61.

Untuk 6.1, kita harus menggunakan representasi lain (seperti representasi desimal, atau IEEE 854 yang memungkinkan basis 2 atau basis 10 untuk representasi nilai floating-point)

Jika Anda membuat angka yang cukup besar dengan floating point (karena dapat melakukan eksponen), maka Anda akan berakhir dengan ketidak eksaktanan di depan titik desimal juga. Jadi saya tidak berpikir pertanyaan Anda sepenuhnya valid karena premisnya salah; itu bukan kasus yang bergeser dengan 10 akan selalu menciptakan lebih presisi, karena pada titik tertentu nomor floating point harus menggunakan eksponen untuk mewakili besarnya angka dan akan kehilangan beberapa presisi dengan cara itu juga.

Saya terkejut belum ada yang menyatakan ini: gunakan pecahan lanjutan . Bilangan rasional apa pun dapat direpresentasikan secara biner dengan cara ini.

Beberapa contoh:

1/3 (0.3333 ...)

0; 3

5/9 (0,5555 ...)

0; 1, 1, 4

10/43 (0.232558139534883720930 ...)

0; 4, 3, 3

9093/18478 (0.49209871198181621387596060179673 ...)

0; 2, 31, 7, 8, 5

Dari sini, ada berbagai cara yang diketahui untuk menyimpan urutan bilangan bulat dalam memori.

Selain menyimpan nomor Anda dengan akurasi sempurna, fraksi lanjutan juga memiliki beberapa manfaat lain, seperti perkiraan rasional terbaik. Jika Anda memutuskan untuk mengakhiri urutan angka dalam fraksi lanjutan lebih awal, digit yang tersisa (ketika digabungkan kembali ke fraksi) akan memberi Anda fraksi terbaik. Ini adalah bagaimana perkiraan untuk pi ditemukan:

Fraksi lanjutan Pi:

3; 7, 15, 1, 292 ...

Mengakhiri urutan di 1, ini memberikan fraksi:

355/113

yang merupakan pendekatan rasional yang sangat baik.

Dalam persamaan

2^x = y ;  
x = log(y) / log(2)

Oleh karena itu, saya hanya ingin tahu apakah kita dapat memiliki sistem basis logaritmik untuk biner seperti,

 2^1, 2^0, 2^(log(1/2) / log(2)), 2^(log(1/4) / log(2)), 2^(log(1/8) / log(2)),2^(log(1/16) / log(2)) ........

Itu mungkin bisa menyelesaikan masalah, jadi jika Anda ingin menulis sesuatu seperti 32,41 dalam biner, itu mungkin

2^5 + 2^(log(0.4) / log(2)) + 2^(log(0.01) / log(2))

Atau

2^5 + 2^(log(0.41) / log(2))

Masalahnya adalah Anda tidak benar-benar tahu apakah angka itu sebenarnya 61.0. Pertimbangkan ini:

float a = 60;
float b = 0.1;
float c = a + b * 10;

Berapa nilai c? Ini bukan 61, karena b tidak benar-benar .1 karena .1 tidak memiliki representasi biner yang tepat.

Ada ambang karena arti digit telah berubah dari integer ke non-integer. Untuk mewakili 61, Anda memiliki 6 * 10 ^ 1 + 1 * 10 ^ 0; 10 ^ 1 dan 10 ^ 0 keduanya bilangan bulat. 6.1 adalah 6 * 10 ^ 0 + 1 * 10 ^ -1, tetapi 10 ^ -1 adalah 1/10, yang jelas bukan bilangan bulat. Begitulah cara Anda berakhir di Inexactville.

Paralel dapat dibuat dari pecahan dan bilangan bulat. Beberapa fraksi misalnya 1/7 tidak dapat direpresentasikan dalam bentuk desimal tanpa banyak dan banyak desimal. Karena floating point berbasis biner, kasus khusus berubah tetapi masalah akurasinya sama.

Ada jumlah bilangan rasional tak terhingga, dan jumlah bit terbatas untuk mewakili mereka. Lihat http://en.wikipedia.org/wiki/Floating_point#Accuracy_problems .

Angka 61.0 memang memiliki operasi floating-point yang tepat — tetapi itu tidak berlaku untuk semua bilangan bulat. Jika Anda menulis loop yang menambahkan satu ke angka floating point presisi ganda dan integer 64-bit, pada akhirnya Anda akan mencapai titik di mana integer 64-bit mewakili angka dengan sempurna, tetapi floating point tidak— karena tidak ada bit yang cukup signifikan.

Jauh lebih mudah untuk mencapai titik perkiraan di sisi kanan titik desimal. Jika Anda mulai menuliskan semua angka dalam floating point biner, itu akan lebih masuk akal.

Cara lain untuk memikirkannya adalah ketika Anda mencatat bahwa 61.0 benar-benar dapat diwakili di basis 10, dan menggeser titik desimal tidak mengubah itu, Anda melakukan penggandaan dengan kekuatan sepuluh (10 ^ 1, 10 ^ -1 ). Dalam floating point, mengalikan dengan kekuatan dua tidak mempengaruhi ketepatan angka. Coba ambil 61.0 dan bagikan dengan tiga berulang kali untuk ilustrasi bagaimana angka yang sangat tepat bisa kehilangan representasi yang tepat.

Anda tahu angka integer bukan? setiap bit mewakili 2 ^ n

2 ^ 4 = 16
2 ^ 3 = 8
2 ^ 2 = 4
2 ^ 1 = 2
2 ^ 0 = 1

baik itu sama untuk floating point (dengan beberapa perbedaan) tetapi bit mewakili 2 ^ -n 2 ^ -1 = 1/2 = 0,5
2 ^ -2 = 1 / (2 * 2) = 0,25
2 ^ -3 = 0,125
2 ^ -4 = 0,0625

Representasi biner titik mengambang:

menandatangani Fraksi Eksponen (saya pikir 1 tak terlihat ditambahkan ke fraksi)
B11 B10 B9 B8 B7 B6 B5 B5 B3 B3 B1 B0 B0

Jawaban skor tinggi di atas berhasil.

Pertama Anda mencampur basis 2 dan basis 10 dalam pertanyaan Anda, lalu ketika Anda meletakkan angka di sisi kanan yang tidak dapat dibagi ke dalam basis Anda mendapatkan masalah. Seperti 1/3 dalam desimal karena 3 tidak masuk ke dalam kekuatan 10 atau 1/5 dalam biner yang tidak masuk ke dalam kekuatan 2.

Komentar lain meskipun TIDAK PERNAH menggunakan sama dengan angka floating point, titik. Bahkan jika itu adalah representasi yang tepat ada beberapa angka dalam beberapa sistem floating point yang dapat secara akurat diwakili dalam lebih dari satu cara (IEEE buruk tentang hal ini, itu adalah spec floating point yang mengerikan untuk memulai, jadi harap sakit kepala). Tidak berbeda di sini 1/3 tidak EQUAL dengan angka pada kalkulator Anda 0,3333333, tidak peduli berapa banyak angka 3 di sebelah kanan titik desimal. Itu atau bisa cukup dekat tetapi tidak sama. jadi Anda akan mengharapkan sesuatu seperti 2 * 1/3 tidak sama dengan 2/3 tergantung pada pembulatan. Jangan pernah gunakan sama dengan floating point.

Seperti yang telah kita bahas, dalam aritmatika titik apung, desimal 0,1 tidak dapat direpresentasikan dengan sempurna dalam biner.

Representasi titik mengambang dan bilangan bulat menyediakan kisi atau kisi untuk angka yang diwakili. Ketika aritmatika dilakukan, hasilnya jatuh dari grid dan harus dimasukkan kembali ke grid dengan pembulatan. Contohnya adalah 1/10 pada kotak biner.

Jika kita menggunakan representasi desimal berkode biner seperti yang disarankan seorang pria, apakah kita dapat menyimpan angka di kotak?