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.