I’ve been searching the web and I can’t find information on using a binary search to find the quotient of a division. It's a pretty simple idea, and may be a few cycles faster than a regular long division. A lookup table can be used to determine an initial guess for the quotient (I haven't coded one yet), trimming a few cycles off the search. The search converges on the correct quotient, so it generates the equivalent of about 1 bit per clock cycle. It can terminate early if it finds a number for which the quotient is easily found.
[/code]
I have the following Verilog code example:
Code:
module fpBSDiv(clk, ld, a, b, q, done);
input clk;
input ld;
input [23:0] a;
input [23:0] b;
output reg [23:0] q;
output reg done;
reg [47:0] aa;
reg [23:0] q2 = 24'hFFFFFF;
reg [23:0] q1 = 0;
wire [48:0] d = aa - (q1 * b);
reg [23:0] minq = 24'h0, maxq=24'hFFFFFF;
reg [2:0] state;
reg [9:0] ndx;
always @(posedge clk)
begin
done <= 1'b0;
if (ld) begin
state <= 3'd1;
q2 <= 24'hFFFFFF;
aa <= {24'h0,a};
if (b==a) begin
q1 <= 24'h800000; // 1.0
q <= 24'h800000; // 1.0
done <= 1'b1;
end
else if (a > b) begin
minq <= 24'h0;
maxq <= a;
q1 = a >> 1;
end
else begin
ndx = {a[23:19],b[23:19]};
minq <= 24'h0;//tbl[{1'b0,ndx}];
maxq <= 24'hFFFFFF;//tbl[{1'b1,ndx}];
q1 <= 24'h7FFFFF;//(tbl[{1'b1,ndx}] + tbl[{1'b0,ndx}]) >> 1;
end
end
else begin
q2 <= q1;
if (d == 24'h0 || q1==q2) begin
done <= 1'b1;
q <= q1;
end
else if (d[48]) begin // d < 0
// q is too big, choose a smaller q
q1 <= (q1 + minq + 1) >> 1;
maxq <= q1;
end
else begin // d > 0
// q is too small, choose a larger q
q1 <= (maxq + q1 + 1) >> 1;
minq <= q1;
end
end
end
endmodule
