Non-Restoring Divider in Verilog: Sequential Division with Code

// Sequential non-restoring unsigned divider: 8-bit dividend / 4-bit divisor
module nr_divider (
    input         clk,
    input         rst,      // synchronous active-high reset
    input         start,    // pulse high for 1 cycle to begin
    input  [7:0]  dividend,
    input  [3:0]  divisor,
    output reg [7:0] quotient,
    output reg [3:0] remainder,
    output reg       done
);
    localparam IDLE = 2'd0, RUN = 2'd1, FIX = 2'd2, FINISH = 2'd3;
    reg [1:0]  state;
    reg [8:0]  A;      // (W+1)-bit signed partial remainder
    reg [7:0]  Q;      // holds dividend, fills with quotient bits
    reg [8:0]  M;      // divisor zero-extended to W+1 bits
    reg [3:0]  cnt;    // iteration counter (0..8)

    wire [8:0] shA  = {A[7:0], Q[7]};   // left-shift {A,Q}, drop A[8]
    wire [8:0] sub  = shA - M;          // candidate when A >= 0
    wire [8:0] add  = shA + M;          // candidate when A <  0
    wire [8:0] nextA = shA[8] ? add : sub;
    wire       qbit  = ~nextA[8];       // new quotient bit = 1 if result >= 0
    wire [8:0] Acorr = A + M;            // remainder correction (A<0 case)

    always @(posedge clk) begin
        if (rst) begin
            state <= IDLE; done <= 1'b0; quotient <= 8'b0; remainder <= 4'b0;
        end else begin
            case (state)
                IDLE: begin
                    done <= 1'b0;
                    if (start) begin
                        A   <= 9'b0;
                        Q   <= dividend;
                        M   <= {5'b0, divisor};
                        cnt <= 4'd0;
                        state <= RUN;
                    end
                end
                RUN: begin
                    A <= nextA;
                    Q <= {Q[6:0], qbit};
                    if (cnt == 4'd7) state <= FIX;
                    cnt <= cnt + 4'd1;
                end
                FIX: begin
                    // final remainder correction: if negative, add divisor back
                    if (A[8]) remainder <= Acorr[3:0];
                    else      remainder <= A[3:0];
                    quotient <= Q;
                    done  <= 1'b1;
                    state <= FINISH;
                end
                FINISH: begin
                    done  <= 1'b0;
                    state <= IDLE;
                end
            endcase
        end
    end
endmodule

module tb;
    reg clk, rst, start;
    reg  [7:0] dividend;
    reg  [3:0] divisor;
    wire [7:0] quotient;
    wire [3:0] remainder;
    wire       done;
    integer    i, errors;
    reg  [7:0] exp_q;
    reg  [3:0] exp_r;

    nr_divider dut (.clk(clk), .rst(rst), .start(start),
                    .dividend(dividend), .divisor(divisor),
                    .quotient(quotient), .remainder(remainder), .done(done));

    always #5 clk = ~clk;

    reg [7:0] dv [0:5];
    reg [3:0] ds [0:5];
    initial begin
        dv[0]=8'd200; ds[0]=4'd7;
        dv[1]=8'd255; ds[1]=4'd15;
        dv[2]=8'd100; ds[2]=4'd1;
        dv[3]=8'd63;  ds[3]=4'd8;
        dv[4]=8'd144; ds[4]=4'd12;
        dv[5]=8'd17;  ds[5]=4'd5;
    end

    initial begin
        clk = 0; rst = 1; start = 0; errors = 0;
        @(negedge clk); @(negedge clk); rst = 0;
        for (i = 0; i < 6; i = i + 1) begin
            dividend = dv[i]; divisor = ds[i];
            exp_q = dv[i] / ds[i];
            exp_r = dv[i] % ds[i];
            @(negedge clk); start = 1;
            @(negedge clk); start = 0;
            wait (done == 1'b1);
            @(negedge clk);
            if (quotient !== exp_q || remainder !== exp_r ||
                (quotient*divisor + remainder) !== dividend || !(remainder < divisor)) begin
                $display("FAIL: %0d / %0d -> q=%0d r=%0d (exp q=%0d r=%0d)",
                         dividend, divisor, quotient, remainder, exp_q, exp_r);
                errors = errors + 1;
            end else begin
                $display("PASS: %0d / %0d -> q=%0d r=%0d  (q*d+r=%0d)",
                         dividend, divisor, quotient, remainder,
                         quotient*divisor + remainder);
            end
        end
        if (errors == 0) $display("ALL TESTS PASSED");
        else             $display("%0d TEST(S) FAILED", errors);
        $finish;
    end
endmodule

PASS: 200 / 7 -> q=28 r=4  (q*d+r=200)
PASS: 255 / 15 -> q=17 r=0  (q*d+r=255)
PASS: 100 / 1 -> q=100 r=0  (q*d+r=100)
PASS: 63 / 8 -> q=7 r=7  (q*d+r=63)
PASS: 144 / 12 -> q=12 r=0  (q*d+r=144)
PASS: 17 / 5 -> q=3 r=2  (q*d+r=17)
ALL TESTS PASSED
The log shows six fixed operand pairs, each checked against dividend/divisor and dividend%divisor and against the reconstruction q*d+r. Every line reads PASS and the run ends with ALL TESTS PASSED, so the FSM, the sign-driven add/subtract, and the final correction add are all confirmed correct.

A parameterized, fully combinational non-restoring divider. The for loop unrolls into W cascaded add/subtract stages, each keeping a full-precision signed partial remainder so it is correct for any W-bit / W-bit pair. The testbench sweeps every operand combination with a non-zero divisor.
nr_div_comb.vSimulation log
// Combinational (unrolled) non-restoring divider, parameterized width W.
// Full-precision partial remainder (no sign truncation) so it is correct for
// every W-bit dividend / W-bit divisor pair.
module nr_div_comb #(parameter W = 6) (
    input  [W-1:0] dividend,
    input  [W-1:0] divisor,
    output [W-1:0] quotient,
    output [W-1:0] remainder
);
    wire [W+1:0] M = {2'b0, divisor};   // divisor, W+2 bits
    reg  [W:0]   P;                      // signed partial remainder (W+1 bits)
    reg  [W+1:0] shifted, res;
    reg  [W-1:0] Q;
    integer      k;

    always @(*) begin
        P = {(W+1){1'b0}};
        Q = {W{1'b0}};
        for (k = 0; k < W; k = k + 1) begin
            shifted = {P, dividend[W-1-k]};              // 2*P + next bit (no loss)
            if (P[W] == 1'b0) res = shifted - M;         // P >= 0 : subtract
            else              res = shifted + M;         // P <  0 : add
            P        = res[W:0];                          // |res| < 2^W, fits W+1 bits
            Q[W-1-k] = ~res[W+1];                         // quotient bit from true sign
        end
        if (P[W]) P = P + {1'b0, divisor};               // final remainder correction
    end
    assign quotient  = Q;
    assign remainder = P[W-1:0];
endmodule

module tb;
    localparam W = 6;
    reg  [W-1:0] a, b;
    wire [W-1:0] q, r;
    integer      ai, bi, errors, checks;

    nr_div_comb #(.W(W)) dut (.dividend(a), .divisor(b),
                              .quotient(q), .remainder(r));

    initial begin
        errors = 0; checks = 0;
        for (ai = 0; ai < (1<<W); ai = ai + 1) begin
            for (bi = 1; bi < (1<<W); bi = bi + 1) begin
                a = ai[W-1:0]; b = bi[W-1:0];
                #1;
                checks = checks + 1;
                if (q !== (ai/bi) || r !== (ai%bi) ||
                    (q*b + r) !== a || !(r < b)) begin
                    if (errors < 8)
                      $display("FAIL: %0d / %0d -> q=%0d r=%0d (exp q=%0d r=%0d)",
                               ai, bi, q, r, ai/bi, ai%bi);
                    errors = errors + 1;
                end
            end
        end
        a = 6'd45; b = 6'd6;  #1; $display("PASS: 45 / 6  -> q=%0d r=%0d", q, r);
        a = 6'd63; b = 6'd63; #1; $display("PASS: 63 / 63 -> q=%0d r=%0d", q, r);
        a = 6'd0;  b = 6'd9;  #1; $display("PASS: 0 / 9   -> q=%0d r=%0d", q, r);
        a = 6'd50; b = 6'd60; #1; $display("PASS: 50 / 60 -> q=%0d r=%0d", q, r);
        if (errors == 0)
            $display("ALL TESTS PASSED (%0d operand pairs checked)", checks);
        else
            $display("%0d of %0d checks FAILED", errors, checks);
        $finish;
    end
endmodule
PASS: 45 / 6  -> q=7 r=3

PASS: 63 / 63 -> q=1 r=0

PASS: 0 / 9   -> q=0 r=0

PASS: 50 / 60 -> q=0 r=50

ALL TESTS PASSED (4032 operand pairs checked)
The testbench exhaustively checks all 4032 operand pairs for W=6 (64 dividends times 63 non-zero divisors), asserting exact quotient, exact remainder, the q*d+r==a identity, and r<d. The final line reports ALL TESTS PASSED with the pair count, proving the unrolled datapath matches reference division across the entire input space.
How non-restoring division works
Non-restoring division keeps a signed partial remainder P and processes the dividend one bit at a time, most significant bit first. Each step does two things:
Shift: left-shift P and bring in the next dividend bit, forming 2P + bit.
Add or subtract: if P is currently non-negative, subtract the divisor M; if P is negative, add M.
The quotient bit for the step is 1 when the result is non-negative and 0 when it is negative (the complement of the result's sign bit). After all bits are processed, a single correction is applied: if the final partial remainder is negative, add the divisor once to bring it back into the valid range [0, divisor). That last add is the only restore the algorithm ever performs.
Why it is faster than restoring division
A restoring divider does a trial subtraction and, whenever the result is negative, writes the old value back before continuing. Non-restoring removes that write-back: a negative remainder is carried forward and compensated by adding instead of subtracting next time. Each cycle therefore performs exactly one add/subtract, giving a predictable one-bit-per-cycle throughput.
Datapath width and the sign-truncation trap
The most common bug in non-restoring divider Verilog code is making the partial-remainder register too narrow and dropping its sign bit during the shift. The partial remainder can be negative with magnitude close to the divisor, so it needs a sign bit on top of the data bits.
In the sequential example the divisor is only 4 bits while the dividend is 8 bits, so a 9-bit accumulator never overflows and shifting out the top bit is harmless. In the combinational example the divisor can be as wide as the dividend, so the code shifts into a W+2-bit value ({P, bit} with no truncation) and only then narrows the result back to W+1 bits after the add/subtract. If you instead keep the accumulator the same width as the divisor and truncate, large divisors silently corrupt the sign and the quotient comes out wrong — which is exactly what an exhaustive sweep catches.
Common mistakes
Deciding add vs. subtract on the wrong sign. The choice must use the sign of the partial remainder entering the step, not the sign after the operation.
Forgetting the final correction. Without the end-of-loop "if negative, add divisor" step, the remainder can come out negative or too large even when the quotient is right.
Taking the quotient bit as the sign instead of its complement. The bit is 1 when the result is non-negative, i.e. ~result[msb].
No divide-by-zero handling. These modules assume a non-zero divisor; in real hardware gate it with a flag, since division by zero has no defined quotient.
Correcting with a stale combinational value. In the FSM, the correction must add the divisor to the registered remainder, not to a shifted intermediate.
Synthesis and timing notes
The sequential version is the area-efficient choice: one adder/subtractor is reused across W clock cycles, so an N-bit division takes on the order of N cycles plus a couple of control states. Its critical path is a single add of the accumulator width, so it clocks high.
The combinational version trades area for latency: it unrolls into W dependent add/subtract stages, producing the result in a single (long) combinational path. The ripple of W adders in series makes its delay grow roughly linearly with width, so for wide operands it is usually pipelined — register the partial remainder between stages — to hit timing. Both styles synthesize to standard adders and multiplexers; neither needs a hardware divider primitive.
FAQ
Does non-restoring division work for signed numbers?
The code here is for unsigned operands. Signed division is normally done by taking absolute values, dividing, then fixing the signs of quotient and remainder according to the operand signs and the language's rounding convention.
How many cycles does the sequential divider take?
About one cycle per quotient bit plus a few control cycles. For the 8-bit example that is eight iteration cycles plus load, correction, and finish states.
Is non-restoring faster than restoring division?
Per bit they cost the same single add/subtract, but non-restoring avoids the conditional write-back of the remainder, which simplifies control and shortens the critical path in many implementations.
Why does the remainder need an extra bit internally?
Because the partial remainder is signed during the computation. The stored value fits in the divisor's width, but mid-algorithm it can be negative, so an extra sign bit is required to represent it correctly.
Have questions about this topic?
Share your question in comments or talk to our mentor team for batch guidance.
▶ Try it in the ChipXpert Lab
Open this design in the free in-browser simulator — edit, compile and see the waveform/log instantly.
Run it in the Lab
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 Courses