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

 [ 2 posts ] 
 Divide Algorithm - Binary Search 
Author Message

Joined: Sat Feb 02, 2013 9:40 am
Posts: 1576
Location: Canada
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.


I have the following Verilog code example:
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)
   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;
      else if (a > b) begin
         minq <= 24'h0;
         maxq <= a;
         q1 = a >> 1;
      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;
   else begin
      q2 <= q1;
      if (d == 24'h0 || q1==q2) begin
         done <= 1'b1;
         q <= q1;
      else if (d[48]) begin   // d < 0
         // q is too big, choose a smaller q
         q1 <= (q1 + minq + 1) >> 1;
         maxq <= q1;
      else begin   // d > 0
         // q is too small, choose a larger q
         q1 <= (maxq + q1 + 1) >> 1;
         minq <= q1;


Robert Finch

Tue Feb 06, 2018 5:58 pm WWW

Joined: Wed Jan 09, 2013 6:54 pm
Posts: 1666
It's a topic worthy of exploration! The wikipedia article on division has some good links.

From Soderquist and Leeson (free pdf download):
"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."


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

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

Who is online

Users browsing this forum: CCBot and 0 guests

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

Jump to:  
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software