Approach To Design Greatest Common Divisor Circuits Based On Methodological Analysis And Valuate Most Efficient Computational Circuit

Abstract

In elementary arithmetic, the greatest common divisor is used to simplify expressions by reducing the size of numbers involved. Greatest common divisor (GCD) of given numbers is the largest number that divides all of the given numbers without leaving any remainder. This paper presents the hardware simulation of different methods employed to compute Greatest common divisor of any two numbers (8-bit binary) in simulator. For this purpose, four different methods were worked out, of which, three were dynamic implementations namely, Euclid's method, Divisibility Check Method, Dynamic modulo and one was static implementation, static modulo method. These algorithms were then compared for their space & time complexity. For Space complexity, number of different components, like basic gates, memory units, plexers, arithmetic operation units, etc. used were compared and for time complexity, clock pulses required were measured for a few set of numbers.