CS:APP 2 Intro

Kenapa biner

Komputer modern menyimpan dan memproses informasi yang direpresentasikan sebagai sinyal bernilai dua. Digit biner sederhana inilah — bit — yang jadi dasar revolusi digital.

Sedikit sejarah desimal

Notasi desimal (basis 10) sudah dipakai lebih dari 1.000 tahun:

dikembangkan di India
disempurnakan matematikawan Arab pada abad ke-12
dibawa ke Barat pada abad ke-13 oleh matematikawan Italia Leonardo Pisano (ca. 1170–1250), yang lebih dikenal sebagai Fibonacci

Notasi desimal terasa alami untuk manusia yang berjari sepuluh. Tapi nilai biner bekerja lebih baik untuk membangun mesin yang menyimpan dan memproses informasi.

Kenapa dua nilai lebih mudah dibuat

Sinyal bernilai dua gampang direpresentasikan, disimpan, dan ditransmisikan. Contoh dari buku:

ada atau tidak adanya lubang pada kartu berlubang
tegangan tinggi atau rendah pada sebuah kawat
domain magnetik yang berorientasi searah atau berlawanan jarum jam

Rangkaian elektronik untuk menyimpan dan menghitung sinyal bernilai dua sangat sederhana dan andal. Karena itulah produsen bisa mengintegrasikan jutaan bahkan miliaran rangkaian semacam itu ke satu keping silikon.

Catatan: Biner dipilih bukan karena lebih "benar" secara matematis, tapi karena lebih gampang dibikin dan lebih tahan derau. Membedakan dua level tegangan jauh lebih andal daripada membedakan sepuluh level. Ini keputusan rekayasa, bukan keputusan matematika.

Bit sendirian tidak berguna

Sebuah bit tunggal, berdiri sendiri, tidak banyak gunanya. Kekuatannya baru muncul ketika kita:

mengelompokkan bit, lalu
menerapkan suatu penafsiran yang memberi makna pada pola-pola bit yang mungkin

Dengan dua langkah itu, kita bisa merepresentasikan elemen dari himpunan berhingga apa pun. Misalnya sistem bilangan biner untuk mengkodekan bilangan tak-negatif, atau kode karakter standar untuk mengkodekan huruf dan simbol.

Perhatikan bahwa maknanya tidak ada di dalam bit itu sendiri — makna datang dari penafsiran yang kita tempelkan. Pola bit yang sama persis bisa berarti bilangan, huruf, atau instruksi, tergantung cara kita membacanya.

Tiga representasi bilangan

Representasi	Dasar	Untuk apa
Unsigned	Notasi biner tradisional	Bilangan lebih besar atau sama dengan 0
Two's-complement	—	Cara paling umum merepresentasikan integer bertanda (positif maupun negatif)
Floating-point	Versi basis 2 dari notasi ilmiah	Bilangan real (secara aproksimasi)

Komputer mengimplementasikan operasi aritmetika seperti penjumlahan dan perkalian pada ketiga representasi ini, mirip dengan operasi yang bersesuaian pada integer dan bilangan real.

Overflow dan kejutannya

Representasi komputer memakai jumlah bit yang terbatas, sehingga sebagian operasi bisa overflow ketika hasilnya terlalu besar untuk direpresentasikan. Ini bisa memberi hasil yang mengejutkan.

Contoh integer

Di kebanyakan komputer sekarang (yang memakai representasi 32-bit untuk tipe int):

200 * 300 * 400 * 500   =   -884.901.888

Perkalian sekumpulan bilangan positif menghasilkan bilangan negatif. Ini bertentangan dengan sifat aritmetika integer yang kita kenal.

Tapi konsisten

Meski begitu, aritmetika integer komputer tetap memenuhi banyak sifat aritmetika integer sejati. Perkalian tetap asosiatif dan komutatif, sehingga semua ekspresi berikut menghasilkan angka yang sama, −884.901.888:

(500 * 400) * (300 * 200)
((500 * 400) * 300) * 200
((200 * 500) * 300) * 400
400 * (200 * (300 * 500))

Kalimat penutup bukunya pantas dikutip: komputer mungkin tidak menghasilkan hasil yang diharapkan, tapi setidaknya konsisten.

Floating point punya penyakit yang berbeda

Aritmetika floating-point punya sifat matematis yang sama sekali berbeda.

Hasil kali sekumpulan bilangan positif selalu positif — meski overflow akan menghasilkan nilai khusus +∞.
Tapi aritmetika floating-point tidak asosiatif, akibat presisi representasinya yang terbatas.

Contoh dari buku:

(3.14 + 1e20) - 1e20   ->   0.0     di kebanyakan mesin
3.14 + (1e20 - 1e20)   ->   3.14

Cuma letak kurungnya yang dipindah, hasilnya berbeda total. Penyebabnya: saat 3.14 dijumlahkan ke 1e20, nilainya terlalu kecil untuk memengaruhi digit-digit signifikan yang tersedia, sehingga hilang dibulatkan.

⚠️

Warning
Integer bisa memberi hasil salah tapi konsisten — urutan operasi tidak mengubah apa pun. Floating point memberi hasil hampir benar tapi bergantung urutan. Jangan menyamakan strategi menghadapi keduanya.

Akar dari semua perbedaan itu

Sifat matematis integer dan floating-point berbeda karena cara keduanya menangani keterbatasan representasinya:

	Rentang	Ketepatan
Integer	relatif kecil	presisi (tepat)
Floating-point	luas	hanya aproksimasi

Satu kalimat ini adalah inti seluruh Bab 2. Semua keanehan di sisa bab — overflow, pembulatan, kehilangan presisi — adalah konsekuensi dari trade-off ini.

Catatan: Trade-off rentang lawan presisi inilah keputusan inti setiap kali memilih format numerik untuk inferensi model. fp32 punya rentang luas dan presisi memadai tapi mahal; fp16 mempersempit rentang; bf16 mempertahankan rentang fp32 tapi memangkas presisi; int8 membuang rentang dinamis sepenuhnya demi ketepatan pada skala tetap. Semuanya adalah titik-titik berbeda pada tabel di atas.

Kenapa ini penting dipelajari

Buku menyebut beberapa alasan:

Kebenaran program. Memahami rentang nilai yang bisa direpresentasikan dan sifat operasinya penting untuk menulis program yang bekerja benar pada seluruh rentang nilai numerik.
Portabilitas. Agar program tetap benar di berbagai kombinasi mesin, operating system, dan compiler.
Keamanan. Sejumlah kerentanan keamanan komputer muncul dari kehalusan aritmetika komputer. Dulu bug program cuma merepotkan orang saat kebetulan terpicu; sekarang ada banyak sekali penyerang yang mencoba mengeksploitasi bug apa pun untuk mendapat akses tak sah ke sistem orang lain. Ini menaruh kewajiban lebih tinggi pada programmer untuk memahami cara programnya bekerja dan cara program itu bisa dibuat berperilaku tidak diinginkan.
Prasyarat Bab 3. Representasi ini harus dikenal sebelum masuk pemrograman tingkat mesin.
Memahami output compiler. Buku menurunkan beberapa cara melakukan operasi aritmetika dengan langsung memanipulasi representasi tingkat bit. Teknik ini penting untuk memahami kode tingkat mesin yang dihasilkan compiler saat berusaha mengoptimalkan evaluasi ekspresi aritmetika.

Pendekatan buku

Pembahasan bab ini berbasis seperangkat prinsip matematis inti. Alurnya:

mulai dari definisi dasar encoding
turunkan sifat-sifatnya: rentang bilangan yang bisa direpresentasikan, representasi tingkat bit-nya, dan sifat operasi aritmetika

Buku sengaja memakai sudut pandang abstrak ini, karena programmer perlu punya pemahaman jelas tentang bagaimana aritmetika komputer berhubungan dengan aritmetika integer dan real yang lebih familiar.

Catatan tentang bahasa lain

Bahasa	Hubungannya
C++	Dibangun di atas C, memakai representasi dan operasi numerik yang persis sama. Semua yang dikatakan tentang C di bab ini berlaku juga untuk C++.
Java	Membuat seperangkat standar baru. Standar C dirancang untuk memungkinkan rentang implementasi yang luas, sedangkan standar Java sangat spesifik soal format dan encoding data.

Catatan untuk kerja systems

"Konsisten" itu benar di level hardware, tapi bukan jaminan di level bahasa C. Standar C menyatakan overflow pada integer bertanda sebagai undefined behavior, sehingga compiler boleh mengasumsikan hal itu tidak pernah terjadi dan mengoptimalkan berdasarkan asumsi itu. Overflow pada integer tak bertanda terdefinisi dan membungkus (wrap). Gunakan -fwrapv bila memang menginginkan perilaku membungkus, atau -fsanitize=undefined untuk mendeteksinya saat pengujian.
Rust memilih sikap berbeda. Overflow integer memicu panic pada build debug dan membungkus pada build release. Kalau perilakunya ingin eksplisit, tersedia wrapping_mul, checked_mul, saturating_mul, dan overflowing_mul. Pilihan eksplisit ini menghilangkan seluruh kelas ambiguitas yang ada di C.
Non-asosiativitas floating point punya konsekuensi langsung pada komputasi paralel. Reduksi penjumlahan yang dipecah ke sejumlah thread menjumlahkan dalam urutan berbeda, sehingga hasilnya bisa berbeda saat jumlah thread diubah. Inilah sebabnya hasil pelatihan model bisa tidak reproducible antar konfigurasi, dan sebabnya ada mode reduksi deterministik di banyak pustaka.
-ffast-math mengizinkan compiler menganggap floating point asosiatif. Itu memang membuka peluang vektorisasi dan penyusunan ulang, tapi sekaligus melanggar jaminan IEEE 754. Berguna untuk sebagian beban kerja, berbahaya untuk kode numerik yang sensitif — dan keputusan ini sebaiknya diambil sadar, bukan diwarisi dari -Ofast.
Overflow integer adalah pintu masuk klasik kerentanan keamanan. Pola paling umum: menghitung ukuran buffer lewat perkalian, hasilnya overflow menjadi angka kecil, alokasi jadi terlalu kecil, lalu penulisan berikutnya meluber. Ini persis "kehalusan aritmetika komputer" yang disinggung buku.

Tip: Cara cepat membuktikan sendiri contoh di atas: kompilasi program kecil berisi printf("%d\n", 200*300*400*500); lalu bandingkan dengan printf("%f\n", (3.14+1e20)-1e20);. Dua baris itu meringkas seluruh pengantar bab ini.

Istilah kunci

Bit: Digit biner; sinyal bernilai dua yang jadi dasar penyimpanan dan pemrosesan informasi.
Encoding: Penafsiran yang diterapkan pada sekelompok bit sehingga pola bit punya makna.
Unsigned encoding: Representasi berbasis notasi biner tradisional untuk bilangan tak-negatif.
Two's-complement encoding: Cara paling umum merepresentasikan integer bertanda.
Floating-point encoding: Versi basis 2 dari notasi ilmiah untuk merepresentasikan bilangan real secara aproksimasi.
Overflow: Keadaan ketika hasil operasi terlalu besar untuk direpresentasikan oleh jumlah bit yang tersedia.