Karatsuba Multiplier in Verilog: Divide-and-Conquer with Code

// Single-level unsigned 8x8 Karatsuba multiplier (4-bit halves)
module karatsuba8 (
    input  [7:0] a,
    input  [7:0] b,
    output [15:0] p
);
    wire [3:0] ah = a[7:4];
    wire [3:0] al = a[3:0];
    wire [3:0] bh = b[7:4];
    wire [3:0] bl = b[3:0];

    wire [7:0] z2 = ah * bh;           // high product
    wire [7:0] z0 = al * bl;           // low product
    wire [4:0] sa = ah + al;           // 5-bit sum (carry out)
    wire [4:0] sb = bh + bl;           // 5-bit sum
    wire [9:0] prod_s = sa * sb;       // (ah+al)*(bh+bl), up to 10 bits
    wire [9:0] z1 = prod_s - z2 - z0;  // middle term

    assign p = ({z2, 8'b0}) + ({z1, 4'b0}) + z0;
endmodule

module tb;
    reg  [7:0] a, b;
    wire [15:0] p;
    integer i, j;
    reg [15:0] ref;
    integer fails;

    karatsuba8 dut (.a(a), .b(b), .p(p));

    initial begin
        fails = 0;
        // Wide, deterministic sweep: every 8-bit a times a set of b values
        for (i = 0; i < 256; i = i + 1) begin
            for (j = 0; j < 256; j = j + 17) begin
                a = i[7:0];
                b = j[7:0];
                #1;
                ref = a * b;
                if (p !== ref) begin
                    $display("FAIL a=%0d b=%0d got=%0d exp=%0d", a, b, p, ref);
                    fails = fails + 1;
                end
            end
        end
        // Named corner cases
        a = 8'd255; b = 8'd255; #1;
        if (p === 16'd65025) $display("PASS 255*255 = %0d", p);
        else begin $display("FAIL 255*255 got=%0d", p); fails = fails + 1; end

        a = 8'd0; b = 8'd200; #1;
        if (p === 16'd0) $display("PASS 0*200 = %0d", p);
        else begin $display("FAIL 0*200 got=%0d", p); fails = fails + 1; end

        a = 8'd15; b = 8'd16; #1;   // exercises carry in sa (15+0), split boundary
        if (p === 16'd240) $display("PASS 15*16 = %0d", p);
        else begin $display("FAIL 15*16 got=%0d", p); fails = fails + 1; end

        if (fails == 0) $display("ALL TESTS PASSED");
        else $display("TOTAL FAILS %0d", fails);
        $finish;
    end
endmodule

PASS 255*255 = 65025
PASS 0*200 = 0
PASS 15*16 = 240
ALL TESTS PASSED
The log shows PASS lines for the stress corners (255×255, a zero case, and the split-boundary 15×16) and ends with ALL TESTS PASSED. That line only prints when every one of the thousands of swept products matched the golden a*b reference, proving the z0/z1/z2 recombination is bit-accurate.

The same algorithm written with a width parameter N (halves are N/2 bits), instantiated here as a 16×16 multiplier. Note the K+1-bit half-sums and the 2K+2-bit middle product that keep the arithmetic from overflowing.
karatsuba.vSimulation log
// Parameterized single-level unsigned Karatsuba multiplier.
// N must be even; halves are N/2 bits wide. Default N=16.
module karatsuba #(parameter N = 16) (
    input  [N-1:0]   a,
    input  [N-1:0]   b,
    output [2*N-1:0] p
);
    localparam K = N/2;
    wire [K-1:0] ah = a[N-1:K];
    wire [K-1:0] al = a[K-1:0];
    wire [K-1:0] bh = b[N-1:K];
    wire [K-1:0] bl = b[K-1:0];

    wire [2*K-1:0] z2 = ah * bh;
    wire [2*K-1:0] z0 = al * bl;
    wire [K:0]     sa = ah + al;         // K+1 bits
    wire [K:0]     sb = bh + bl;         // K+1 bits
    wire [2*K+1:0] prod_s = sa * sb;     // up to 2K+2 bits
    wire [2*K+1:0] z1 = prod_s - z2 - z0;

    assign p = ({z2, {N{1'b0}}})       // z2 << N
             + ({z1, {K{1'b0}}})       // z1 << K
             + z0;
endmodule

module tb;
    reg  [15:0] a, b;
    wire [31:0] p;
    integer i, j;
    reg [31:0] ref;
    integer fails;

    karatsuba #(.N(16)) dut (.a(a), .b(b), .p(p));

    initial begin
        fails = 0;
        // Deterministic sparse sweep across the 16-bit space.
        for (i = 0; i < 65536; i = i + 1021) begin
            for (j = 0; j < 65536; j = j + 2039) begin
                a = i[15:0];
                b = j[15:0];
                #1;
                ref = a * b;
                if (p !== ref) begin
                    $display("FAIL a=%0d b=%0d got=%0d exp=%0d", a, b, p, ref);
                    fails = fails + 1;
                end
            end
        end
        a = 16'hFFFF; b = 16'hFFFF; #1;
        if (p === 32'd4294836225) $display("PASS 65535*65535 = %0d", p);
        else begin $display("FAIL max got=%0d", p); fails = fails + 1; end

        a = 16'd255; b = 16'd257; #1;   // carry in sa/sb, cross-half mix
        if (p === 16'd255*16'd257) $display("PASS 255*257 = %0d", p);
        else begin $display("FAIL 255*257 got=%0d", p); fails = fails + 1; end

        a = 16'd0; b = 16'hABCD; #1;
        if (p === 32'd0) $display("PASS 0*0xABCD = %0d", p);
        else begin $display("FAIL zero got=%0d", p); fails = fails + 1; end

        if (fails == 0) $display("ALL TESTS PASSED");
        else $display("TOTAL FAILS %0d", fails);
        $finish;
    end
endmodule
PASS 65535*65535 = 4294836225
PASS 255*257 = 65535
PASS 0*0xABCD = 0
ALL TESTS PASSED
The sweep walks the full 16-bit input space with coprime strides so it hits a wide, repeatable set of operand pairs, plus the all-ones maximum (65535×65535 = 4294836225). ALL TESTS PASSED confirms the parameterized shifts (z2<<N, z1<<K) and the widened sums are correct at N=16.

The z0 / z1 / z2 algebra
Write each operand as a high and low half using a split point of k bits: a = ah·2k + al and b = bh·2k + bl. The exact product expands to:
a*b = ah*bh * 2^(2k)
    + (ah*bl + al*bh) * 2^k
    + al*bl
A direct evaluation needs four half-width multiplies: ah*bh, ah*bl, al*bh, al*bl. Karatsuba's insight is that the middle term can be recovered from a single extra product:
z2 = ah*bh
z0 = al*bl
z1 = (ah+al)*(bh+bl) - z2 - z0   // = ah*bl + al*bh
Then a*b = z2·22k + z1·2k + z0. Three multiplications (z2, z0, and the (ah+al)(bh+bl) product) replace four, at the cost of two extra adds and two subtracts.
The (ah+al) carry and the width subtlety
This is where most buggy karatsuba multiplier verilog code goes wrong. If ah and al are each k bits, their sum ah+al can be k+1 bits — it carries. The same is true for bh+bl. If you declare sa and sb as only k bits wide, the top carry is dropped and z1 comes out wrong for large operands.
Declare the half-sums as k+1 bits: in the 8-bit design sa/sb are [4:0].
Their product (ah+al)*(bh+bl) can be up to (k+1)+(k+1) = 2k+2 bits, so z1's raw product needs that width before the subtractions.
The subtraction prod_s - z2 - z0 is mathematically non-negative, so an unsigned result is safe once the widths are correct.
The parameterized example makes this explicit with wire [K:0] sa and wire [2*K+1:0] prod_s.
Why Karatsuba matters for wide multipliers
For a single 8×8 or 16×16 multiply, a modern synthesis tool will usually map a plain a*b to an efficient array or DSP block, and one level of Karatsuba saves little — the extra adders can even cost area. Karatsuba pays off when operands are wide and the sub-multiplications are themselves recursively Karatsuba or mapped to fixed-size hard multipliers.
Applied recursively, replacing four multiplies with three changes the asymptotic cost of multiplication from O(n2) toward O(nlog23) ≈ O(n1.585). In hardware this shows up when building, say, a 256-bit or 1024-bit multiplier for cryptography (RSA, ECC) out of 64×64 DSP primitives: each Karatsuba level cuts the number of DSP multiplies by 25% at the expense of wider adders. The design in these examples is the single-level building block you would nest to reach those widths.
Combinational vs pipelined
Both examples are purely combinational: the product settles after the longest path through the three multipliers, the two adders feeding z1, and the final three-term recombination adder. For small widths that is fine, but for wide recursive Karatsuba the carry chains in the recombination and the sub-multiplier delays make the combinational path long.
To hit timing, pipeline it: register the three sub-products (z2, z0, prod_s) in one stage, compute z1 and register it in a second stage, and perform the shifted final addition in a third. Each stage becomes an always @(posedge clk) block; the combinational algebra shown here is exactly what sits between the pipeline registers. Keep the k+1-bit sum widths in the pipelined version too — registering a too-narrow sum bakes the dropped-carry bug into silicon.
FAQ
Does Karatsuba work for signed multiplication?
The core identity is the same, but you must sign-extend the halves and handle the sign of the middle term carefully; the half-sums become signed k+1-bit values and z1 can be negative, so the subtraction and the final add must be signed. The unsigned version here is the usual starting point and the one asked about in interviews.
Why do the testbenches use strided sweeps instead of $random?
Deterministic stimulus makes the simulation log reproducible and the PASS/FAIL outcome stable. Coprime strides across the input space exercise a wide, well-spread set of operand pairs while keeping runtime short, and the explicit corner cases cover the carry and boundary conditions that a random run might miss on any given seed.
Is one level of Karatsuba faster than a*b?
Not necessarily for narrow operands — measure after synthesis. The win is algorithmic and appears when the structure is applied recursively to wide operands or to reduce the count of scarce hard multiplier blocks.
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