Verilog GCD: Euclid's Algorithm in Hardware with Testbench

To compute the greatest common divisor (GCD) of two numbers in hardware, you apply Euclid's algorithm one step per clock cycle: either subtract the smaller value from the larger, or replace the pair (a, b) with (b, a mod b), until one value reaches zero or both are equal. The value left is the GCD. This post explains the algorithm, keeps the original 2008 Verilog example, explains why that code does not compile as written, and gives a corrected, synthesizable Verilog GCD with a self-checking testbench.

Key takeaways

• Euclid's algorithm rests on one identity: GCD(a, b) = GCD(b, a mod b), and GCD(a, 0) = a.
• The subtraction form, GCD(a, b) = GCD(a - b, b) for a > b, needs only a comparator and a subtractor, so it is the usual choice for small hardware.
• A synthesizable GCD is a small sequential circuit: two registers, a compare, a subtract and a start/done handshake. A while loop inside always @(*) is a simulation model, not hardware.
• The subtraction form can take many cycles (up to about max(a, b)); the modulo form takes far fewer steps but needs a divider.
• Always test the corner cases: a = 0, b = 0, a = b, and inputs in both orders.

Updated on 25th Jan 2022!! (Further updated in November 2026 with a corrected design, worked examples and FAQ.)

What is Euclid's algorithm?

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.

The identity holds because any number that divides both a and b also divides a - b, and therefore also divides a mod b (which is a minus a whole multiple of b). The set of common divisors never changes from one step to the next, while the numbers keep getting smaller, so the process must end. For more than two numbers, apply it pairwise: GCD(a, b, c) = GCD(GCD(a, b), c).

Worked example: modulo form

GCD(1071, 462), a classic textbook example:

Step	a	b	a mod b
1	1071	462	147 (1071 = 2 x 462 + 147)
2	462	147	21 (462 = 3 x 147 + 21)
3	147	21	0 (147 = 7 x 21)
4	21	0	stop, GCD = 21

Worked example: subtraction form

GCD(48, 18), one subtraction per step. This is exactly what the hardware below does, one row per clock cycle after the inputs are loaded:

Cycle after load	a	b	Action
1	48	18	a > b, so a = 48 - 18
2	30	18	a > b, so a = 30 - 18
3	12	18	b > a, so b = 18 - 12
4	12	6	a > b, so a = 12 - 6
5	6	6	a = b, so gcd = 6 and done = 1

The modulo form reaches the same answer in three steps (48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0). The difference grows quickly: GCD(1000, 1) takes 1,000 subtraction steps but only one modulo step.

The original Verilog example (2008, updated 2022)

Here's a basic example of 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. The expected results are 6 and 9.

Why the original module does not compile, and a corrected simulation model

The algorithm in the original is right, but the module has three problems that any Verilog compiler will report or that synthesis will reject:

1. It assigns to input ports. a and b are inputs (nets), and a procedural block cannot assign to a net.
2. It assigns a wire inside an always block. gcd is declared output wire; it must be output reg to be assigned procedurally.
3. The loop count depends on the data. A while loop whose number of iterations depends on input values cannot be unrolled into fixed gates, so synthesis tools reject it. The % operator would also build a large combinational divider.

The version below fixes the first two problems by working on local copies. It compiles and runs with the original testbench unchanged, but it is a behavioural model for simulation only:

// Behavioural GCD model: simulation only, not synthesizable
module gcd_calc (input  wire [31:0] a,
                 input  wire [31:0] b,
                 output reg  [31:0] gcd);
  reg [31:0] x, y, r;
  always @(*) begin
    x = a;
    y = b;
    while (y != 0) begin
      r = y;
      y = x % y;
      x = r;
    end
    gcd = x;
  end
endmodule

A synthesizable Verilog GCD (subtraction based)

Real hardware spreads the loop over clock cycles. The design below loads the operands on start, performs one compare-and-subtract per clock, and pulses done for one cycle when gcd is valid. It uses only a comparator and a subtractor, so it is small and fast to clock.

// Sequential GCD, subtraction form of Euclid's algorithm
module gcd_seq #(parameter W = 32) (
  input  wire         clk,
  input  wire         rst_n,   // active-low asynchronous reset
  input  wire         start,   // pulse high for one cycle to begin
  input  wire [W-1:0] a_in,
  input  wire [W-1:0] b_in,
  output reg  [W-1:0] gcd,
  output reg          done,    // one-cycle pulse when gcd is valid
  output wire         busy
);
  reg [W-1:0] a, b;
  reg         run;

  assign busy = run;

  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      a    <= {W{1'b0}};
      b    <= {W{1'b0}};
      gcd  <= {W{1'b0}};
      done <= 1'b0;
      run  <= 1'b0;
    end else begin
      done <= 1'b0;
      if (start && !run) begin
        a   <= a_in;
        b   <= b_in;
        run <= 1'b1;
      end else if (run) begin
        if (b == {W{1'b0}} || a == b) begin   // GCD(a,0) = a, GCD(a,a) = a
          gcd  <= a;
          done <= 1'b1;
          run  <= 1'b0;
        end else if (a == {W{1'b0}}) begin    // GCD(0,b) = b
          gcd  <= b;
          done <= 1'b1;
          run  <= 1'b0;
        end else if (a > b) begin
          a <= a - b;
        end else begin
          b <= b - a;
        end
      end
    end
  end
endmodule

How it handles the corner cases: GCD(0, 0) returns 0, GCD(0, 7) and GCD(7, 0) return 7, and equal inputs finish in one cycle. A zero can only appear at load time, because the circuit always subtracts the smaller value from the strictly larger one.

Self-checking testbench

The testbench drives inputs on the falling edge, waits for done, and compares the result with a reference function. Inputs for the random tests are kept below 1,000 so that the subtraction loop stays short.

`timescale 1ns/1ps
module gcd_seq_tb;
  reg         clk = 1'b0, rst_n = 1'b0, start = 1'b0;
  reg  [31:0] a_in = 0, b_in = 0;
  wire [31:0] gcd;
  wire        done, busy;
  integer     errors = 0, i;

  gcd_seq #(.W(32)) dut (.clk(clk), .rst_n(rst_n), .start(start),
                         .a_in(a_in), .b_in(b_in),
                         .gcd(gcd), .done(done), .busy(busy));

  always #5 clk = ~clk;

  function [31:0] ref_gcd(input [31:0] x0, input [31:0] y0);
    reg [31:0] x, y, t;
    begin
      x = x0; y = y0;
      while (y != 0) begin
        t = y; y = x % y; x = t;
      end
      ref_gcd = x;
    end
  endfunction

  task run_one(input [31:0] x, input [31:0] y);
    begin
      @(negedge clk); a_in = x; b_in = y; start = 1'b1;
      @(negedge clk); start = 1'b0;
      while (!done) @(negedge clk);
      if (gcd !== ref_gcd(x, y)) begin
        errors = errors + 1;
        $display("FAIL: GCD(%0d,%0d) got %0d, expected %0d", x, y, gcd, ref_gcd(x, y));
      end else
        $display("PASS: GCD(%0d,%0d) = %0d", x, y, gcd);
    end
  endtask

  initial begin
    #12 rst_n = 1'b1;
    run_one(48, 18);   run_one(18, 48);   run_one(1071, 462);
    run_one(17, 5);    run_one(12, 12);   run_one(0, 7);
    run_one(7, 0);     run_one(0, 0);
    for (i = 0; i < 50; i = i + 1)
      run_one({$random} % 1000, {$random} % 1000);
    if (errors == 0) $display("All tests passed");
    else             $display("%0d test(s) failed", errors);
    $finish;
  end
endmodule

You can run both files in any free simulator, for example Icarus Verilog or one of the tools in our list of free HDL simulators, or in the ModelSim PE Student Edition.

Subtraction or modulo: which to build?

Aspect	Subtraction form	Modulo form
Hardware per step	Comparator and subtractor	Divider (or a multi-cycle divide unit)
Steps for GCD(48, 18)	5	3
Worst case steps	About max(a, b), for example GCD(N, 1)	Logarithmic in the input size; consecutive Fibonacci numbers are the worst case
Clock speed	High, short critical path	Lower if the divide is done in one cycle
Typical use	Small inputs, area-limited designs, teaching	Wide inputs where latency matters

A third option is the binary GCD (Stein's algorithm), which replaces division with shifts and subtraction by using the rules GCD(2a, 2b) = 2 x GCD(a, b) and GCD(2a, b) = GCD(a, b) for odd b. It suits hardware well because shifts cost almost nothing.

Common mistakes to avoid

• Writing the loop in an always @(*) block and expecting it to synthesize. Data-dependent loops must become a state machine over clock cycles.
• Forgetting the zero cases. With the subtraction form, a zero input that is not handled makes the circuit subtract zero forever.
• Assigning to input ports or declaring a procedurally assigned output as wire.
• Sampling done and gcd on the same clock edge that updates them in the testbench, which creates a race. Sample on the opposite edge, as above.

Our post on common RTL coding mistakes and how to avoid them covers more of these traps. For another small design with a testbench, see the Verilog shift register with test bench. Definitions of Verilog and RTL are in The Semiconductor Hub glossary.

How interviewers extend this question

• Make it synthesizable and add a start/done handshake (the design above).
• What is the worst-case latency for W-bit inputs, and how would you bound it?
• Implement the binary GCD with shifts, or compute the least common multiple using LCM(a, b) = a x b / GCD(a, b).
• Pipeline it so that a new pair can be accepted every cycle.

Frequently asked questions

Is a while loop synthesizable in Verilog?

Only when the number of iterations is fixed at compile time so the tool can unroll it. A loop that runs until a data value reaches zero, as in GCD, is not synthesizable; write it as a sequential circuit instead.

How many clock cycles does the hardware GCD take?

For the subtraction design above, one cycle per subtraction plus one to finish: 5 cycles for GCD(48, 18). The worst case is roughly the larger input, for example GCD(1000, 1) needs about 1,000 cycles.

What is GCD(0, 0)?

By convention it is 0, and the design above returns 0. GCD(a, 0) is a for any a.

Can I compute GCD in a single clock cycle?

Only for narrow inputs, by fully unrolling a fixed number of steps into combinational logic. For 32-bit inputs this is large and slow, so a multi-cycle design is normal.