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 [ 81.98 KiB | Viewed 3796 times ] |
Page 1 of 1 | All times are UTC |
Powered by phpBB® Forum Software © phpBB Group http://www.phpbb.com/ |