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 :
(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++
01 | int FPB(int a, int b) |
02 | { |
03 | if (a < b) |
04 | {int t = a; a = b; b = t;} // Tukar a dan b jika a < b |
05 |
06 | int r = 0; |
07 |
08 | do |
09 | { |
10 | r = a % b; |
11 | a = b; |
12 | b = r; |
13 | } while (r); // Teruskan loop hanya jika r tidak 0 |
14 |
15 | return a; |
16 | } |
Assembly
01 | FPB PROC |
02 | ; Fungsi : FPB(a,b) |
03 | ; Input : (a,b) -> (eax, ebx) |
04 | ; Output : FPB -> eax |
05 |
06 | pushad ; Simpan semua register |
07 | cmp eax, ebx ; Bandingkan eax dan ebx |
08 | ja startloop ; Jika a > b, langsung ke startloop |
09 | xchg eax, ebx ; Jika tidak, tukar isi eax dan ebx |
10 | startloop: |
11 | xor edx, edx ; edx = 0 |
12 | div ebx ; eax / edx, sisanya akan disimpan di edx |
13 | cmp edx, 0 ; Bandingkan edx dan 0 |
14 | je endloop ; Jika edx = 0, hentikan loop ke endloop |
15 | mov eax, ebx ; eax = ebx |
16 | mov ebx, edx ; ebx = edx |
17 | jmp startloop ; Mulai lagi loop |
18 | endloop: |
19 | popad ; Kembalikan semua register ke asal |
20 | mov eax, ebx ; Simpan nilai FPB di eax |
21 | ret ; Kembali ke pemanggil |
22 |
23 | FPB ENDP |
Pascal
01 | Function FPB(a, b : Integer) : Integer; |
02 |
03 | Var t, r : Integer; |
04 |
05 | Begin |
06 | If (a < b) Then |
07 | Begin |
08 | t := a; a := b; b := t |
09 | End; |
10 |
11 | Repeat |
12 | r := a Mod b; |
13 | a := b; |
14 | b := r |
15 | Until r = 0; |
16 |
17 | FPB := a; |
18 | End; |
BASIC
01 | Function FPB(ByVal a As Long, ByVal b As Long) As Long |
02 |
03 | Dim t As Long, r As Long |
04 |
05 | If a < b Then t = a: a = b: b = t |
06 |
07 | Do |
08 | r = a Mod b |
09 | a = b |
10 | b = r |
11 | Loop Until r = 0 |
12 |
13 | FPB = a |
14 |
15 | End Function |
Posts
No Response to "Tips Menghitung FPB dengan Algoritma Euclidean"
Post a Comment
Link dead , link invalid , suggestions or criticism ?
Please explain or tell to us by leaving a comment bellow.