Anum Week 0

Introduction & Motivation

Motivasi menulis blog ini sebenarnya sederhana. Orang bilang mata kuliah ini susah. Dan setelah beberapa pertemuan sepertinya saya merasakannya. Saya tidak mengetahui mengapa demikian, tetapi saya merasa sulit saja. Itulah mengapa saya memutuskan untuk menuliskan apa yang saya ketahui dan dapatkan dari setiap lecture. Harapannya sih menulis blog ini sama saja seperti mengajar orang. Dengan metode ini harapannya saya mengetahui konsep mana yang belum saya mengerti secara penuh dan saya bisa mempelajari hal yang saya kurang kuasai.

Oh ya, maafkan saya jika bahasa yang saya gunakan kadang formal dan kadang tidak formal. Blog ini didesain untuk dikerjakan dengan cepat. Kemudian, ada bagian dimana saya menggunakan bahasa Inggris. Jadi bersiaplah untuk hal itu. Untuk alasannya sendiri saya tidak terlalu memikirkannya. Saya akan menulis pada bahasa Inggris jika pikiran saya menyuruh saya untuk menuliskannya.

Prerequisite

Ilmu yang sebaiknya anda ketahui sebelum membaca sisa dari blog ini adalah mengenai bagaimana komputer menyimpan sebuah angka. Materinya adalah Floating Number Representation jika anda ingin mengetahui lebih banyak.

Bits Are Finite

Perhatikan bahwa rumus untuk menghitung luas lingkaran adalah:

\[A=\pi r^2\]

Perhatikan bahwa pada rumus, kita hanya perlu meng-input nilai radius, dan kita dapatkan luas.

Permasalahan komputasi pada bagian ini ada 2, yaitu: kita hanya bisa menyimpan nilai $\pi$ secara terbatas dan bit kita terbatas.

Pi is Srrational

Kita hanya bisa menggunakan nilai $\pi$ secara finite. Apa maksudnya? Maksudnya adalah kita hanya bisa menggunakan 5, 10, ataupun 15 digit $\pi$ saja. Intinya adalah $\pi$ yang kita gunakan terbatas digitnya. Hal ini adalah karena bilangan $\pi$ adalah bilangan irasional. Artinya, digitnya tidak terbatas (infinite).

Our Bits Are Finite

Katakanlah kita ingin menggunakan 15 digit $\pi$. Kita kemudian perlu menyimpannya pada komputer kita untuk melakukan kalkulasi. Komputer menggunakan floating digit arithmetic. Saya harap anda sudah mengetahui hal tersebut. Jika tidak, intinya adalah komputer kita biasanya menggunakan 32 atau 64 bit untuk menyimpan sebuah angka. Angka yang disimpan bisa desimal (desimal disini berarti bilangan koma, bukan bilangan basis 10 ya), positif, atau negatif. Bilagan ini disimpan dengan scientific notation yang terlihat seperti: $2\times 2^{3}$.

Intinya adalah, karena kita hanya punya 32 atau 64 bit untuk menyimpan angka, kita tidak bisa menyimpan seluruh angka di alam semesta. Bayangkan saja kamu hanya punya 64 digit angka, tapi kamu disuruh menyimpan seluruh angka pada alam semesta. Ini tentu tidak bisa dilakukan!

Small Numbers vs Big Numbers

Jenis bilangan 32 bit atau 64 bit yang disimpan oleh komputer/laptop kita menggunakan standar IEEE. Masalah menarik yang muncul adalah bilangan besar pada komputer lebih sparse. Masalah sparse pada bilangan besar ini munculnya kira-kira seperti ini: jika kita sekarang sedang menyimpan angka 2 juta, jika kita ingin ke bilangan berikutnya, bilangan berikutnya bukanlah 2.000.001, melainkan bilangan 2.300.000. Hal ini adalah implikasi dari bit yang digunakan komputer kita terbatas.

Ketika kita menggunakan bilangan kecil, hal ini masih lebih dapat teratasi. Jump yang dilakukan oleh sebuah bilangan tidak terlalu jauh (ya iya lah, kita kan bekerja di bilangan kecil). Oleh karena itu, sebaiknya scale-lah bilangan yang sedang kamu kerjakan supaya dia tidak terlalu besar. Hal ini dapat meningkatkan akurasi dari komputasi numerik yang dilakukan.

Smallest Possible Number

Ada sebuah angka dimana dia sangat dekat dengan 0, tetapi bukan 0, yang menjadi sebuah treshold. Jika kurang dari treshold ini, maka bilangan tersebut langsung dibulatkan 0. Hal ini bisa dibuktikan dengan algoritma berikut:

x=1;
n=0;

while x>0:
        x=x/2;
        n=n+1;

print(x)
print(n)

Hal ini pada dasarnya perlu diingat jika bekerja dengan angka yang sangat mendekati 0. Untuk mengetahui lebih lanjut tentang masalah ini, silahkan baca soal machine epsilon di google.

Error Propagation

Cobalah menghitung bilangan ke 10 dari bilangan fib dengan algoritma dari geek for geek ini:

# Function for nth fibonacci number - Space Optimisation
# Taking 1st two fibonacci numbers as 0 and 1


def fibonacci(n):
	a = 0
	b = 1
	if n < 0:
		print("Incorrect input")
	elif n == 0:
		return a
	elif n == 1:
		return b
	else:
		for i in range(2, n+1):
			c = a + b
			a = b
			b = c
		return b

# Driver Program


print(fibonacci(10))

# This code is contributed by Saket Modi

Eksperimen 1

Tantangannya adalah cobalah hitung bilangan ke 10 dari barisan ini, tapi suku pertama dan kedua buatlah menjadi 0.1 dan 1.1. Hal ini mencerminkan error pada mesin kita. Coba lihat seberapa besar aplifikasi error yang dilakukan.

Eksperimen 2

Tantangannya sama, tapi suku pertama adalah 0.1 dan suku kedua adalah 0.9.

Eksperimen 3

Tantangannya sama, tapi suku pertama adalah -0.1 dan suku kedua adalah 1.1.

Eksperimen 4

Cobalah buat program yang sama di bahasa yang agak “primitif”. Gunakan java, c, c++, atau rust. Bandingkan hasilnya.

Kesimpulan Eksperimen

Intinya adalah jika initial value-nya ada masalah, komputasi yang dilakukan juga akan bermasalah.

Cancellation (Loss of Significant Digit)

Bagaimana jika kita ingin menghitung 1-cos(x) untuk x yang dekat dengan 0. Jika x dekat 0 maka cos(x) akan dekat dengan 1. Hal ini akan mengakibatkan 1-cos(x) akan dekat dengan 0. Ingat masalah kita tadi diatas? Ingat bahwa jika kita merepresentasikan bilangan yang terlalu dekat dengan 0, ada sebuah treshold dimana bilangan tersebut akan dibulatkan ke 0.

Permasalahan tersebut juga bisa dianalogikan dengan mengurangkan bilangan 0.12345678 dan 0.12345676 yang akan menghasilkan $0.2\times 10^{-7}$ dimana hanya ada 1 significant digit. Itulah mengapa permasalahan ini disebut Loss of Significant Digit.

Selain itu, masalah ini juga akan terjadi dengan persamaan quadrat dimana b»ac. Hal ini karena solusi persamaan kuardrat adalah sebagai berikut:

\[x_{1, 2}=\frac{-b\pm\sqrt{b^2-4ac}}{2a}\]

Perhatikan bahwa jika b»ac, maka b^2 akan jauh lebih besar dari ac. hal ini dapat membuat Loss of Significant Digit pada x dimana $-b$ ditambahkan dengan $\sqrt{b^2-4ac}$. Hal ini karena:

\[\sqrt{b^2-4ac}=\sqrt{b^2}=b\]

Hal tersebut kita bisa lakukan karena asumsi bahwa b»ac.