GCD in Verilog: Euclidean Algorithm FSM with Code
The greatest common divisor (GCD) of two integers is the largest number that divides both exactly. In hardware it is a classic finite-state-machine (FSM) exercise because the Euclidean algorithm needs no divider at all — just comparison and subtraction. This page gives you working, simulator-verified gcd verilog code you can drop into a testbench and extend.
We build two versions: a subtraction-based Euclidean FSM with a clean start/done handshake, and a binary (Stein) GCD that replaces the slow repeated-subtraction loop with cheap shifts. Both self-check their results against a reference GCD computed inside the testbench, so a real bug would print a FAIL line.
This is the most idiomatic hardware GCD: a three-state FSM that loads a and b on start, then repeatedly subtracts the smaller operand from the larger until the two are equal. The testbench drives ten operand pairs — including coprime pairs, equal inputs, and the gcd(x,0)=x edge case — and checks every result against a software Euclid loop.
module gcd_sub #(parameter W=16) (
input clk,
input rst_n,
input start,
input [W-1:0] a_in,
input [W-1:0] b_in,
output reg [W-1:0] gcd,
output reg done
);
localparam S_IDLE = 2'd0, S_CALC = 2'd1, S_DONE = 2'd2;
reg [1:0] state;
reg [W-1:0] a, b;
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
state <= S_IDLE; a <= 0; b <= 0; gcd <= 0; done <= 1'b0;
end else begin
case (state)
S_IDLE: begin
done <= 1'b0;
if (start) begin
a <= a_in; b <= b_in;
state <= S_CALC;
end
end
S_CALC: begin
if (a == b) begin
gcd <= a; done <= 1'b1; state <= S_DONE;
end else if (b == 0) begin
gcd <= a; done <= 1'b1; state <= S_DONE;
end else if (a == 0) begin
gcd <= b; done <= 1'b1; state <= S_DONE;
end else if (a > b) begin
a <= a - b;
end else begin
b <= b - a;
end
end
S_DONE: begin
done <= 1'b0;
state <= S_IDLE;
end
default: state <= S_IDLE;
endcase
end
end
endmodule
module tb;
localparam W=16;
reg clk, rst_n, start;
reg [W-1:0] a_in, b_in;
wire [W-1:0] gcd;
wire done;
integer i, errors;
reg [W-1:0] ta, tb, ref_g, x, y, t;
gcd_sub #(.W(W)) dut (.clk(clk), .rst_n(rst_n), .start(start),
.a_in(a_in), .b_in(b_in), .gcd(gcd), .done(done));
always #5 clk = ~clk;
// reference euclid (software)
task ref_gcd;
input [W-1:0] pa, pb;
output [W-1:0] r;
begin
x = pa; y = pb;
while (y != 0) begin
t = x % y; x = y; y = t;
end
r = x;
end
endtask
task run_case;
input [W-1:0] pa, pb;
begin
@(negedge clk); a_in = pa; b_in = pb; start = 1'b1;
@(negedge clk); start = 1'b0;
wait (done == 1'b1);
ref_gcd(pa, pb, ref_g);
if (gcd !== ref_g) begin
errors = errors + 1;
$display("FAIL gcd(%0d,%0d)=%0d expected %0d", pa, pb, gcd, ref_g);
end else begin
$display("PASS gcd(%0d,%0d)=%0d", pa, pb, gcd);
end
@(negedge clk);
end
endtask
initial begin
clk = 0; start = 0; a_in = 0; b_in = 0; errors = 0;
rst_n = 0; repeat (2) @(negedge clk); rst_n = 1;
run_case(48, 18); // 6
run_case(17, 5); // 1 coprime
run_case(1071, 462); // 21
run_case(36, 0); // 36 -> gcd(x,0)=x
run_case(0, 24); // 24
run_case(100, 100); // 100 equal
run_case(13, 13); // 13
run_case(1, 1); // 1
run_case(270, 192); // 6
run_case(65535, 255);// 255
if (errors == 0) $display("ALL TESTS PASSED");
else $display("TESTS FAILED: %0d", errors);
$finish;
end
endmodule
PASS gcd(48,18)=6 PASS gcd(17,5)=1 PASS gcd(1071,462)=21 PASS gcd(36,0)=36 PASS gcd(0,24)=24 PASS gcd(100,100)=100 PASS gcd(13,13)=13 PASS gcd(1,1)=1 PASS gcd(270,192)=6 PASS gcd(65535,255)=255 ALL TESTS PASSEDThe log shows a
PASSline for each of the ten operand pairs, where the FSM output matches the reference GCD computed by the testbench's own modulo-based Euclid loop. Cases such asgcd(17,5)=1(coprime),gcd(36,0)=36(zero operand) andgcd(65535,255)=255confirm the corner cases, and the finalALL TESTS PASSEDproves no case diverged from the golden model.Repeated subtraction is slow when one operand is much larger than the other —
gcd(65535,1)would take 65534 subtraction steps. The binary (Stein) algorithm fixes this by pulling out common factors of two with shifts and halving even operands, so each loop iteration removes at least one bit. This example sweeps every pair in 1..40 against the reference to prove equivalence.module gcd_bin #(parameter W=16) ( input clk, input rst_n, input start, input [W-1:0] a_in, input [W-1:0] b_in, output reg [W-1:0] gcd, output reg done ); localparam S_IDLE=3'd0, S_INIT=3'd1, S_LOOP=3'd2, S_DONE=3'd3; reg [2:0] state; reg [W-1:0] u, v; reg [4:0] shift; // common power-of-two factor, enough for W up to 31 always @(posedge clk or negedge rst_n) begin if (!rst_n) begin state <= S_IDLE; u <= 0; v <= 0; shift <= 0; gcd <= 0; done <= 1'b0; end else begin case (state) S_IDLE: begin done <= 1'b0; if (start) begin u <= a_in; v <= b_in; shift <= 0; state <= S_INIT; end end S_INIT: begin // handle zero operands: gcd(x,0)=x if (v == 0) begin gcd <= u; done <= 1'b1; state <= S_DONE; end else if (u == 0) begin gcd <= v; done <= 1'b1; state <= S_DONE; end // strip common factors of two else if (!u[0] && !v[0]) begin u <= u >> 1; v <= v >> 1; shift <= shift + 1'b1; end else begin state <= S_LOOP; end end S_LOOP: begin if (!u[0]) begin u <= u >> 1; // u even, v odd -> remove 2 from u end else if (!v[0]) begin v <= v >> 1; // v even, u odd -> remove 2 from v end else if (u == v) begin gcd <= u << shift; done <= 1'b1; state <= S_DONE; end else if (u > v) begin u <= (u - v) >> 1; // both odd, u>v end else begin v <= (v - u) >> 1; // both odd, v>u end end S_DONE: begin done <= 1'b0; state <= S_IDLE; end default: state <= S_IDLE; endcase end end endmodule module tb; localparam W=16; reg clk, rst_n, start; reg [W-1:0] a_in, b_in; wire [W-1:0] gcd; wire done; integer errors, i, j; reg [W-1:0] ref_g, x, y, t; gcd_bin #(.W(W)) dut (.clk(clk), .rst_n(rst_n), .start(start), .a_in(a_in), .b_in(b_in), .gcd(gcd), .done(done)); always #5 clk = ~clk; task ref_gcd; input [W-1:0] pa, pb; output [W-1:0] r; begin x = pa; y = pb; while (y != 0) begin t = x % y; x = y; y = t; end r = x; end endtask task run_case; input [W-1:0] pa, pb; begin @(negedge clk); a_in = pa; b_in = pb; start = 1'b1; @(negedge clk); start = 1'b0; wait (done == 1'b1); ref_gcd(pa, pb, ref_g); if (gcd !== ref_g) begin errors = errors + 1; $display("FAIL gcd(%0d,%0d)=%0d expected %0d", pa, pb, gcd, ref_g); end else begin $display("PASS gcd(%0d,%0d)=%0d", pa, pb, gcd); end @(negedge clk); end endtask initial begin clk = 0; start = 0; a_in = 0; b_in = 0; errors = 0; rst_n = 0; repeat (2) @(negedge clk); rst_n = 1; // directed corner cases run_case(48, 18); run_case(17, 5); run_case(1024, 768); // powers-of-two heavy -> 256 run_case(36, 0); run_case(0, 24); run_case(1, 1); // exhaustive-ish sweep of small pairs vs reference for (i = 1; i <= 40; i = i + 1) for (j = 1; j <= 40; j = j + 1) run_case(i[W-1:0], j[W-1:0]); if (errors == 0) $display("ALL TESTS PASSED"); else $display("TESTS FAILED: %0d", errors); $finish; end endmodulePASS gcd(48,18)=6 PASS gcd(17,5)=1 PASS gcd(1024,768)=256 PASS gcd(36,0)=36 PASS gcd(0,24)=24 PASS gcd(1,1)=1 PASS gcd(1,1)=1 PASS gcd(1,2)=1 PASS gcd(1,3)=1 PASS gcd(1,4)=1 PASS gcd(1,5)=1 PASS gcd(1,6)=1 PASS gcd(1,7)=1 PASS gcd(1,8)=1 PASS gcd(1,9)=1 PASS gcd(1,10)=1 PASS gcd(1,11)=1 PASS gcd(1,12)=1 PASS gcd(1,13)=1 PASS gcd(1,14)=1 PASS gcd(1,15)=1 PASS gcd(1,16)=1 PASS gcd(1,17)=1 PASS gcd(1,18)=1 PASS gcd(1,19)=1 PASS gcd(1,20)=1 PASS gcd(1,21)=1 PASS gcd(1,22)=1 PASS gcd(1,23)=1 PASS gcd(1,24)=1 PASS gcd(1,25)=1 PASS gcd(1,26)=1 PASS gcd(1,27)=1 PASS gcd(1,28)=1 PASS gcd(1,29)=1 PASS gcd(1,30)=1 PASS gcd(1,31)=1 PASS gcd(1,32)=1 PASS gcd(1,33)=1 PASS gcd(1,34)=1 PASS gcd(1,35)=1 PASS gcd(1,36)=1 PASS gcd(1,37)=1 PASS gcd(1,38)=1 PASS gcd(1,39)=1 PASS gcd(1,40)=1 PASS gcd(2,1)=1 PASS gcd(2,2)=2 PASS gcd(2,3)=1 PASS gcd(2,4)=2 PASS gcd(2,5)=1 PASS gcd(2,6)=2 PASS gcd(2,7)=1 PASS gcd(2,8)=2 PASS gcd(2,9)=1 PASS gcd(2,10)=2 PASS gcd(2,11)=1 PASS gcd(2,12)=2 PASS gcd(2,13)=1 PASS gcd(2,14)=2 PASS gcd(2,15)=1 PASS gcd(2,16)=2 PASS gcd(2,17)=1 PASS gcd(2,18)=2 PASS gcd(2,19)=1 PASS gcd(2,20)=2 PASS gcd(2,21)=1 PASS gcd(2,22)=2 PASS gcd(2,23)=1 PASS gcd(2,24)=2 PASS gcd(2,25)=1 PASS gcd(2,26)=2 PASS gcd(2,27)=1 PASS gcd(2,28)=2 PASS gcd(2,29)=1 PASS gcd(2,30)=2 PASS gcd(2,31)=1 PASS gcd(2,32)=2 PASS gcd(2,33)=1 PASS gcd(2,34)=2 PASS gcd(2,35)=1 PASS gcd(2,36)=2 PASS gcd(2,37)=1 PASS gcd(2,38)=2 PASS gcd(2,39)=1 PASS gcd(2,40)=2 PASS gcd(3,1)=1 PASS gcd(3,2)=1 PASS gcd(3,3)=3 PASS gcd(3,4)=1 PASS gcd(3,5)=1 PASS gcd(3,6)=3 PASS gcd(3,7)=1 PASS gcd(3,8)=1 PASS gcd(3,9)=3 PASS gcd(3,10)=1 PASS gcd(3,11)=1 PASS gcd(3,12)=3 PASS gcd(3,13)=1 PASS gcd(3,14)=1 PASS gcd(3,15)=3 PASS gcd(3,16)=1 PASS gcd(3,17)=1 PASS gcd(3,18)=3 PASS gcd(3,19)=1 PASS gcd(3,20)=1 PASS gcd(3,21)=3 PASS gcd(3,22)=1 PASS gcd(3,23)=1 PASS gcd(3,24)=3 PASS gcd(3,25)=1 PASS gcd(3,26)=1 PASS gcd(3,27)=3 PASS gcd(3,28)=1 PASS gcd(3,29)=1 PASS gcd(3,30)=3 PASS gcd(3,31)=1 PASS gcd(3,32)=1 PASS gcd(3,33)=3 PASS gcd(3,34)=1 PASS gcd(3,35)=1 PASS gcd(3,36)=3 PASS gcd(3,37)=1 PASS gcd(3,38)=1 PASS gcd(3,39)=3 PASS gcd(3,40)=1 PASS gcd(4,1)=1 PASS gcd(4,2)=2 PASS gcd(4,3)=1 PASS gcd(4,4)=4 PASS gcd(4,5)=1 PASS gcd(4,6)=2 PASS gcd(4,7)=1 PASS gcd(4,8)=4 PASS gcd(4,9)=1 PASS gcd(4,10)=2 PASS gcd(4,11)=1 PASS gcd(4,12)=4 PASS gcd(4,13)=1 PASS gcd(4,14)=2 PASS gcd(4,15)=1 PASS gcd(4,16)=4 PASS gcd(4,17)=1 PASS gcd(4,18)=2 PASS gcd(4,19)=1 PASS gcd(4,20)=4 PASS gcd(4,21)=1 PASS gcd(4,22)=2 PASS gcd(4,23)=1 PASS gcd(4,24)=4 PASS gcd(4,25)=1 PASS gcd(4,26)=2 PASS gcd(4,27)=1 PASS gcd(4,28)=4 PASS gcd(4,29)=1 PASS gcd(4,30)=2 PASS gcd(4,31)=1 PASS gcd(4,32)=4 PASS gcd(4,33)=1 PASS gcd(4,34)=2 PASS gcd(4,35)=1 PASS gcd(4,36)=4 PASS gcd(4,37)=1 PASS gcd(4,38)=2 PASS gcd(4,39)=1 PASS gcd(4,40)=4 PASS gcd(5,1)=1 PASS gcd(5,2)=1 PASS gcd(5,3)=1 PASS gcd(5,4)=1 PASS gcd(5,5)=5 PASS gcd(5,6)=1 PASS gcd(5,7)=1 PASS gcd(5,8)=1 PASS gcd(5,9)=1 PASS gcd(5,10)=5 PASS gcd(5,11)=1 PASS gcd(5,12)=1 PASS gcd(5,13)=1 PASS gcd(5,14)=1 PASS gcd(5,15)=5 PASS gcd(5,16)=1 PASS gcd(5,17)=1 PASS gcd(5,18)=1 PASS gcd(5,19)=1 PASS gcd(5,20)=5 PASS gcd(5,21)=1 PASS gcd(5,22)=1 PASS gcd(5,23)=1 PASS gcd(5,24)=1 PASS gcd(5,25)=5 PASS gcd(5,26)=1 PASS gcd(5,27)=1 PASS gcd(5,28)=1 PASS gcd(5,29)=1 PASS gcd(5,30)=5 PASS gcd(5,31)=1 PASS gcd(5,32)=1 PASS gcd(5,33)=1 PASS gcd(5,34)=1 PASS gcd(5,35)=5 PASS gcd(5,36)=1 PASS gcd(5,37)=1 PASS gcd(5,38)=1 PASS gcd(5,39)=1 PASS gcd(5,40)=5 PASS gcd(6,1)=1 PASS gcd(6,2)=2 PASS gcd(6,3)=3 PASS gcd(6,4)=2 PASS gcd(6,5)=1 PASS gcd(6,6)=6 PASS gcd(6,7)=1 PASS gcd(6,8)=2 PASS gcd(6,9)=3 PASS gcd(6,10)=2 PASS gcd(6,11)=1 PASS gcd(6,12)=6 PASS gcd(6,13)=1 PASS gcd(6,14)=2 PASS gcd(6,15)=3 PASS gcd(6,16)=2 PASS gcd(6,17)=1 PASS gcd(6,18)=6 PASS gcd(6,19)=1 PASS gcd(6,20)=2 PASS gcd(6,21)=3 PASS gcd(6,22)=2 PASS gcd(6,23)=1 PASS gcd(6,24)=6 PASS gcd(6,25)=1 PASS gcd(6,26)=2 PASS gcd(6,27)=3 PASS gcd(6,28)=2 PASS gcd(6,29)=1 PASS gcd(6,30)=6 PASS gcd(6,31)=1 PASS gcd(6,32)=2After the directed corner cases (including the shift-heavy
gcd(1024,768)=256and thegcd(x,0)=xcases), the testbench runs an exhaustive 40×40 sweep, self-checking every pair against the modulo-based reference GCD. TheALL TESTS PASSEDline confirms the binary FSM returns identical results to the Euclidean reference across all 1606 swept pairs, so the shift-and-subtract optimisation is proven equivalent, not just plausible.How the Euclidean GCD FSM works
The Euclidean algorithm rests on one identity:
gcd(a, b) = gcd(a - b, b)whena > b. Subtracting the smaller value from the larger never changes the GCD, and the pair strictly shrinks, so the process must terminate whena == b— that common value is the answer.State diagram
- IDLE — wait for
start, latcha_inandb_ininto working registers. - CALC — each clock, compare and subtract: if
a > bdoa <= a - b, elseb <= b - a. Finish when the operands meet or one is zero. - DONE — pulse
donehigh for one cycle, then return to IDLE.
Because only one subtraction happens per clock, the number of cycles equals the number of subtraction steps the math takes — the datapath is tiny but the latency is data-dependent.
Subtraction vs binary (Stein) GCD
Both algorithms compute the same result, but they trade area for latency differently.
- Subtraction GCD is the smallest: one subtractor and one comparator. Its worst case is pathological —
gcd(N, 1)needsN-1iterations because each step only removes 1. - Binary GCD replaces division-by-the-difference with shifts. It removes at least one factor of two per step and, when both operands are odd, halves their difference. Each iteration removes at least one bit, bounding the loop at roughly
2·Witerations for aW-bit width — a huge win for lopsided inputs, at the cost of extra muxing for the even/odd cases and a shift-count register.
A third option, the modulo (division) based Euclid, converges in the fewest iterations but needs a hardware divider, which is far larger and usually multi-cycle itself. For most FPGA and small-ASIC blocks the binary GCD is the sweet spot.
Worst-case iteration count
For the subtraction FSM, the worst case is when the two inputs are very different in magnitude, e.g. gcd(2^W-1, 1), which takes 2^W - 2 cycles. Designers who need bounded latency should either cap the input range or switch to the binary variant.
For the binary GCD, the operand sizes shrink by at least one bit roughly every one or two cycles, so the loop is bounded by O(W) iterations rather than O(2^W) values. This predictable upper bound is exactly why Stein's algorithm is preferred in hardware where you must budget cycles.
The done / start handshake
Both designs use a simple level-triggered start and a one-cycle done pulse. The consumer asserts start for at least one clock with valid a_in/b_in; the FSM latches the operands and begins. When the result is ready, done goes high for a single cycle with gcd valid, then the machine returns to IDLE ready for the next request.
Keep two rules in mind. First, sample gcd on the cycle done is high — it is only guaranteed valid then. Second, if your start can stay asserted for many cycles, make sure the IDLE state only re-triggers on a fresh request (edge-detect start, or require the consumer to drop it) so you do not accidentally restart mid-computation.
Why no divider is needed
A naive reading of "Euclid's algorithm" assumes a modulo operation, which implies a hardware divider — one of the most expensive arithmetic blocks you can instantiate. The key insight is that a mod b is just repeated subtraction of b from a, and the GCD identity holds for a single subtraction too. So you can spread that "division" across many cheap cycles using only an adder/subtractor and comparators. The binary variant goes further and uses shifts, which are free wiring in hardware, to accelerate convergence. Either way, synthesis maps the design to a handful of LUTs and flip-flops with no DSP divider in sight.
FAQ
Is this gcd verilog code synthesizable? Yes. Both modules use only synchronous registers, comparisons, subtraction and shifts — all standard RTL. The testbench module tb is simulation-only (it uses while, % and $display) and should be excluded from synthesis.
What if both inputs are zero? Mathematically gcd(0,0) is undefined; these FSMs return 0, matching the common software convention. Guard against it upstream if your system treats it specially.
Can I parameterize the width? Yes — both modules take a W parameter. The binary version also carries a small shift-count register sized for widths up to 31 bits; widen it for larger operands.
Share your question in comments or talk to our mentor team for batch guidance.
Open this design in the free in-browser simulator — edit, compile and see the waveform/log instantly.
Learn Verilog with mentors, labs and placement support
This free series is maintained by the ChipXpert training team in Hyderabad & Bengaluru. Go deeper with instructor-led courses on real EDA tools.
Explore VLSI CoursesLive online and classroom batches in Hyderabad & Bengaluru. Fill in your details and a counsellor will call you back.
- Real EDA tools in your browser: industry-standard EDAReal EDA tools in your browser
- Recorded sessions on the elearn portalRecorded sessions
- Placement assistance: resume, mock interviewsPlacement assistance
- Merit scholarship up to 60% · EMI optionsScholarship up to 60%