Algoritma Euclid

Algoritma Euclid atau dalam bahasa Internasional dikenali dengan Eucladin's Algorithm merupakan suatu algoritma, atau kesatuan perintah yang terdiri dari simbol (setelah di terjemahkan secara simbolik) yang digunakan untuk menentukan faktor komplotan terbesar dari dua buah bilangan bulat. Secara historis algortima ini dikenal sebagai algoritma tertua di dunia. Algoritma ini sendiridikutip dari buku Element karya Euclid pada tahun sekitar 300 BC. Ketika mencari faktor komplotan terbesar (FPB) dari dua buah bilangan dengan menggunakan algoritma Euclid tidak diharapkan proses pemfaktoran.

Contoh Algoritma Euclid

Penerapan Algoritma Euclid

Sebagai referensi untuk mempermudah pemahaman pengunaan algoritma euclid diperlihatkan oleh referensi di bawah ini. Misalkan diberikan x dan y. Kita akan mencari FPB kedua bilangan tersebut. Lebih sederhananya dalam hal ini kita misalkan x = 1071 dan y = 1021. Demi lebih kerapian kita akan lebih menentukan menulis dalam bentuk tabel berikut ini.

x	y	sisa
1071	1029	42
1029	42	21
42	21	0

Secara umum klarifikasi dengan menggunakan formula ini mengunakan prinsip sebagai berikut. Pertama periksa apakah bilangan y nol atau tidak. Jika y yaitu nol maka a merupakan fpb. Jika tidak maka diulang lagi proses y, kalau sehabis x dibagi y lagi (penulisan dibuat dalam x modulus y). Karena y pada baris pertama bukanlah nol, maka bilanganyang lebih besar dibagi dengan bilangan kedua. Hasil yang diperoleh satu dan bersisa 42. Dalam hal ini biasanya akan ditulis dalam bentuk fungsi modulus. 1071= 1.1029 + 42. Usaha meningat cuilan yang ditebalkan, alasannya ini akan digunakan pada berikutya.

Sekarang kita lanjutkan pada baris ke-dua. Pembagi pada baris pertama (y1) akan mengisi cuilan x2. Sementara sisa pada baris pertama akan mengisi ruang pada pembagi (y2) pada baris kedua. Langkah selanjutnya akan dilakukan operasi pembagian yang sama.Pada baris ke dua dilakukan operasi yang sama. 1029 : 42 didapat sisa pembagian 21. Dalam fungsi modulus terbentuk 1029= 24.42+21. Sama dengan sebelumnya pembagi pada baris kedua akan menempati cuilan x3 dan sisa baris kedua akan menempati pembagi (y3)  pada baris ke 3.

Hal ini terus dilakukan hingga sisa pembagian nol. Pada dilema kali ini terlihat pada baris ketiga di sanggup pembagian 42: 21 bersisa nol. Ini akkirnya proses telah selesai. Maka pembagi tamat yang menyebabka sisa nol tersebut merupakan Faktor Persekutuan Terbesar yang kita cari. Keterangan dari fungsi modulus mempunyai bentuk umum Bilangan = (k)x(Pembagi) + Sisa. Jika diperhatikan fungsi modulus di atas maka angka yang berwarna biru yaitu pembagi dan berwarna merah yaitu sisa pembagian. Baca: Pra Sejarah Angka Nol.

Algortima Euclid dalam Bahasa Pemograman 

Dengan kecanggihan teknologi, serta perkembangan matematika yang terintegrasi dalam beberapa bahasa pemograman maka algoritma Euclid ini sanggup dibuat dalam bentuk program komputasi. Dengan mengunakan bahasa pemograman maka cukup dengan melaksanakan input bilangan yang akan dicari akan ditemukan pribadi FPB dari kedua bilangan tersebut. Berikut salah satu referensi code yang dikutip dari wikicode.

if b = 0return aelsereturn fpb(b, a modulus b);Penulisan fungsi dalam bentuk iteratif: function fpb(a, b)
while b ≠ 0
var t := b
b := a modulus b
a := t
return a
function fpb(a, b)
while a ≠ b
if a > b
a := a - b
else
b := b - a
return a 

Pembuktian kebenaran teori ini secara induktif sanggup dilakukan secara pemfaktoran. Sebagaimana referensi yang telah diberikan tadi, sanggup diambil angka 1071 dan  1029. Faktor dari 1071 = 3x3x7x17. Sementara penfaktoran 1029= 3x7x7x7. Terlihat terang faktor komplotan dari ke dua bilangan tersebut 37= 21. Baca: Sejarah Penemuan Algoritma.
Sumber http://www.marthamatika.com/

Share :