Algoritma Euklides

Algoritma Euklidean (juga disebut Algoritma Euklid) adalah suatu algoritma untuk menentukan faktor persekutuan terbesar (FPB) dari dua bilangan bulat. Algoritma ini adalah salah satu algoritma yang tertua, dan muncul dalam buku Elemen Euklid sekitar 300 SM. Algoritma ini 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 a

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