Algoritma Euklidean

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas
Langsung ke: navigasi, cari

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[sunting | sunting sumber]

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(ab). 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[sunting | sunting sumber]

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[sunting | sunting sumber]