## Do not restore the remainder divider

### Basic algorithm

The basic algorithm of the divider without restoring the remainder comes from the restoring divider. The difference is that when the remainder becomes negative, it does not stop to restore the remainder but continues to run the iteration, and adds the shifted divisor to the iteration instead of subtracting the shifted. Divisor, the basic algorithm is as follows

1. Shift the divisor to the left to be exactly greater than the dividend
2. If the remainder is positive: the remainder is subtracted from the shifted divisor; if the remainder is negative: the remainder is added to the shifted divisor;
3. If the current remainder is positive, the result of this bit is 1, otherwise it is 0, and the divisor is shifted one bit to the right
4. Repeat 2, 3, knowing that the divisor after shifting is smaller than the original divisor

### RTL code

module norestore_divider #(
parameter WIDTH = 4
)(
input clk,//Clock
input rst_n,//Asynchronous reset active low

input [WIDTH * 2-1:0]dividend,
input [WIDTH-1:0]divisor,

input din_valid,

output reg[2 * WIDTH-1:0]dout,
output [WIDTH-1:0]remainder
);

//parameter JUDGE = 2 ** (2 * WIDTH);

reg [2 * WIDTH:0]remainder_r;
reg [3 * WIDTH-1:0]divisor_move;
reg [WIDTH-1:0]divisor_lock;
reg [2 * WIDTH:0]judge;
always @ (*) begin
if(remainder_r[2 * WIDTH] == 1'b0) begin
judge = remainder_r-divisor_move;
end else begin
judge = remainder_r + divisor_move;
end
end

always @ (posedge clk or negedge rst_n) begin
if(~rst_n) begin
{remainder_r,divisor_lock,divisor_move,dout} <='b0;
end else begin
if(din_valid == 1'b1) begin//lock input data
remainder_r[WIDTH * 2-1:0] <= dividend;
remainder_r[2 * WIDTH] <='b0;
divisor_move[3 * WIDTH-1:2 * WIDTH] <= divisor;
divisor_move[2 * WIDTH-1:0] <='b0;
divisor_lock <= divisor;
dout <='b0;
end else if((divisor_move>'{remainder_r}) && (dout =='b0)) begin
//Start calculation conditions
remainder_r <= remainder_r;
dout <='b0;
divisor_move <= divisor_move >> 1;
divisor_lock <= divisor_lock;
end else if(divisor_move >='{divisor_lock}) begin
if(remainder_r[2 * WIDTH] == 1'b0) begin
remainder_r <= judge;
if(judge[2 * WIDTH] =='b0) begin
dout <= {dout[2 * WIDTH-2:0],1'b1};
end else begin
dout <= {dout[2 * WIDTH-2:0],1'b0};
end
end else begin
remainder_r <= judge;
if(judge[2 * WIDTH] =='b0) begin
dout <= {dout[2 * WIDTH-2:0],1'b1};
end else begin
dout <= {dout[2 * WIDTH-2:0],1'b0};
end
end
divisor_move <= divisor_move >> 1;
divisor_lock <= divisor_lock;
end else if(remainder_r[2 * WIDTH-1] == 1'b1) begin
remainder_r <= remainder_r + divisor_lock;
dout <= dout;
divisor_lock <= divisor_lock;
divisor_move <= divisor_move;
end else begin
remainder_r <= remainder_r;
divisor_lock <= divisor_lock;
divisor_move <= divisor_move;
dout <= dout;
end
end
end

assign remainder = remainder_r[WIDTH-1:0];

endmodule

### testing platform

module tb_divider (
);

parameter WIDTH = 4;

logic clk;//Clock
logic rst_n;//Asynchronous reset active low
logic [2 * WIDTH-1:0]dividend;
logic [WIDTH-1:0]divisor;

logic din_valid;

logic [2 * WIDTH-1:0]dout;
logic [WIDTH-1:0]remainder;

norestore_divider #(
.WIDTH(WIDTH)
) dut (
.clk(clk),//Clock
.rst_n(rst_n),//Asynchronous reset active low

.dividend(dividend),
.divisor(divisor),

.din_valid(din_valid),

.dout(dout),
.remainder(remainder)
);

initial begin
clk ='b0;
forever begin
#50 clk = ~clk;
end
end

initial begin
rst_n = 1'b1;
# 5 rst_n ='b0;
#10 rst_n = 1'b1;
end

logic [2 * WIDTH-1:0]dout_exp;
logic [WIDTH-1:0]remainder_exp;
initial begin
{dividend,divisor,din_valid} ='b0;
forever begin
@(negedge clk);
dividend = (2 * WIDTH)'($urandom_range(0,2 ** (2 * WIDTH))); divisor = (WIDTH)'($urandom_range(1,2 ** WIDTH-1));
din_valid = 1'b1;

remainder_exp = dividend% divisor;
dout_exp = (dividend-remainder_exp)/divisor;

repeat(5 * WIDTH) begin
@(negedge clk);
din_valid ='b0;
end
if((remainder == remainder_exp) && (dout_exp == dout)) begin
$display("successfully"); end else begin$display("failed");
\$stop;
end
end
end

endmodule
Reference: https://cloud.tencent.com/developer/article/1110618 does not restore the remainder divider-Cloud + Community-Tencent Cloud