Random Articles
Reseach Article
Hardware Implementation of Greatest Common Divisor using subtractor in Euclid Algorithm
| 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
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
- 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.
- R. P. Brent, H. T. Kung, "A Systolic Algorithm for GCD Computation" Proc. 7th IEEE Symp. On Comp. Arith. , pp 118-125, 1985.
- M. J. Foster and H. T. Kung, "The Design of Special Purpose VLSI Chips" IEEE Computer , Vol. 13, pp. 26-40, Jan. 1980.
- B. Vallee "Dynamical analysis of a class of Euclidean Algorithms. " The Computer Science, 297(1-3):447-486, 2003.
- R. M. Corless, S. M. Watt, and L. Zhi QR factoring to compute the GCD of univariate approximate polynomials", 2003
- 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.
- P. Emeliyanenko. "Accelerating Symbolic Computations on NVIDIA Fermi". In GTC '10, 2010. Poster presentation.
- P. Emeliyanenko. "Modular Resultant Algorithm for Graphics Processors". In ICA3PP '10, pages 427– 440, Berlin, Heidelberg, 2010. Springer-Verlag.
- Haroon Altarawneh, A Comparison of Several Greatest Common Divisor (GCD) Algorithms,International Journal of Computer Applications (0975 ? 8887), Volume 26? No. 5, July2011.
- 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.
- Jonanthan Sorenson, Two fast GCD Algorithms, Journal Of Algorithms16,110-114(1994).
- Jeffrey Shallit and Jonathan Sorenson, ?nalysis Of Left-Shift GCD Binary Algorithm?, J. Symbolic Computation (1994) 17, 473-486.
Index Terms
Keywords