 Last visit was: Sun Jan 23, 2022 4:58 am It is currently Sun Jan 23, 2022 4:58 am

 Page 1 of 1 [ 2 posts ]
Divide Algorithm - Binary Search
Author Message

Joined: Sat Feb 02, 2013 9:40 am
Posts: 1576  Divide Algorithm - Binary Search
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) 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

_________________
Robert Finch http://www.finitron.ca

Tue Feb 06, 2018 5:58 pm Joined: Wed Jan 09, 2013 6:54 pm
Posts: 1666  Re: Divide Algorithm - Binary Search
It's a topic worthy of exploration! The wikipedia article on division has some good links.

"While addition and multiplication implementations have become increasingly efficient, division and square root support has remained uneven. There is a considerable variation in the types of algorithms employed, as well as the quality and performance of the implementations. This situation originates in skepticism about the importance of division and square root, and an insufficient understanding of the design alternatives... as the latency gap grows between addition and multiplication on the one hand and divide/square root on the other, the latter increasingly become performance bottlenecks."

Attachment:
Division-Soderquist-Leeser.png

You do not have the required permissions to view the files attached to this post.

Wed Feb 07, 2018 11:26 am
 Page 1 of 1 [ 2 posts ]

Who is online

Users browsing this forum: CCBot and 0 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

 Jump to:  Select a forum ------------------ General Discussions Newbies Software    General programming    Languages and tools    Kernels and operating systems Hardware    Hardware in general    CPU/MCU choices and designs    Implementation and Construction Programmable logic Simulation and emulation Nostalgia Projects Anycpu.org