Algoritma Euclidean

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 : 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)

ax + by = \text {gcd}(a,b)

Perhatikan contoh soal diatas:
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

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 : 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.