Algoritme Euklidean

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas
Loncat ke navigasi Loncat ke pencarian

Dalam matematika, algoritme Euklidean (juga disebut algoritme Euklid) adalah suatu algoritme untuk menentukan faktor persekutuan terbesar (FPB) dari dua bilangan bulat. Algoritme ini dinamai setelah matematikawan Yunani Euklides menuliskannya dalam Buku VII dan Buku X Elemen Euklides.

Algoritme Euklidean muncul dalam buku Elemen Euklides sekitar tahun 300 SM, menjadikannya salah satu algoritme numerik yang tertua dan masih digunakan secara luas.

Algoritme Euklidean tidak memerlukan faktorisasi.

Deskripsi algoritme[sunting | sunting sumber]

  1. Diberikan dua bilangan asli a dan b, periksa apakah b adalah nol.
  2. Jika ya, a adalah FPB. Jika tidak, ulangi langkah pertama dengan menggunakan b sebagai a yang baru dan sisa setelah a dibagi oleh b sebagai b yang aru.

Contoh[sunting | sunting sumber]

Sebagai contoh, FPB dari 1071 dan 1029 yang dihitung dengan menggunakan algoritme ini adalah 21, dengan langkah-langkah sebagai berikut:

a b sisa setelah a dibagi oleh b

1071 1029 42
1029 42 21
42 21 0
21 0

Dengan mencatat hasil bagi (yang merupakan bilangan bulat) selama menjalankan algoritme, kita juga dapat menentukan bilangan bulat p dan q di mana ap + bq = fpb(ab). Hal ini dikenal sebagai ekstensi algoritme Euklidean.

Bukti kebenaran[sunting | sunting sumber]

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.

Implementasi[sunting | sunting sumber]

Algoritme 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

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

Efisiensi algorritme[sunting | sunting sumber]

"Himpunan garis berwarna yang memancar dari titik nol sistem koordinat x-y. Setiap garis melambangkan sebuah himpunan pasangan bilangan yang memerlukan banyak langkah yang sama dalam algoritme Euklidean."
Grafik banyak langkah yang diperlukan algoritme Euklidean untuk mencari fpb(x,y). Titik-titik yang warnanya cerah (merah dan kuning) menandakan langkah yang dibutuhkan relatif sedikit, sedangkan warna yang gelap (violet dan biru) menunjukkan perlu banyak langkah. Daerah yang paling gelap ada di garis y = Φx, di mana Φ adalah rasio emas.

Efisiensi komputasional algoritme Euklid telah dipelajari secara menyeluruh.[1] Efisiensi ini bisa diartikan sebagai banyak langkah pembagian yang perlu dilakukan algoritme, dikali dengan harga komputasi setiap pembagian. Analisis tertua yang diketahui tentang algoritme Euklid berasal dari A. A. L. Reynaud pada tahun 1811,[2] yang menunjukkan bahwa banyak langkah pembagian yang dilakukan dengan masukan (u, v) tidak mungkin lebih dari v; dia kemudian memperbaiki batas ini menjadi v/2  + 2. Kemudian, pada tahun 1841, P. J. E. Finck menunjukkan[3] bahwa banyak langkah pembagian tidak mungkin lebih tinggi dari 2 log2 v + 1, dan artinya algoritme Euklid berjalan dalam waktu polinomial dari ukuran masukannya.[4] Émile Léger, pada tahun 1837, mempelajari kasus terburuknya, yaitu ketika masukannya adalah bilangan Fibonacci yang bersebelahan.[4] Analisis Finck kemudian diperbaiki oleh Gabriel Lamé pada tahun 1844,[5] yang menunjukkan bahwa banyak langkah yang diperlukan untuk menyelesaikan algoritme tidak pernah lebih dari lima kali banyak digit bilangan yang lebih kecil b.[6][7]

Penggunaan[sunting | sunting sumber]

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

Referensi[sunting | sunting sumber]

  1. ^ Knuth 1997, hlm. 339–364
  2. ^ Reynaud, A.-A.-L. (1811). Traité d'arithmétique à l'usage des élèves qui se destinent à l'École Polytechnique (edisi ke-6th). Paris: Courcier. Note 60, p. 34.  Dikutip oleh (Shallit 1994).
  3. ^ Finck, P.-J.-E. (1841). Traité élémentaire d'arithmétique à l'usage des candidats aux écoles spéciales (dalam bahasa Prancis). Derivaux. 
  4. ^ a b Shallit, J. (1994). "Origins of the analysis of the Euclidean algorithm". Historia Math. 21: 401–419. doi:10.1006/hmat.1994.1031. 
  5. ^ Lamé, G. (1844). "Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers". Comptes Rendus Acad. Sci. (dalam bahasa Prancis). 19: 867–870. 
  6. ^ Grossman, H. (1924). "On the Number of Divisions in Finding a G.C.D". The American Mathematical Monthly. 31 (9): 443. doi:10.2307/2298146. JSTOR 2298146. 
  7. ^ Honsberger, R. (1976). Mathematical Gems II. The Mathematical Association of America. hlm. 54–57. ISBN 0-88385-302-7. 

Bibliografi[sunting | sunting sumber]

Pranala luar[sunting | sunting sumber]