GCD: Euclid dan Binary

Apa itu GCD??

GCD itu singkatan dari greatest common divisor.. Artinya bilangan terbesar yang dapat membagi dua bilangan atau beberapa bilangan. Istilah Indonesia yang lebih umum di telinga kita adalah FPB (Faktor Persekutuan Terbesar).. Di sini, sebaiknya kita terbiasa menggunakan istilah GCD, karena lebih internasional.

Contoh:
GCD (24,12)=12 (Artinya 12 merupakan bilangan terbesar yang membagi 24 dan 12)
GCD (24,9)= 3 (Artinya 3 merupakan bilangan terbesar yang membagi 24 dan 9)

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Cara menentukan GCD:
Banyak Cara yang bisa dilakukan untuk menentukan GCD:

1. Ubah ke bentuk perkalian bilangan prima berpangkat. Lalu pilih pangkat terendah.
__Contoh soal 1: Tentukan GCD (2520,2646)!
__Jawab:2520 = 2³ x 3² x 5 x 7
________2646 = 2 x 3³ x 7²
________Jadi, GCD (2520,2646) = 2 x 3² x7 = 126

2.

Mirip cara pertama, tapi gunakan tangga bersusun.. Bagi bilangan-bilangan dengan bilangan x (biasanya mulai dari prima terkecil hingga terbesar).. Tandai bilangan x jika x bisa membagi semua bilangan (misalnya dengan bintang). Ulangi pembagian hingga bilangan-bilangan yang dibagi sudah mencapai angka 1. Lalu, kalikan semua bilangan yang sudah ditandai. Hasil kalinya itulah GCD-nya.. Contoh soal 2: Tentukan GCD (9240,7150)! Jawab: Tanda bintang menunjukkan bahwa kedua bilangan habis dibagi.. Jadi, GCD (9240,7150)=2 x 5 x 11 = 110

3.	Gunakan Algoritma Euclidean Perhatikan penjelasan Algoritma Euclidean di bawah.

4. Gunakan Algoritma Stein (Binary GCD Algorithm)
__Lihat penjelasan di bawah.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Algoritma Euclidean (Euclidean Algorithm)

Algoritma ini merupakan algoritma tertua sepanjang sejarah. Algoritma ini disebarkan sejak 300 BC oleh Euclid dalam tulisannya berjudul Euclid's Element.

Algoritma ini khususnya berlaku untuk mencari GCD dari 2 bilangan, dan sangat cocok diterapkan dalam pemrograman komputer karena sifatnya yang dinamis (tidak perlu mencari bilangan prima lagi). Konsep algoritma ini: bilangan yang lebih besar (p) dibagi dengan bilangan yang lebih kecil (q). Jika tak bersisa, GCD-nya adalah q. Jika bersisa, lakukan perulangan lagi. Kali ini, q dibagi dengan r(sisa).. Lalu, lakukan terus perulangan pembagian hingga didapat sisanya 0. Maka, GCD-nya adalah bilangan terakhir yang menjadi remainder (sisa).

Contoh soal 3: Tentukan GCD (16524, 73756)!
Jawab:
73756 = 4 x 16524 + 7660
16524 = 2 x 7660 + 1204
7660 = 6 x 1204 + 436
1204 = 2 x 436 + 332
436 = 1 x 332 +104
332 = 3 x 104 + 20
104 = 5 x 20 + 4
20 = 5 x 4 + 0

Karena remainder terakhir adalah 0, maka GCD dari 16524 dan 73756 adalah remainder/sisa sebelumnya, yaitu 4.
GCD (16524, 73756) = 4.

Contoh soal 4: Tentukan GCD(1353,1716)!
Jawab:
1716 = 1 x 1353 + 363
1353 = 3 x 363 + 264
363 = 1 x 264 + 99
264 = 2 x 99 + 66
99 = 1 x 66+ 33
66 = 2 x 33 +0

Jadi, GCD (1353,1716) = 33.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Pengembangan Algoritma Euclidean
Algoritma Euclidean selain menemukan GCD, juga dapat menemukan integer x dan y dalam identitas Bezout (persamaan linear diophantine)

Perhatikan contoh soal ke-4:
Ambil persamaan terbawah ke-2:
33 = 99 - 66
33 = 99 - (264 - 2 x 99)
33 = 3 x 99 - 264
33 = 3 x (363 - 1 x 264) - 264
33 = 3 x 363 - 4 x 264
33 = 3 x 363 - 4 x (1353 - 3 x 363)
33 = 15 x 363 - 4 x 1353
33 = 15 x (1716 - 1353) - 4 x 1353
33 = 15 x 1716 - 19 x 1353 ________ ==> Nah inilah identitas Bezout yang dimaksud

Lihat persamaan diophantine yang di-post di blog ini untuk lebih jelasnya...

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Algoritma Stein (Binary GCD Algorithm)
Algoritma ini disebarkan oleh Josef Stein di Jerman tahun 1961.

Kelebihan: tidak memerlukan perhitungan yang kompleks dibanding algoritma Euclidean. Jadi, perkalian dan pembagian dalam algoritma euclidean diganti di sini. Dan, dibuktikan oleh Brigitte Vallée bahwa algoritma ini 60% lebih efisien dibanding rata-rata pemakaian algoritma Euclidean..
Kekurangan: tidak dapat dipakai sebagai identitas Bezout / persamaan diophantine linear.

Dalam algoritma ini dipakai identitas yang berulang sebagai berikut:

1. gcd(0, v) = v, karena bilangan apapun membagi 0 dan v adalah bilangan terbesar yang membagi v. Sama halnya, gcd(u, 0) = u. gcd(0, 0) tidak dapat didefinisikan.
   
2. Jika u and v keduanya genap, maka gcd(u, v) = 2·gcd(u/2, v/2), karena 2 adalah pembagi keduanya.
3. Jika u genap dan v ganjil, maka gcd(u, v) = gcd(u/2, v), karena 2 bukan pembagi keduanya. Sama halnya, jika u ganjil dan v genap, maka gcd(u, v) = gcd(u, v/2).
4. Jika u dan v keduanya ganjil, dan u ≥ v, maka gcd(u, v) = gcd((u−v)/2, v). Jika keduanya ganjil dan u < v, maka gcd(u, v) = gcd((v-u)/2, u). Ini merupakan kombinasi satu langkah dari algoritma Euclid, yang menggunakan pengurangan setiap langkah, dan sebuah aplikasi dari langkah 3. Pembagian oleh 2 menghasilkan sebuah integer karena perbedaan dari dua angka ganjil adalah genap.
5. Ulangi langkah 3–4 sampai u = v, (atau satu langkah lagi) sampai u = 0. Dalam kasus ini, hasilnya adalah 2^kv, di mana k adalah faktor dari 2 yang ditemukan di langkah 2.

Contoh soal 5: Tentukan GCD(1353,1716) menggunakan algoritma Stein!
Jawab:
gcd(1353,1716)=gcd(1353, 858)=gcd(1353,429)
=gcd(462,429)=gcd(231,429)=gcd(231,99)
=gcd(66,99) = gcd(33,99) = gcd(33,33)=gcd(33,0)=33.

Huahuahuahuahua..... ... Guammpang bangetzzzzzzzz... Gancilll.. Nah, sekarang, persiapkan diri kamu buat isenk-in temen... Siapa yang palink cepet menemukan GCD (atau biasa disebut FPB), maka ditraktir makan... huahuahuaaaa..