View source for 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|title=Poin yang sering terlewat|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 ==

{| class="wikitable"
! 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 <code>int</code>):

<pre>
200 * 300 * 400 * 500   =   -884.901.888
</pre>

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:

<pre>
(500 * 400) * (300 * 200)
((500 * 400) * 300) * 200
((200 * 500) * 300) * 400
400 * (200 * (300 * 500))
</pre>

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:

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

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|title=Dua penyakit yang berbeda|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''':

{| class="wikitable"
! !! 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|title=Relevansi ke quantization|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 ==

{| class="wikitable"
! 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 <code>-fwrapv</code> bila memang menginginkan perilaku membungkus, atau <code>-fsanitize=undefined</code> 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 <code>wrapping_mul</code>, <code>checked_mul</code>, <code>saturating_mul</code>, dan <code>overflowing_mul</code>. 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.
* '''<code>-ffast-math</code> 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 <code>-Ofast</code>.
* '''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 <code>printf("%d\n", 200*300*400*500);</code> lalu bandingkan dengan <code>printf("%f\n", (3.14+1e20)-1e20);</code>. 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.