Blog Zainuddin Nafarin

Algoritma Euclidean adalah salah satu algoritma tercepat untuk menghitung FPB (Faktor Persekutuan terBesar) / GCD (Greatest Common Divisor). FPB dari 2 angka adalah angka terbesar yang habis membagi 2 angka tersebut. Prinsip dari algoritma Euclidean ini adalah dari kenyataan bahwa FPB dari 2 angka tidak akan berubah jika angka terbesar dikurangi angka terkecil. Sebagai contoh, 22 adalah FPB dari 198 dan 110 (198 = 22 x 9; 110 = 22 x 5), 198 – 110 = 88 dan 110 tetap mempunyai FPB 22. Proses ini bisa terus di-ulang sampai salah satu dari angka tersebut adalah 0, sehingga angka yang lainnya adalah FPB dari 2 angka paling awal. Jika dilihat langkah – langkahnya sampai selesai :

(198, 110) -> (110, 88) -> (88, 22) -> (22, 0)

Dapat juga dituliskan secara prosedural :
198 = 110 x 1 + 88
110 = 88 x 1 + 22
88 = 22 x 4 + 0

Berdasarkan prosedur di atas, sekarang akan dibuat implementasinya di 4 bahasa pemrograman (C/C++, Assembly, Pascal, dan BASIC). Implementasinya akan berbentuk fungsi FPB dengan input 2 bilangan bulat (integer) 32-bit, dan output juga integer. Berikut ini adalah kode-kode fungsi FPB algoritma Euclidean di 4 bahasa tersebut :

C/C++

int FPB(int a, int b)
{
    if (a < b)
       {int t = a; a = b; b = t;} // Tukar a dan b jika a < b

    int r = 0;

    do
    {
        r = a % b;
        a = b;
        b = r;
    } while (r); // Teruskan loop hanya jika r tidak 0 

    return a;
}

Assembly

FPB PROC
; Fungsi : FPB(a,b)
; Input  : (a,b) -> (eax, ebx)
; Output : FPB -> eax

	pushad              ; Simpan semua register
	cmp	eax, ebx    ; Bandingkan eax dan ebx
	ja	startloop   ; Jika  a > b, langsung ke startloop
	xchg    eax, ebx    ; Jika tidak, tukar isi eax dan ebx
startloop:
	xor	edx, edx    ; edx = 0
	div	ebx         ; eax / edx, sisanya akan disimpan di edx
	cmp	edx, 0      ; Bandingkan edx dan 0
	je	endloop     ; Jika edx = 0, hentikan loop ke endloop
	mov	eax, ebx    ; eax = ebx
	mov	ebx, edx    ; ebx = edx
	jmp	startloop   ; Mulai lagi loop
endloop:
	popad               ; Kembalikan semua register ke asal
	mov eax, ebx        ; Simpan nilai FPB di eax
	ret                 ; Kembali ke pemanggil

FPB ENDP

Pascal

Function FPB(a, b : Integer) : Integer;

Var t, r : Integer;

Begin
 If (a < b) Then
    Begin
      t := a; a := b; b := t
    End;

 Repeat
    r := a Mod b;
    a := b;
    b := r
 Until r = 0;

 FPB := a;
End;

BASIC

Function FPB(ByVal a As Long, ByVal b As Long) As Long

    Dim t As Long, r As Long

    If a < b Then t = a: a = b: b = t

    Do
        r = a Mod b
        a = b
        b = r
    Loop Until r = 0

    FPB = a

End Function