Analisis efisiensi pencarian greatest common divisor dengan metode euclidean algorithms, middle school procedure dan CIC
DOI:
https://doi.org/10.54593/jstekwid.v1i1.62Keywords:
Greatest Common Divisor, Efisiensi, Euclidean Algorithm, Consecutive Integer Checking (CIC), Middle School ProcedurAbstract
Permasalahan yang ada saat mencari GCD sangatlah beragam, untuk itu perlu diteliti metode mana yang efisiensinya paling tinggi untuk setiap masalah yang ada saat mencarinya. Efisiensi yang kita cari dilihat dari faktor pemakaian memori dan waktu dalam menjalankan algoritma tersebut. Dalam penelitian ini, digunakam tiga metode tersebut dalam mencari Greatest Common Divisor (GCD) yaitu Euclidean Algorithms, Consecutive Integer Checking (CIC) dan Middle School Procedure. Hasil penelitian menunjukkan bahwa metode Consecutive Integer Checking menggunakan waktu yang paling sedikit dibandingkan dua metode lainnya, tetapi metode ini menggunakan memori yang sangat banyak daripada metode lain sehingga metode ini tidak dapat dikatakan sebagai metode yang paling efisien. Metode Euclidean Algorithms adalah metode yang paling efektif karena tidak memerlukan waktu yang banyak dan memori yang digunakan juga sedikit.
References
Program to find GCD or HCF of two numbers. (2018, November22) .
Retrieved from https://www.geeksforgeeks.org/c-program-find- gcd-hcf-two-numbers/.
GargCheck, K. D., & Garg, K. D. (2019, June 24). Program to find GCD or HCF of two numbers using Middle School Procedure. Retrieved from https://www.geeksforgeeks.org/program-to-find- gcd-or-hcf-of-two-numbers-using-middle-school-procedure/.
Greatest Common Divisor. (n.d.). Retrieved from http://mathworld.wolfram.com/GreatestCommon Divisor.html.
Euclidean Algorithm. (n.d.). Retrieved from http://mathworld.wolfram.com/EuclideanAlgorit hm.html.
Berkaay. (n.d.). Middle school procedure for computing gcd m n Steps 1 Find prime factors of m2. Retrieved from https://www.coursehero.com/file/p7alqjp/Middle-school-procedure-for-computing-gcd-m-n- Steps-1-Find-prime-factors-of-m-2/.
Kid_Crown_Finch16. (n.d.). Methods for gcd mn Middle school procedure Step 1 Find the prime factorization : Course Hero. Retrieved from https://www.coursehero.com/file/p62g3oh/Meth ods-for-gcd-mn-Middle-school-procedure-Step- 1-Find-the-prime-factorization/.
Fitri Dwi Lestari - AMIK BSI Pontianak. (n.d.). Analisa Algoritma Faktor Persekutuan Terbesar (FPB) Menggunakan Bahasa Pemrograman C . etrieved from https://ejournal.bsi.ac.id/ejurnal/index.php/evolusi/article/view/1728/0.
Al-Haija, Q. A. (n.d.). Reviewing and Analyzing Efficient GCD/LCM Algorithms for Cryptographic Design. Retrieved from https://www.academia.edu/35267009/Reviewing_and_Analyzing_Efficient_GCD_LCM_Algorith ms_for_Cryptographic_Design.
Downloads
Published
Issue
Section
License
Copyright (c) 2022 Fenisa Lourence Br Tobing, Alex Chandra, Fenina Adline Twince Tobing, Rena Nainggolan, Prayogo
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
<p><a href="http://creativecommons.org/licenses/by-nc-sa/4.0/" rel="license"><img style="border-width: 0;" src="https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png" alt="Creative Commons License" /></a><br /><strong>Jurnal Sains dan Teknologi Widyaloka (JSTekWid)</strong> This work is licensed under a <a href="http://creativecommons.org/licenses/by-nc-sa/4.0/" rel="license">Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License</a>.</p>
