Newton-Raphson Divider in Verilog with Code

// Fixed-point Newton-Raphson reciprocal (Q16).
// Refines x_{i+1} = x_i*(2 - D*x_i); seed x0 = 1.0 (valid for D in [0.5,1)).
module nr_recip #(
    parameter Q    = 16,
    parameter ITER = 6
) (
    input  [31:0] d,        // divisor, Q16, assumed normalized to [0.5,1)
    output reg [31:0] recip // 1/d, Q16
);
    integer i;
    reg [63:0] x, prod, t;
    localparam [63:0] ONE = (64'd1 << Q);
    localparam [63:0] TWO = (64'd2 << Q);
    always @(*) begin
        x = ONE;                        // seed = 1.0
        for (i = 0; i < ITER; i = i + 1) begin
            prod = (d * x) >> Q;        // D*x  (Q16)
            t    = TWO - prod;          // 2 - D*x
            x    = (x * t) >> Q;        // x*(2 - D*x)
        end
        recip = x[31:0];
    end
endmodule

module tb;
    localparam Q   = 16;
    localparam ONE = (1 << Q);
    reg  [31:0] d;
    wire [31:0] recip;
    reg  [31:0] dv [0:4];
    integer k, fails;
    reg [63:0] golden, diff, q_hw, q_gold, qdiff;
    reg [31:0] num;
    localparam EPS = 64;        // ~0.001 in Q16

    nr_recip #(.Q(Q), .ITER(6)) dut (.d(d), .recip(recip));

    initial begin
        dv[0] = 32768;   // 0.5
        dv[1] = 40960;   // 0.625
        dv[2] = 49152;   // 0.75
        dv[3] = 57344;   // 0.875
        dv[4] = 61440;   // 0.9375
        num   = 32'd45875;  // 0.7 in Q16, a fixed numerator for N/D check
        fails = 0;
        for (k = 0; k < 5; k = k + 1) begin
            d = dv[k];
            #1;
            // golden reciprocal in Q16 via integer division (TB reference only)
            golden = (64'd1 << (2*Q)) / d;
            diff   = (recip > golden) ? (recip - golden) : (golden - recip);
            if (diff <= EPS)
                $display("PASS recip d=%0d hw=%0d golden=%0d diff=%0d", d, recip, golden, diff);
            else begin
                $display("FAIL recip d=%0d hw=%0d golden=%0d diff=%0d", d, recip, golden, diff);
                fails = fails + 1;
            end
            // N/D using the reciprocal: q = num * recip (multiply only)
            q_hw   = (num * recip) >> Q;
            q_gold = (num << Q) / d;
            qdiff  = (q_hw > q_gold) ? (q_hw - q_gold) : (q_gold - q_hw);
            if (qdiff <= EPS)
                $display("PASS N/D   d=%0d q_hw=%0d q_gold=%0d diff=%0d", d, q_hw, q_gold, qdiff);
            else begin
                $display("FAIL N/D   d=%0d q_hw=%0d q_gold=%0d diff=%0d", d, q_hw, q_gold, qdiff);
                fails = fails + 1;
            end
        end
        if (fails == 0) $display("ALL TESTS PASSED");
        else            $display("TOTAL FAILURES=%0d", fails);
        $finish;
    end
endmodule

PASS recip d=32768 hw=131072 golden=131072 diff=0
PASS N/D   d=32768 q_hw=91750 q_gold=91750 diff=0
PASS recip d=40960 hw=104858 golden=104857 diff=1
PASS N/D   d=40960 q_hw=73400 q_gold=73400 diff=0
PASS recip d=49152 hw=87382 golden=87381 diff=1
PASS N/D   d=49152 q_hw=61167 q_gold=61166 diff=1
PASS recip d=57344 hw=74899 golden=74898 diff=1
PASS N/D   d=57344 q_hw=52429 q_gold=52428 diff=1
PASS recip d=61440 hw=69906 golden=69905 diff=1
PASS N/D   d=61440 q_hw=48933 q_gold=48933 diff=0
ALL TESTS PASSED
The log prints a PASS line for every divisor: the hardware reciprocal matches the testbench's integer golden (1<<32)/D to within 1 LSB of Q16, and the multiply-only N/D result matches (N<<16)/D just as tightly. The closing ALL TESTS PASSED confirms every case cleared the tolerance, so a real bug in the iteration would surface as a FAIL.

A Q20 divider with a runtime iteration count. For four (N, D) pairs the testbench sweeps the iteration count from 1 to 6 and checks that the error against the golden quotient never increases, then requires the final result to land within a tight tolerance. This makes the quadratic convergence visible in the numbers.
nr_divider.vSimulation log
// Newton-Raphson divider with a runtime iteration count, parameterized Q width.
// Computes Q = N/D by first refining R = 1/D (multiply-only), then Q = N*R.
module nr_divider #(
    parameter Q = 20      // fractional bits
) (
    input  [63:0] n,          // numerator, Qformat
    input  [63:0] d,          // divisor,  Qformat, normalized to [0.5,1)
    input  [3:0]  iters,      // number of Newton iterations
    output reg [63:0] quot    // n/d, Qformat
);
    integer i;
    reg [127:0] x, prod, t;
    localparam [127:0] ONE = (128'd1 << Q);
    localparam [127:0] TWO = (128'd2 << Q);
    always @(*) begin
        x = ONE;                         // seed 1.0
        for (i = 0; i < iters; i = i + 1) begin
            prod = (d * x) >> Q;
            t    = TWO - prod;
            x    = (x * t) >> Q;
        end
        quot = ((n * x) >> Q);           // n * (1/d)
    end
endmodule

module tb;
    localparam Q   = 20;
    localparam ONE = (1 << Q);
    reg  [63:0] n, d;
    reg  [3:0]  iters;
    wire [63:0] quot;
    reg  [63:0] golden, diff, prev_err;
    integer p, j, fails;
    reg [63:0] nv [0:3];
    reg [63:0] dv [0:3];
    localparam EPS = 8;      // tight Q20 tolerance at full iterations

    nr_divider #(.Q(Q)) dut (.n(n), .d(d), .iters(iters), .quot(quot));

    initial begin
        nv[0] = 64'd1572864; dv[0] = 64'd786432;  // 1.5 / 0.75
        nv[1] = 64'd1887437; dv[1] = 64'd629146;  // 1.8 / 0.6
        nv[2] = 64'd3250586; dv[2] = 64'd996148;  // 3.1 / 0.95
        nv[3] = 64'd2097152; dv[3] = 64'd576717;  // 2.0 / 0.55
        fails = 0;

        for (p = 0; p < 4; p = p + 1) begin
            n = nv[p];
            d = dv[p];
            golden = (n << Q) / d;   // TB integer-fixed-point reference
            prev_err = 64'hFFFFFFFFFFFFFFFF;
            // sweep iteration counts; show error monotonically shrinking
            for (j = 1; j <= 6; j = j + 1) begin
                iters = j[3:0];
                #1;
                diff = (quot > golden) ? (quot - golden) : (golden - quot);
                $display("pair=%0d iters=%0d quot=%0d golden=%0d err=%0d", p, j, quot, golden, diff);
                if (j > 1 && diff > prev_err) begin
                    $display("FAIL error did not shrink pair=%0d iters=%0d", p, j);
                    fails = fails + 1;
                end
                prev_err = diff;
            end
            // final (6 iters) must be within tight tolerance
            if (diff <= EPS)
                $display("PASS converged pair=%0d err=%0d", p, diff);
            else begin
                $display("FAIL not converged pair=%0d err=%0d", p, diff);
                fails = fails + 1;
            end
        end
        if (fails == 0) $display("ALL TESTS PASSED");
        else            $display("TOTAL FAILURES=%0d", fails);
        $finish;
    end
endmodule
pair=0 iters=1 quot=1966080 golden=2097152 err=131072
pair=0 iters=2 quot=2088960 golden=2097152 err=8192
pair=0 iters=3 quot=2097120 golden=2097152 err=32
pair=0 iters=4 quot=2097151 golden=2097152 err=1
pair=0 iters=5 quot=2097153 golden=2097152 err=1
pair=0 iters=6 quot=2097153 golden=2097152 err=1
PASS converged pair=0 err=1
pair=1 iters=1 quot=2642411 golden=3145726 err=503315
pair=1 iters=2 quot=3065195 golden=3145726 err=80531
pair=1 iters=3 quot=3143664 golden=3145726 err=2062
pair=1 iters=4 quot=3145725 golden=3145726 err=1
pair=1 iters=5 quot=3145727 golden=3145726 err=1
pair=1 iters=6 quot=3145727 golden=3145726 err=1
PASS converged pair=1 err=1
pair=2 iters=1 quot=3413112 golden=3421666 err=8554
pair=2 iters=2 quot=3421647 golden=3421666 err=19
pair=2 iters=3 quot=3421668 golden=3421666 err=2
pair=2 iters=4 quot=3421668 golden=3421666 err=2
pair=2 iters=5 quot=3421668 golden=3421666 err=2
pair=2 iters=6 quot=3421668 golden=3421666 err=2
PASS converged pair=2 err=2
pair=3 iters=1 quot=3040870 golden=3813002 err=772132
pair=3 iters=2 quot=3656646 golden=3813002 err=156356
pair=3 iters=3 quot=3806594 golden=3813002 err=6408
pair=3 iters=4 quot=3812994 golden=3813002 err=8
pair=3 iters=5 quot=3813004 golden=3813002 err=2
pair=3 iters=6 quot=3813004 golden=3813002 err=2
PASS converged pair=3 err=2
ALL TESTS PASSED
For each pair the err= value falls steeply as iterations increase (roughly doubling the correct bits each step) until it hits the Q20 rounding floor of a few LSBs. The testbench flags any step where the error grows and any pair that fails to converge, so the ALL TESTS PASSED line proves both the monotonic refinement and the final accuracy across all four pairs.

How the iteration works and why it converges quadratically
Newton-Raphson finds a root of f(x) = 1/x − D, whose root is exactly 1/D. Applying the Newton update xi+1 = xi − f(xi)/f'(xi) with f'(x) = −1/x² collapses neatly to a division-free form:
x_{i+1} = x_i * (2 - D * x_i)
Let the relative error be ei = 1 − D·xi. Substituting gives ei+1 = ei². The error is squared every iteration, which is quadratic convergence: if a step is accurate to 4 bits, the next is accurate to about 8, then 16, then 32. That is why the sweep in Example 2 shows the error dropping by orders of magnitude per step until it reaches the fixed-point rounding floor.
Seed selection and normalization
Quadratic convergence only holds once you are reasonably close, and the iteration diverges unless 0 < x0 < 2/D. The standard trick is to normalize the divisor into a fixed range, typically D ∈ [0.5, 1), by shifting out leading zeros (the same shift amount is applied in reverse to the result's exponent or binary point). Within that range a constant seed such as x0 = 1.0 is always valid, which is what Example 1 uses.
Production dividers squeeze out iterations by using a better linear seed, classically x0 = 48/17 − (32/17)·D, which is the minimax linear fit over [0.5,1) and already gives about 4 correct bits. A small lookup table addressed by the top few bits of D can give 8–12 bits, cutting the number of Newton steps to two or three.
Why multiply-only matters in hardware
A full-width hardware divider is expensive: restoring and non-restoring dividers produce roughly one quotient bit per cycle, so a 32-bit divide is a long, high-latency operation that is hard to pipeline. Newton-Raphson replaces that with a short sequence of multiplications, and multipliers are cheap, fast, and already present in most datapaths (DSP blocks on FPGAs, dedicated multiplier arrays in ASICs).
Each iteration is two multiplies and a subtract; the subtract 2 − D·x is a simple two's-complement operation (and in some formats just a bit inversion near 1.0).
The structure is regular and easy to pipeline: unroll the loop and place registers between iterations to hit a target clock, trading latency for throughput.
The same hardware computes reciprocal, divide (N·(1/D)), and with a sign-of-the-error variant, reciprocal square root — good reuse of one multiplier datapath.
Fixed-point tolerance and when to stop
In fixed point the result can never be more accurate than the format's least significant bit, so error cannot fall to zero — it reaches a rounding floor of one or a few LSBs and then stops improving, exactly as the Example 2 log shows. Iterating further wastes cycles and can even jitter by ±1 LSB because of truncation in the intermediate >> Q shifts.
Pick the iteration count from the seed accuracy and the target width: starting bits b and doubling each step, k iterations give about b·2k correct bits, so solve for the smallest k that covers your fractional width. With a 1-bit seed and Q20 that is about 5 steps; with a good linear or table seed it drops to 2–3. Guarding against the last-LSB jitter (as Example 2's non-increasing-error check does) is a practical way to validate the chosen count.
Comparison to restoring and non-restoring division
Restoring and non-restoring division are digit-recurrence algorithms: they produce a fixed number of quotient bits per cycle (one for basic radix-2, more for SRT radix-4/8), so latency grows linearly with precision and the per-step logic is an adder/subtractor plus control.
Latency: digit-recurrence is linear in bits; Newton-Raphson is logarithmic in bits (because of quadratic convergence), so it wins at wide precisions — at the cost of multipliers.
Area/energy: non-restoring needs only adders and is small; Newton-Raphson reuses multipliers, which is attractive when they already exist for other operations.
Exactness: non-restoring gives a bit-exact quotient and remainder, which matters for integer division; Newton-Raphson gives a rounded reciprocal, so a final correction step is needed for IEEE-correct rounding or an exact remainder.
Common mistakes
Forgetting to normalize D, so the constant seed falls outside (0, 2/D) and the iteration diverges.
Under-sizing intermediate registers — D·x is a double-width product and must not overflow before the >> Q shift.
Over-iterating and then being surprised by ±1 LSB jitter at the rounding floor.
FAQ
Is this synthesizable? Yes. Both modules use only combinational always @(*) logic with a bounded, unrollable loop; for timing you would register the result or pipeline each iteration.
Can it do signed division? Operate on magnitudes, compute the sign separately as the XOR of the operand signs, and apply it at the end.
Why not just use the / operator? The testbenches use / as an offline golden reference, but / on variables does not map to efficient hardware; Newton-Raphson is how you build a fast divider from multipliers.
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