View unanswered posts | View active topics It is currently Thu Mar 28, 2024 9:40 pm



Reply to topic  [ 2 posts ] 
 Divide Algorithm - Binary Search 
Author Message

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

[/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

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


Tue Feb 06, 2018 5:58 pm
Profile WWW

Joined: Wed Jan 09, 2013 6:54 pm
Posts: 1780
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."

Attachment:
Division-Soderquist-Leeser.png
Division-Soderquist-Leeser.png [ 81.98 KiB | Viewed 3721 times ]


Wed Feb 07, 2018 11:26 am
Profile
Display posts from previous:  Sort by  
Reply to topic   [ 2 posts ] 

Who is online

Users browsing this forum: No registered users and 2 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

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