# Digital "Greatest Common Divisor (GCD)" - Euclid’s algorithm Updated on 25th Jan 2022!!

The Euclidean algorithm is a method for finding the greatest common divisor (GCD) of two or more integers. It works by repeatedly applying the formula GCD(a,b) = GCD(b, a mod b) until the remainder is 0. The GCD is then equal to the last non-zero remainder or the last b value. It is named after the Greek mathematician Euclid, who first described it over 2,000 years ago.

Here's a basic example of synthesizable Verilog code for finding the greatest common divisor (GCD) of two numbers using Euclid's algorithm:

module gcd_calc(input wire [31:0] a, input wire [31:0] b, output wire [31:0] gcd);

reg [31:0] temp;

always @(*) begin
temp = a;
while (b != 0) begin
temp = b;
b = a % b;
a = temp;
end
gcd = temp;
end

endmodule

here's a simple test bench that tests the gcd_calc module:

module gcd_calc_tb;

reg [31:0] a;
reg [31:0] b;
wire [31:0] gcd;

gcd_calc dut (a, b, gcd);

initial begin
a = 48;
b = 18;
#10 \$display("GCD of %d and %d is %d", a, b, gcd);

a = 123456789;
b = 987654321;
#10 \$display("GCD of %d and %d is %d", a, b, gcd);
end

endmodule

In this test bench, two pairs of numbers are tested, and their GCDs are displayed on the console after a delay of 10 simulation time units. The test bench sets the inputs a and b, and the gcd_calc module calculates the GCD and assigns it to the output wire gcd. The results are displayed using the \$display system task.

1. thanks for sharing this site. you can download lots of ebooks from here

http://feboook.blogspot.com

2. This will go into infinite loop, e.g. if a=0 and b=5

3. Please fix your code for a = 0, b = any number