Algoritma Euklides

Dalam matematika, algoritma Euklides adalah suatu algoritme 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 Euklides muncul dalam buku Elemen Euklides sekitar tahun 300 SM, menjadikannya salah satu algoritma numerik yang tertua dan masih digunakan secara luas.

Algoritma Euklides tidak memerlukan faktorisasi.

 Deskripsi algoritma 
 Diberikan dua bilangan asli  dan , periksa apakah  adalah nol.
 Jika ya,  adalah FPB. Jika tidak, ulangi langkah pertama dengan menggunakan  sebagai  yang baru dan sisa setelah  dibagi oleh  sebagai  yang baru.

 Contoh 
Sebagai contoh, FPB dari 1071 dan 1029 yang dihitung dengan menggunakan algoritma 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 algoritma, kita juga dapat menentukan bilangan bulat p dan q di mana ap + bq = fpb(a, b). Hal ini dikenal sebagai perluasan algoritme Euklides.

 Bukti kebenaran 
Misalkan  dan  adalah bilangan yang FPB-nya akan ditentukan. Dan misalkan sisa dari pembagian dari  oleh  adalah . Maka  di mana  adalah hasil bagi (yang merupakan bilangan bulat) dari pembagian tersebut. Sekarang, setiap pembagi dari  dan  juga dapat habis membagi  (karena  dapat ditulis sebagai ). Dengan cara yang sama, setiap pembagi dari  dan  juga akan habis membagi . Maka faktor persekutuan terbesar dari  dan  adalah sama dengan FPB dari  dan . Oleh karena itu, kita cukup meneruskan proses tadi dengan  dan  saja. Karena  lebih kecil dalam nilai mutlak dari , kita akan mencapai setelah sejumlah langkah.

 Implementasi 
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

Euklides 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 algoritma

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

 Penggunaan 
Algoritma ini dapat digunakan dalam konteks di mana pembagian bersisa memungkinkan. Ini termasuk polinomial gelanggang dalam suatu medan, juga gelanggang dari bilangan bulat Gauss, dan dalam ranah Euklides umum.

 Referensi 

 Bibliografi 


 Pranala luar 


  Algoritma Euklides di cut-the-knot

 Binary Euclid's Algorithm (Java)
 Euclid's Game (Java)

Kategori:Matematika
Kategori:Euklides