CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

A Comparison of Several Greatest Common Divisor(GCD)Algorithms

by Haroon Altarawneh
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 26 - Number 5
Year of Publication: 2011
Authors: Haroon Altarawneh
10.5120/3099-4253

Haroon Altarawneh . A Comparison of Several Greatest Common Divisor(GCD)Algorithms. International Journal of Computer Applications. 26, 5 ( July 2011), 24-31. DOI=10.5120/3099-4253

@article{ 10.5120/3099-4253,
author = { Haroon Altarawneh },
title = { A Comparison of Several Greatest Common Divisor(GCD)Algorithms },
journal = { International Journal of Computer Applications },
issue_date = { July 2011 },
volume = { 26 },
number = { 5 },
month = { July },
year = { 2011 },
issn = { 0975-8887 },
pages = { 24-31 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume26/number5/3099-4253/ },
doi = { 10.5120/3099-4253 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:12:00.719821+05:30
%A Haroon Altarawneh
%T A Comparison of Several Greatest Common Divisor(GCD)Algorithms
%J International Journal of Computer Applications
%@ 0975-8887
%V 26
%N 5
%P 24-31
%D 2011
%I Foundation of Computer Science (FCS), NY, USA
Abstract

This paper about Greater Common Divisor GCD, the paper shows that there is a lot of algorithms, some of these algorithm is good in timing and make low number of iteration, the other make a lot of iteration with a lot of time! But as we see in the analysis of the algorithms that some of the algorithms is faster than the others in small numbers (like Brute force is faster than Bishop Algorithm in the small numbers, but in the large numbers the Bishop Algorithm is too fast with comparison with the brute force) so the researchers recommend to develop the Bishop algorithm the make it more efficient in computing the GCD for small numbers. In the other hand the Dijkstra algorithm is too close in timing and number of iteration with the Bishop algorithm. But as we see in the analysis the best algorithm to use in computing the GCD in all type of integers is the Extended Euclidean algorithm which makes few loops with small or large numbers.

References
  1. Handbook of Applied Cryptography, by A. Menezes, P. van Oorschot, and S. Vanstone, CRC Press, 1996.
  2. eLiteral The Moving Constant available at http://services.eliteral.com/digital-certificate-mumbai/chap14.php
  3. Washington University, St. Louis available at http://www.cs.wustl.edu/~kjg/cs101/Notes/Recursion/recursion.html
  4. Centre for Information Security and Cryptography available at http://cisac.math.ucalgary.ca/news_events/hugh/talks/sorenson.pdf
  5. National Institute of Standards and Technology available at http://www.nist.gov/dads/
  6. Computer Science Ben Gurion University of the Negev available at http://www.cs.bgu.ac.il/~berend/teaching/Intro2CS/examples/main.html
Index Terms

Computer Science
Information Sciences

Keywords

Brute Force Algorithm Dijkstras Algorithm Extended Euclidean Algorithm Lehmers GCD Algorithm Bishops Method for GCD Fibonacci GCD's

Powered by PhDFocusTM