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

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

Hardware Implementation of Greatest Common Divisor using subtractor in Euclid Algorithm

by Darshana Upadhyay, Harshit Patel
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 65 - Number 7
Year of Publication: 2013
Authors: Darshana Upadhyay, Harshit Patel
10.5120/10937-5888

Darshana Upadhyay, Harshit Patel . Hardware Implementation of Greatest Common Divisor using subtractor in Euclid Algorithm. International Journal of Computer Applications. 65, 7 ( March 2013), 24-28. DOI=10.5120/10937-5888

@article{ 10.5120/10937-5888,
author = { Darshana Upadhyay, Harshit Patel },
title = { Hardware Implementation of Greatest Common Divisor using subtractor in Euclid Algorithm },
journal = { International Journal of Computer Applications },
issue_date = { March 2013 },
volume = { 65 },
number = { 7 },
month = { March },
year = { 2013 },
issn = { 0975-8887 },
pages = { 24-28 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume65/number7/10937-5888/ },
doi = { 10.5120/10937-5888 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:18:09.597942+05:30
%A Darshana Upadhyay
%A Harshit Patel
%T Hardware Implementation of Greatest Common Divisor using subtractor in Euclid Algorithm
%J International Journal of Computer Applications
%@ 0975-8887
%V 65
%N 7
%P 24-28
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
Abstract

This paper proposed an efficient implementation of digital circuit based on the Euclidean Algorithm with modular arithmetic to find Greatest Common Divisor (GCD) of two Binary Numbers given as input to the circuit. Output of the circuit is the GCD of the given inputs. In this paper subtraction-based narrative defined by Euclid is described, the remainder calculation replaced by repeated subtraction. The selection of the Division Method using subtractor is due to ease of implementation and less complexity in connection with reduced hardware. The circuit is built using basic digital electronic components like Multiplexers & comparator (A

References
  1. M. Morris Mano "Digital Logic and Computer Design", Published by Pearson Education, Inc. and Dorling Kindersley Publishing Inc. , Printed in India by Gopsons Papers Ltd, 2011.
  2. R. P. Brent, H. T. Kung, "A Systolic Algorithm for GCD Computation" Proc. 7th IEEE Symp. On Comp. Arith. , pp 118-125, 1985.
  3. M. J. Foster and H. T. Kung, "The Design of Special Purpose VLSI Chips" IEEE Computer , Vol. 13, pp. 26-40, Jan. 1980.
  4. B. Vallee "Dynamical analysis of a class of Euclidean Algorithms. " The Computer Science, 297(1-3):447-486, 2003.
  5. R. M. Corless, S. M. Watt, and L. Zhi QR factoring to compute the GCD of univariate approximate polynomials", 2003
  6. P. Emeliyanenko. "A complete modular resultant algorithm targeted for realization on graphics hardware". In PASCO '10, pages 35–43, New York, NY, USA,2010. ACM.
  7. P. Emeliyanenko. "Accelerating Symbolic Computations on NVIDIA Fermi". In GTC '10, 2010. Poster presentation.
  8. P. Emeliyanenko. "Modular Resultant Algorithm for Graphics Processors". In ICA3PP '10, pages 427– 440, Berlin, Heidelberg, 2010. Springer-Verlag.
  9. Haroon Altarawneh, A Comparison of Several Greatest Common Divisor (GCD) Algorithms,International Journal of Computer Applications (0975 ? 8887), Volume 26? No. 5, July2011.
  10. T. Jebelean,Comparing Several GCD Algorithms " Che Wun Chiou, Fu Hua Chou , Yun-Chi Yeh , Speeding up Euclid's GCD algorithm with no magnitude comparisons? , International Journal of Information and Computer Security table of contents archive Volume 4 Issue 1, February 2010.
  11. Jonanthan Sorenson, Two fast GCD Algorithms, Journal Of Algorithms16,110-114(1994).
  12. Jeffrey Shallit and Jonathan Sorenson, ?nalysis Of Left-Shift GCD Binary Algorithm?, J. Symbolic Computation (1994) 17, 473-486.
Index Terms

Computer Science
Information Sciences

Keywords

Greatest Common Divisor Magnitude Comparator Multiplexer Full Subtractor Euclidean Algorithm

Powered by PhDFocusTM