Dalam matematika, algoritma Euklidean (juga disebut algoritma Euklid) adalah suatu algoritma untuk menentukan faktor persekutuan terbesar (FPB) dari dua bilangan bulat. Algoritma ini dinamai setelah matematikawan Yunani Euklides menuliskannya dalam Buku VII dan Buku X Elemen Euklides.
Algoritma Euklidean muncul dalam buku Elemen Euklides sekitar tahun 300 SM, menjadikannya salah satu algoritma numerik yang tertua dan masih digunakan secara luas.
Algoritma Euklidean tidak memerlukan faktorisasi.
Algoritma dan implementasi
Diberikan dua bilangan asli a dan b, periksa apakah b adalah nol. Jika ya, a adalah FPB. Jika tidak, ulangi proses tadi menggunakan b dan sisa setelah a dibagi oleh b (ditulis sebagai a modulus b). Algoritma ini dapat dinyatakan dengan menggunakan rekursi kanan:
function fpb(a, b)
if b = 0
return a
else
return fpb(b, a modulus b);
Secara iteratif, fungsi ini dapat ditulis sebagai:
function fpb(a, b) while b ≠ 0 var t := b b := a modulus b a := t return aSebagai contoh, FPB dari 1071 dan 1029 yang dihitung dengan menggunakan algoritma ini adalah 21, dengan langkah-langkah sebagai berikut:
| a | b | t |
|
| 1071 | 1029 | 42 |
| 1029 | 42 | 21 |
| 42 | 21 | 0 |
| 21 | 0 |
Dengan mencatat hasil bagi (yang merupakan bilangan bulat) selama menjalankan algoritma, kita juga dapat menentukan bilangan bulat p dan q di mana ap + bq = fpb(a, b). Hal ini dikenal sebagai Ekstensi Algoritma Euklidean.
Algoritma ini dapat digunakan dalam konteks di mana pembagian bersisa memungkinkan. Ini termasuk polinomial cincin dalam suatu medan, juga cincin dari bilangan bulat Gaussian, dan dalam domain Euklidean umum.
Euklid pada mulanya merumuskan masalah ini secara geometri, sebagai masalah untuk mencari "satuan" yang dapat dipakai untuk panjang dari dua buah garis, dan algoritmanya berlangsung dengan mengulangi pengurangan dari sisi yang lebih pendek dari sisi yang lebih panjang. Implementasi ini sama dengan implementasi berikut ini, yang cukup tidak efisien dibandingkan dengan cara yang telah dijelaskan di atas:
function fpb(a, b) while a ≠ b if a > b a := a - b else b := b - a return a Bukti kebenaran
Tidaklah sulit untuk membuktikan bahwa algoritma itu benar. Misalkan a dan b adalah bilangan yang FPB-nya akan ditentukan. Dan misalkan sisa dari pembagian dari a oleh b adalah t. Maka a = qb + t di mana q adalah hasil bagi (yang merupakan bilangan bulat) dari pembagian tersebut. Sekarang, setiap pembagi dari a dan b juga dapat habis membagi t (karena t dapat ditulis sebagai t = a − qb); Dengan cara yang sama, setiap pembagi dari b dan t juga akan habis membagi a. Maka faktor persekutuan terbesar dari a dan b adalah sama dengan FPB dari b dan t. Oleh karena itu, kita cukup meneruskan proses tadi dengan b dan t saja. Karena t lebih kecil dalam nilai mutlak dari b, kita akan mencapai t = 0 setelah sejumlah langkah.
Pranala luar
- Euclid's Algorithm: Algorithm, generalization, game and related topics
- Binary Euclid's Algorithm (Java)
- Euclid's Game (Java)
Sumber :
m.andrafarm.com, wiki.gilland-ganesha.com, id.wikipedia.org, dsb.
