AnyCPU
http://anycpu.org/forum/

Divide Algorithm - Binary Search
http://anycpu.org/forum/viewtopic.php?f=17&t=508
Page 1 of 1

Author:  robfinch [ Tue Feb 06, 2018 5:58 pm ]
Post subject:  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[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

Author:  BigEd [ Wed Feb 07, 2018 11:26 am ]
Post subject:  Re: Divide Algorithm - Binary Search

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 3784 times ]

Page 1 of 1 All times are UTC
Powered by phpBB® Forum Software © phpBB Group
http://www.phpbb.com/