From: eyals@hywire.com (Eyal Shachrai) Newsgroups: comp.arch.fpga Subject: divide by 5 Date: 3 Jun 2002 08:53:08 -0700 Organization: http://groups.google.com/ Lines: 4 Message-ID: <70029bf5.0206030753.79ed5416@posting.google.com> NNTP-Posting-Host: 192.116.227.170 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: posting.google.com 1023119589 14517 127.0.0.1 (3 Jun 2002 15:53:09 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: 3 Jun 2002 15:53:09 GMT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.imp.ch!news.imp.ch!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!news-hog.berkeley.edu!ucberkeley!newsfeed.stanford.edu!postnews1.google.com!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:18049 does anyone know of an elegant way to divide a number of 21 bits by 5 ? please note that I'm using xilinx's virtex 2 and mentor's leonardo for synthesys. ###### From: Christopher.Saunter@durham.ac.uk (Christopher Saunter) Newsgroups: comp.arch.fpga Subject: Re: divide by 5 Date: Mon, 3 Jun 2002 17:57:33 +0000 (UTC) Organization: University of Durham, Durham, UK Lines: 46 Message-ID: References: <70029bf5.0206030753.79ed5416@posting.google.com> NNTP-Posting-Host: deneb.dur.ac.uk X-Trace: sirius.dur.ac.uk 1023127053 29252 129.234.4.80 (3 Jun 2002 17:57:33 GMT) X-Complaints-To: usenet@durham.ac.uk NNTP-Posting-Date: Mon, 3 Jun 2002 17:57:33 +0000 (UTC) X-Newsreader: TIN [version 1.2 PL2] Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!newsfeeder.edisontel.com!fu-berlin.de!server1.netnews.ja.net!server5.netnews.ja.net!nntphost.dur.ac.uk!deneb.dur.ac.uk!dph1cds Xref: chonsp.franklin.ch comp.arch.fpga:18045 Eyal Shachrai (eyals@hywire.com) wrote: : does anyone know of an elegant way to divide a number : of 21 bits by 5 ? Eyal, I've outlined the way I do this for various fixed divisors below, I hope it is usefull. I also hope I am not doing this in some silly way... How precise do you need the result to be? Is the divisor fixed at 5? If the divisor is fixed, you are better of thinking of the operation as a 'multiply by 1/5.' rather than a 'divide by 5' If this is the case, you can do the 'divide' as a multiply by 0.2, which you can decompose into a series of bit shifts (not really existant in an FPGA...) and additions. 0.2*X can be aproximated to within ~ 0.02% as x/8 + x/16 + x/128 + x/256 + x/2048 + x/4096. I am doing something similar on data with a highish data rate (~100MHz). If it is hard to meet the timing requirements of your design adding all 6 signals in one colck cycle, the additions can be performed in pairs, pipelined. (how I am doing it) If you have a lower speed reqirement, you could use bit serial arithmetic, which would result in a highly reduced logic usage. This may be a daft question, but are you sure you can't just divide by 4 and compensate somewhere else? Probably not! Also, I note you are using a Virtex-II - this leads me on to a question / idea..... I am working on something where a low latency divider (<10cycles) with variable coeficients (a/b) could be a 'magic bullet' - b is ~ 16 bits wide, a~10. Is there any reason I can't use the embeded multiplier, connected to a BlockRAM acting as a look up table for the coefficients to convert a divider of X into a multiplier of 1/X. I understand this will have serious scaling issues as the number of bits of acuracy required by 'b' rises mind... If you have a situation of a/b, where a has a high data rate, and b changes infrequently, perhaps c=1/b could be generated with bit serial arithmetic, and a fast parallel multiplier used to calculate a*c. Comments appreciated! Regards, Chris Saunter ###### From: "Kevin Neilson" Newsgroups: comp.arch.fpga References: <70029bf5.0206030753.79ed5416@posting.google.com> Subject: Re: divide by 5 Lines: 32 X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2600.0000 X-MIMEOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 Message-ID: NNTP-Posting-Host: 12.253.117.91 X-Complaints-To: abuse@attbi.com X-Trace: rwcrnsc52.ops.asp.att.net 1023128019 12.253.117.91 (Mon, 03 Jun 2002 18:13:39 GMT) NNTP-Posting-Date: Mon, 03 Jun 2002 18:13:39 GMT Organization: AT&T Broadband Date: Mon, 03 Jun 2002 18:13:39 GMT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.imp.ch!news.imp.ch!nntp-out.monmouth.com!newspeer.monmouth.com!newsfeed.mathworks.com!wn3feed!worldnet.att.net!204.127.198.204!attbi_feed4!attbi.com!rwcrnsc52.ops.asp.att.net.POSTED!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:18056 I don't know if there's an elegant solution, because you need to multiply by 1/5, which is a number that can't be represented exactly in a binary number of finite digits (I don't think). However, 51/256ths is pretty close: 0.1992. When this is expressed in binary, it is 0.0110011, which has only four ones so you can do the multiplication with four shifted adds (if you don't have a multiplier). So the optimized code would look something like: wire [20:0] in; // number to be divided wire [20:0] result = (in + (in<<1) + (in<<4) + (in<<5)) >> 8; The right shift is to get the radix point in the correct place. As an example, we'll try 21: 21 + 42 + 336 + 672 >> 8 = 1071 >> 8 = 4.18. Since we made the result an integer, the result would be rounded and only the '4' would be retained. You can keep some fraction if you like. You can pipeline the adders too, for more speed. -Kevin "Eyal Shachrai" wrote in message news:70029bf5.0206030753.79ed5416@posting.google.com... > does anyone know of an elegant way to divide a number > of 21 bits by 5 ? > please note that I'm using xilinx's virtex 2 > and mentor's leonardo for synthesys. ###### Message-ID: <3CFBDE80.B4A28FB6@mail.com> From: John_H X-Mailer: Mozilla 4.75 [en]C-CCK-MCD (Win95; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: divide by 5 References: <70029bf5.0206030753.79ed5416@posting.google.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 40 Date: Mon, 03 Jun 2002 21:24:15 GMT NNTP-Posting-Host: 192.65.17.17 X-Complaints-To: postmaster@opbu.xerox.com X-Trace: news-west.eli.net 1023139455 192.65.17.17 (Mon, 03 Jun 2002 15:24:15 MDT) NNTP-Posting-Date: Mon, 03 Jun 2002 15:24:15 MDT Organization: Xerox Officeprinting NewsReader Service Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!cyclone.bc.net!logbridge.uoregon.edu!news-west.eli.net!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:18061 You can do serial division if you can spend a few cycles getting your answer. If you need the results pipelines, multiply by 1/5. Since the fraction is a little more than 20'h33333 / 21'h100000, you can do some addition stages. To account for the rounding problems 1) if truncating the accumulator and 2) for the fraction resolution you need to make some adjustments. You can play with the number to figure out a "best fit". Since you probably need at least 18 bits you'd need a minimum of 3 additions making a 32 bit equivalent fraction just as easy to implement. I've had trouble getting a balance between truncating the adders mid-stream and rounding but the following scheme appears to work. In Verilog, some of the elements might look like: input [20:0] in; reg [22:0] x3; reg [26:0] x33; reg [21:0] x3333; reg [18:0] result; always @(clk) begin x3 <= (in<<1) + in; x33 <= (x3<<4) + x3; x3333 <= (x33 + (x33>>8)) >> 13; result <= (x3333 + (x3333>>16) + 1) >> 3; end Eyal Shachrai wrote: > does anyone know of an elegant way to divide a number > of 21 bits by 5 ? > please note that I'm using xilinx's virtex 2 > and mentor's leonardo for synthesys. ###### From: john.l.smith@titan.com (John) Newsgroups: comp.arch.fpga Subject: Re: divide by 5 Date: 3 Jun 2002 16:57:43 -0700 Organization: http://groups.google.com/ Lines: 88 Message-ID: <5b9931fd.0206031557.3502685b@posting.google.com> References: <70029bf5.0206030753.79ed5416@posting.google.com> <3CFBB6A3.59598A79@xilinx.com> NNTP-Posting-Host: 199.254.9.224 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: posting.google.com 1023148664 6688 127.0.0.1 (3 Jun 2002 23:57:44 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: 3 Jun 2002 23:57:44 GMT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news-ge.switch.ch!deine.net!news-out.nuthinbutnews.com!propagator-sterling!news-in.nuthinbutnews.com!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed.stanford.edu!postnews1.google.com!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:18113 A slightly simpler approach may be to notice that 1/5 = 3/16 + 3/256 + 3/4096 + ... 3/(2^(4n))... = .0011001100110011001100110011001100110011.... ---- -------- ---------------- -------------------------------- ---------------------------------------------------------------- First approximation is 3/16, a shift, add, and a shift. Take result, shift down by four and add again, this gives 8 bits precision. Take result, shift down by eight, add again, 16 bits of precision. Take result, shift down by sixteen, add again, 32 bits of precision. Thus Four adds => 32-bits of precision Five adds => 64 bits ... This is a general technique that can be used for _any_ _fixed_ divisor, as there is always a repeating pattern... 1/5 is nice illustrative case, 1/3 and 1/7 also work well. HTH Austin Lesea wrote in message news:<3CFBB6A3.59598A79@xilinx.com>... > Kevin, > > I think at 21 bits resolution, this is a really big error > (0.02...)......but...... > > I thought of using Newton's method, whereby you initially "guess" by shifting > the 21 bit number to the right (divide by four), and then subtract another > shifted value (divide by 8). > > (Your first guess could be just 1/4 the original value). > > The first guess is then multiplied by 5 (easy to do, shift by two to the left > (X4) and add to the original guess). If it is larger, you shift the guess by > two right (divide) and add or subtract from the orgginal guess (save the new > add/sub value), and repeat the mult by 5. Also save the running corrected guess > (which at the end is the answer). > > At each compare, you continue to divide the add/sub value by 2, getting closer > to the final answer. > > At each successive compare, you are converging on the solution. After 20 > cycles, you have converged on the answer to the required 21 bits of resolution. > > I think this is 21 cycles, each cycle is a two shifts, add, compare, two shifts, > then add or subtract. If each operation takes a clock cycle, that is 7*21 > clocks. I am sure with some pipelining it can be done in less. > > Austin > > Kevin Neilson wrote: > > > I don't know if there's an elegant solution, because you need to multiply by > > 1/5, which is a number that can't be represented exactly in a binary number > > of finite digits (I don't think). However, 51/256ths is pretty close: > > 0.1992. When this is expressed in binary, it is 0.0110011, which has only > > four ones so you can do the multiplication with four shifted adds (if you > > don't have a multiplier). > > > > So the optimized code would look something like: > > > > wire [20:0] in; // number to be divided > > wire [20:0] result = (in + (in<<1) + (in<<4) + (in<<5)) >> 8; > > > > The right shift is to get the radix point in the correct place. As an > > example, we'll try 21: > > 21 + 42 + 336 + 672 >> 8 > > = 1071 >> 8 = 4.18. > > > > Since we made the result an integer, the result would be rounded and only > > the '4' would be retained. You can keep some fraction if you like. You can > > pipeline the adders too, for more speed. > > > > -Kevin > > > > "Eyal Shachrai" wrote in message > > news:70029bf5.0206030753.79ed5416@posting.google.com... > > > does anyone know of an elegant way to divide a number > > > of 21 bits by 5 ? > > > please note that I'm using xilinx's virtex 2 > > > and mentor's leonardo for synthesys. ###### From: "Kevin Neilson" Newsgroups: comp.arch.fpga References: <70029bf5.0206030753.79ed5416@posting.google.com> <3CFBB6A3.59598A79@xilinx.com> <5b9931fd.0206031557.3502685b@posting.google.com> Subject: Re: divide by 5 Lines: 113 X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2600.0000 X-MIMEOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 Message-ID: NNTP-Posting-Host: 12.253.117.91 X-Complaints-To: abuse@attbi.com X-Trace: sccrnsc02 1023149661 12.253.117.91 (Tue, 04 Jun 2002 00:14:21 GMT) NNTP-Posting-Date: Tue, 04 Jun 2002 00:14:21 GMT Organization: AT&T Broadband Date: Tue, 04 Jun 2002 00:14:21 GMT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed1.cidera.com!Cidera!cyclone1.gnilink.net!wn1feed!worldnet.att.net!204.127.198.204!attbi_feed4!attbi_feed3!attbi.com!sccrnsc02.POSTED!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:18068 That's pretty smooth. "John" wrote in message news:5b9931fd.0206031557.3502685b@posting.google.com... > A slightly simpler approach may be to notice that > > 1/5 = 3/16 + 3/256 + 3/4096 + ... 3/(2^(4n))... > > = .0011001100110011001100110011001100110011.... > ---- > -------- > ---------------- > -------------------------------- > ---------------------------------------------------------------- > > First approximation is 3/16, a shift, add, and a shift. > > Take result, shift down by four and add again, this gives 8 bits precision. > Take result, shift down by eight, add again, 16 bits of precision. > Take result, shift down by sixteen, add again, 32 bits of precision. > > Thus Four adds => 32-bits of precision > > Five adds => 64 bits ... > > This is a general technique that can be used for _any_ > _fixed_ divisor, as there is always a repeating pattern... > 1/5 is nice illustrative case, 1/3 and 1/7 also work well. > HTH > > > Austin Lesea wrote in message news:<3CFBB6A3.59598A79@xilinx.com>... > > Kevin, > > > > I think at 21 bits resolution, this is a really big error > > (0.02...)......but...... > > > > I thought of using Newton's method, whereby you initially "guess" by shifting > > the 21 bit number to the right (divide by four), and then subtract another > > shifted value (divide by 8). > > > > (Your first guess could be just 1/4 the original value). > > > > The first guess is then multiplied by 5 (easy to do, shift by two to the left > > (X4) and add to the original guess). If it is larger, you shift the guess by > > two right (divide) and add or subtract from the orgginal guess (save the new > > add/sub value), and repeat the mult by 5. Also save the running corrected guess > > (which at the end is the answer). > > > > At each compare, you continue to divide the add/sub value by 2, getting closer > > to the final answer. > > > > At each successive compare, you are converging on the solution. After 20 > > cycles, you have converged on the answer to the required 21 bits of resolution. > > > > I think this is 21 cycles, each cycle is a two shifts, add, compare, two shifts, > > then add or subtract. If each operation takes a clock cycle, that is 7*21 > > clocks. I am sure with some pipelining it can be done in less. > > > > Austin > > > > Kevin Neilson wrote: > > > > > I don't know if there's an elegant solution, because you need to multiply by > > > 1/5, which is a number that can't be represented exactly in a binary number > > > of finite digits (I don't think). However, 51/256ths is pretty close: > > > 0.1992. When this is expressed in binary, it is 0.0110011, which has only > > > four ones so you can do the multiplication with four shifted adds (if you > > > don't have a multiplier). > > > > > > So the optimized code would look something like: > > > > > > wire [20:0] in; // number to be divided > > > wire [20:0] result = (in + (in<<1) + (in<<4) + (in<<5)) >> 8; > > > > > > The right shift is to get the radix point in the correct place. As an > > > example, we'll try 21: > > > 21 + 42 + 336 + 672 >> 8 > > > = 1071 >> 8 = 4.18. > > > > > > Since we made the result an integer, the result would be rounded and only > > > the '4' would be retained. You can keep some fraction if you like. You can > > > pipeline the adders too, for more speed. > > > > > > -Kevin > > > > > > "Eyal Shachrai" wrote in message > > > news:70029bf5.0206030753.79ed5416@posting.google.com... > > > > does anyone know of an elegant way to divide a number > > > > of 21 bits by 5 ? > > > > please note that I'm using xilinx's virtex 2 > > > > and mentor's leonardo for synthesys. ###### Message-ID: <3CFC0EE0.177E@designtools.co.nz> From: Jim Granville Reply-To: jim.granville@designtools.co.nz Organization: Mandeno Granville elect X-Mailer: Mozilla 3.0C-XTRA (Win95; I) MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: divide by 5 References: <70029bf5.0206030753.79ed5416@posting.google.com> <3CFBB6A3.59598A79@xilinx.com> <5b9931fd.0206031557.3502685b@posting.google.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 9 Date: Tue, 04 Jun 2002 12:50:40 +1200 NNTP-Posting-Host: 203.79.102.182 X-Complaints-To: abuse@tsnz.net X-Trace: news02.tsnz.net 1023151906 203.79.102.182 (Tue, 04 Jun 2002 12:51:46 NZST) NNTP-Posting-Date: Tue, 04 Jun 2002 12:51:46 NZST Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.imp.ch!news.imp.ch!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!xmission!news-out.spamkiller.net!propagator2-maxim!propagator-maxim!news-in.spamkiller.net!news02.tsnz.net!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:18097 John wrote: > > A slightly simpler approach may be to notice that > > 1/5 = 3/16 + 3/256 + 3/4096 + ... 3/(2^(4n))... Impressive. Just how did you 'notice' that ? -jg ###### From: "Steve Casselman" Newsgroups: comp.arch.fpga References: <70029bf5.0206030753.79ed5416@posting.google.com> <3cfbf038@news.svn.net> Subject: Re: divide by 5 Lines: 25 Organization: Virtual Computer Corporation X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 5.00.3018.1300 X-MIMEOLE: Produced By Microsoft MimeOLE V5.00.3018.1300 Message-ID: NNTP-Posting-Host: 64.168.189.229 X-Complaints-To: abuse@prodigy.net X-Trace: newssvr21.news.prodigy.com 1023164726 ST000 64.168.189.229 (Tue, 04 Jun 2002 00:25:26 EDT) NNTP-Posting-Date: Tue, 04 Jun 2002 00:25:26 EDT X-UserInfo1: FKPO@SNEPJWWCTLXXJKDM^P@VZ\LPCXLLBWLOOAF@YUDUWYAKVUOPCW[ML\JXUCKVFDYZKBMSFX^OMSAFNTINTDDMVW[X\THOPXZRVOCJTUTPC\_JSBVX\KAOTBAJBVMZTYAKMNLDI_MFDSSOLXINH__FS^\WQGHGI^C@E[A_CF\AQLDQ\BTMPLDFNVUQ_VM Date: Tue, 04 Jun 2002 04:25:26 GMT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.imp.ch!news.imp.ch!newsfeed.vmunix.org!newsfeed.stueberl.de!teaser.fr!noos.fr!proxad.net!skynet.be!skynet.be!prodigy.com!newsmst01.news.prodigy.com!prodigy.com!postmaster.news.prodigy.com!newssvr21.news.prodigy.com.POSTED!2ac7f5fa!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:18064 One way to do this might be to use one or two of the block rams for a lookup table to get a first approximation. Then use the arithmetic techniques. Steve Casselman "James Horn" wrote in message news:3cfbf038@news.svn.net... > Without multiplying per se, consider that to 32 bits, 1/5=858993459/2^32 > (rounded). The numerator is 3 * 17 * 257 * 65537. Each of these factors > has two non-zero bits. So you get: > n := n + (n<<1); > n := n + (n<<4); > n := n + (n<<8); > n := n + (n<<16); > return n>>32; > > Of course, rounding and moving the final shift to among the prior four can > make for a smaller implimentation. But that's essentially 4 pipelined > adders. > > Jim Horn ###### From: John_H Newsgroups: comp.arch.fpga Subject: Re: divide by 5 Date: Mon, 03 Jun 2002 21:49:41 -0700 Organization: Posted via Supernews, http://www.supernews.com Message-ID: <3CFC46E5.AA88ABF9@mail.com> X-Mailer: Mozilla 4.73 [en] (Win98; U) X-Accept-Language: en MIME-Version: 1.0 References: <70029bf5.0206030753.79ed5416@posting.google.com> <3CFBB6A3.59598A79@xilinx.com> <5b9931fd.0206031557.3502685b@posting.google.com> <3CFC0EE0.177E@designtools.co.nz> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Complaints-To: newsabuse@supernews.com Lines: 15 Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.imp.ch!news.imp.ch!newsfeed.vmunix.org!newsfeed.online.be!sn-xit-01!sn-post-01!supernews.com!corp.supernews.com!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:18127 What's 1/5 in hex? Grab MS Calculator. (DEC) 2^32/5 -> HEX -> 33333333. Jim Granville wrote: > > John wrote: > > > > A slightly simpler approach may be to notice that > > > > 1/5 = 3/16 + 3/256 + 3/4096 + ... 3/(2^(4n))... > > Impressive. Just how did you 'notice' that ? > > -jg ###### Message-ID: <3CFC89ED.FEC72059@algor.co.uk> From: Rick Filipkiewicz X-Mailer: Mozilla 4.75 [en] (WinNT; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: divide by 5 References: <70029bf5.0206030753.79ed5416@posting.google.com> <3CFBB6A3.59598A79@xilinx.com> <5b9931fd.0206031557.3502685b@posting.google.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Organization: Algorithmics Ltd. Cache-Post-Path: mudchute.algor.co.uk!unknown@rfhome.algor.co.uk X-Cache: nntpcache 2.4.0b2 (see http://www.nntpcache.org/) Lines: 42 Date: Tue, 04 Jun 2002 10:35:41 +0100 NNTP-Posting-Host: 62.254.210.251 X-Complaints-To: abuse@ntlworld.com X-Trace: news6-win.server.ntlworld.com 1023183346 62.254.210.251 (Tue, 04 Jun 2002 10:35:46 BST) NNTP-Posting-Date: Tue, 04 Jun 2002 10:35:46 BST Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.imp.ch!news.imp.ch!newsfeed.vmunix.org!newsfeed.stueberl.de!newspeer1-gui.server.ntli.net!ntli.net!news6-win.server.ntlworld.com.POSTED!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:18086 John wrote: > A slightly simpler approach may be to notice that > > 1/5 = 3/16 + 3/256 + 3/4096 + ... 3/(2^(4n))... > > = .0011001100110011001100110011001100110011.... > ---- > -------- > ---------------- > -------------------------------- > ---------------------------------------------------------------- > > First approximation is 3/16, a shift, add, and a shift. > > Take result, shift down by four and add again, this gives 8 bits precision. > Take result, shift down by eight, add again, 16 bits of precision. > Take result, shift down by sixteen, add again, 32 bits of precision. > > Thus Four adds => 32-bits of precision > > Five adds => 64 bits ... > > This is a general technique that can be used for _any_ > _fixed_ divisor, as there is always a repeating pattern... > 1/5 is nice illustrative case, 1/3 and 1/7 also work well. > HTH > > Nice find. If I've got my maths right in general 1/N can be expressed as a repeating pattern in radix 2**r if there is a K such that N * K = 2**r -1 so N = 11 works with K = 93, r = 10. Is it always possible to do this ? ###### Message-ID: <3CFCB4D6.7D777436@andraka.com> From: Ray Andraka Organization: Andraka Consulting Group, Inc X-Mailer: Mozilla 4.77 [en] (WinNT; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: divide by 5 References: <70029bf5.0206030753.79ed5416@posting.google.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 41 Date: Tue, 04 Jun 2002 12:35:48 GMT NNTP-Posting-Host: 68.15.41.165 X-Complaints-To: abuse@cox.net X-Trace: news1.east.cox.net 1023194148 68.15.41.165 (Tue, 04 Jun 2002 08:35:48 EDT) NNTP-Posting-Date: Tue, 04 Jun 2002 08:35:48 EDT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.imp.ch!news.imp.ch!newsfeed.vmunix.org!newsfeed.stueberl.de!cox.net!news1.east.cox.net.POSTED!53ab2750!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:18082 How accurate do you need? One possibility is to multiply by the reciprocal. In this case, the reciprocal has a nice repeating bit pattern (common for 1/N's): 11001100... If you are multiplying by this, you can get an effective multiply by a 32 bit representation of 1/5 using just 4 adders, with more accuracy than you have on the 21 bit input. If you can get by with a 16 bit representation, you only need 3 adds. if the input is a then b<= (a + 2a)/16 =3a (1100) c<= b + 16b = 17b = 51a (11001100) d<= c + 256c = 257c = 13107a (1100110011001100) e<= d + 65536d = 65537d = 858993459a (11001100110011001100110011001100) 858993459/(2^32) =0.19999999995, Eyal Shachrai wrote: > does anyone know of an elegant way to divide a number > of 21 bits by 5 ? > please note that I'm using xilinx's virtex 2 > and mentor's leonardo for synthesys. -- --Ray Andraka, P.E. President, the Andraka Consulting Group, Inc. 401/884-7930 Fax 401/884-7950 email ray@andraka.com http://www.andraka.com "They that give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." -Benjamin Franklin, 1759 ###### Message-ID: <3CFCDFF0.3CB14FB5@mail.com> From: John_H X-Mailer: Mozilla 4.75 [en]C-CCK-MCD (Win95; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: divide by 5 References: <70029bf5.0206030753.79ed5416@posting.google.com> <3CFBB6A3.59598A79@xilinx.com> <5b9931fd.0206031557.3502685b@posting.google.com> <3CFC89ED.FEC72059@algor.co.uk> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 27 Date: Tue, 04 Jun 2002 15:42:32 GMT NNTP-Posting-Host: 192.65.17.17 X-Complaints-To: postmaster@opbu.xerox.com X-Trace: news-west.eli.net 1023205352 192.65.17.17 (Tue, 04 Jun 2002 09:42:32 MDT) NNTP-Posting-Date: Tue, 04 Jun 2002 09:42:32 MDT Organization: Xerox Officeprinting NewsReader Service Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!cyclone.bc.net!logbridge.uoregon.edu!news-west.eli.net!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:18128 Think of it in the "other" base of decimal. The reason we get the repeats is that we end up at some point in our long division with a remainder of 1 when we do 1/N. with 1/7 you will repeat a sequence of 7 digits. For a given N you'll always end up with either an even fraction (1/8 for instance) or you'll get the remainder of 1 within N digits, whether those digits are decimal, hex, or binary. look at 1/7 for binary (just for kicks) _____ 111)1 000 - 111 1 That was quick! 1/7 in fractional binary is 0.001001001... The repeat is every 3 bits. Rick Filipkiewicz wrote: > Nice find. > > If I've got my maths right in general 1/N can be expressed as a repeating pattern in radix 2**r if > there is a K such that > > N * K = 2**r -1 > > so N = 11 works with K = 93, r = 10. Is it always possible to do this ? ###### From: john.l.smith@titan.com (John) Newsgroups: comp.arch.fpga Subject: Re: divide by 5 Date: 4 Jun 2002 12:22:27 -0700 Organization: http://groups.google.com/ Lines: 33 Message-ID: <5b9931fd.0206041122.52d44df7@posting.google.com> References: <70029bf5.0206030753.79ed5416@posting.google.com> <3CFBB6A3.59598A79@xilinx.com> <5b9931fd.0206031557.3502685b@posting.google.com> <3CFC89ED.FEC72059@algor.co.uk> NNTP-Posting-Host: 199.254.9.224 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: posting.google.com 1023218548 25405 127.0.0.1 (4 Jun 2002 19:22:28 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: 4 Jun 2002 19:22:28 GMT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!cyclone.bc.net!newsfeed.stanford.edu!postnews1.google.com!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:18118 Rick Filipkiewicz wrote in message news:<3CFC89ED.FEC72059@algor.co.uk>... > John wrote: Same as others when I saw no one had yet posted the recursive method ... > Nice find. > > If I've got my maths right in general 1/N can be expressed as a repeating pattern in radix 2**r if > there is a K such that > > N * K = 2**r -1 > > so N = 11 works with K = 93, r = 10. Is it always possible to do this ? Every rational number can be expressed as a repeating expansion ( I recall from the dimness of a high school math course, don't ask me to dig deep and prove it, I just build the stuff now ) 1/11 is an interesting case, the repeating pattern is .0001011101 0001011101 0001011101 0001011101 ... Here the sequence would start with two subtractions to give the first 10 bits precision, ( 1/8 - 1/32 - 1/1024) then the shifts/adds give 20, 40, 80 bits precision... it converges faster than 1/5 when the base pattern is properly Booth re-coded. I wonder if anyone has a table for optimum fixed divisor encoding? It would make a nice app note... I think someone referred to this as "Russian recursive division", but would be hard pressed to find a reference. A Google search for "Russian division" doesn't work. ###### From: john.l.smith@titan.com (John) Newsgroups: comp.arch.fpga Subject: Re: divide by 5 Date: 4 Jun 2002 20:35:12 -0700 Organization: http://groups.google.com/ Lines: 39 Message-ID: <5b9931fd.0206041935.721ac188@posting.google.com> References: <70029bf5.0206030753.79ed5416@posting.google.com> <3CFBB6A3.59598A79@xilinx.com> <5b9931fd.0206031557.3502685b@posting.google.com> <3CFC89ED.FEC72059@algor.co.uk> <5b9931fd.0206041122.52d44df7@posting.google.com> NNTP-Posting-Host: 199.254.9.224 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: posting.google.com 1023248112 10034 127.0.0.1 (5 Jun 2002 03:35:12 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: 5 Jun 2002 03:35:12 GMT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!newsfeed.icl.net!iad-peer.news.verio.net!news.verio.net!news.maxwell.syr.edu!newsfeed.stanford.edu!postnews1.google.com!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:18116 john.l.smith@titan.com (John) wrote in message news:<5b9931fd.0206041122.52d44df7@posting.google.com>... > Rick Filipkiewicz wrote in message news:<3CFC89ED.FEC72059@algor.co.uk>... > > John wrote: > Same as others when I saw no one had yet > posted the recursive method ... > > > Nice find. > > > > If I've got my maths right in general 1/N can be expressed as a repeating pattern in radix 2**r if > > there is a K such that > > > > N * K = 2**r -1 > > > > so N = 11 works with K = 93, r = 10. Is it always possible to do this ? > > Every rational number can be expressed as a repeating expansion > ( I recall from the dimness of a high school math course, don't > ask me to dig deep and prove it, I just build the stuff now ) > > 1/11 is an interesting case, the repeating pattern is > > .0001011101 0001011101 0001011101 0001011101 ... > > Here the sequence would start with two subtractions > to give the first 10 bits precision, ( 1/8 - 1/32 - 1/1024) > then the shifts/adds give 20, 40, 80 bits precision... > it converges faster than 1/5 when the base pattern is > properly Booth re-coded. Ooops- THREE subtractions: (1/8 - 1/1024 - 1/512 - 1/32 ) so it isn't any faster than the smaller divisors. > I wonder if anyone has a > table for optimum fixed divisor encoding? > It would make a nice app note... > > I think someone referred to this as "Russian recursive > division", but would be hard pressed to find a reference. > A Google search for "Russian division" doesn't work. ###### Message-ID: <3CFDE5B4.3256F7B9@algor.co.uk> From: Rick Filipkiewicz X-Mailer: Mozilla 4.75 [en] (WinNT; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: divide by 5 References: <70029bf5.0206030753.79ed5416@posting.google.com> <3CFBB6A3.59598A79@xilinx.com> <5b9931fd.0206031557.3502685b@posting.google.com> <3CFC89ED.FEC72059@algor.co.uk> <5b9931fd.0206041122.52d44df7@posting.google.com> <5b9931fd.0206041935.721ac188@posting.google.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Organization: Algorithmics Ltd. Cache-Post-Path: mudchute.algor.co.uk!unknown@rfhome.algor.co.uk X-Cache: nntpcache 2.4.0b2 (see http://www.nntpcache.org/) Lines: 39 Date: Wed, 05 Jun 2002 11:19:32 +0100 NNTP-Posting-Host: 62.254.210.251 X-Complaints-To: abuse@ntlworld.com X-Trace: news6-win.server.ntlworld.com 1023272377 62.254.210.251 (Wed, 05 Jun 2002 11:19:37 BST) NNTP-Posting-Date: Wed, 05 Jun 2002 11:19:37 BST Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.imp.ch!news.imp.ch!eusc.inter.net!newsfeed01.sul.t-online.de!t-online.de!newspeer1-gui.server.ntli.net!ntli.net!news6-win.server.ntlworld.com.POSTED!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:18080 John wrote: > > > > > Every rational number can be expressed as a repeating expansion > > ( I recall from the dimness of a high school math course, don't > > ask me to dig deep and prove it, I just build the stuff now ) > > > > 1/11 is an interesting case, the repeating pattern is > > > > In fact the true statement is that the expansion of any rational number to any radix is either finite or *eventually* drops into a repeated pattern (since there are only r possible remainders for radix = r). However there will in general be an initial digit sequence before the periodicity starts. To show that the binary expansion of 1/N for N odd is always purely periodic you just have to note that for all possible exponents E there are only N possible remainders (2**E - 1) % N. Choose 2 exponents E1 < E2 with the same remainder R: 2**E1 - 1 = N * K1 + R 2**E2 - 1 = N * K2 + R Then (2**E1) * (2**(E2-E1) - 1) = N * (K2 - K1) Since N is odd we must have 2**E1 dividing (K2 - K1) => N divides (2**(E2-E1) - 1). Which is what we wanted. [works for radixes (radices ? radixen ?) that are powers of a prime p and N%p != 0]. For N even we have, for some E, N = (2**E) * M with M odd so the binary expansions of 1/N for even N are a number of 0's followed by a periodic pattern. e.g. 1/12 = .000101010101... ###### From: "Cyrille de Brébisson" Newsgroups: comp.arch.fpga Subject: Re: divide by 5 Date: Thu, 6 Jun 2002 12:02:04 -0600 Organization: SSO-IT, Hewlett-Packard Co. Lines: 60 Message-ID: References: <70029bf5.0206030753.79ed5416@posting.google.com> NNTP-Posting-Host: 41dhcp355.boi.hp.com X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2600.0000 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!nntp.abs.net!uunet!dca.uu.net!news.compaq.com!fc.hp.com!news.cup.hp.com!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:18158 Hello, on the HP calculators, they are doing division of 20 bits number by 5 by doing a multiplication by $333334h followed by a shift right of 24 bit. This is accurate for every possible 20 bit number but one (where there is a 0.00001% error). I guess it would be as good for a 21bit number. do you need exact accuracy? regards, cyrille "Christopher Saunter" wrote in message news:adgamd$si4$1@sirius.dur.ac.uk... > Eyal Shachrai (eyals@hywire.com) wrote: > : does anyone know of an elegant way to divide a number > : of 21 bits by 5 ? > > Eyal, > I've outlined the way I do this for various fixed divisors below, > I hope it is usefull. I also hope I am not doing this in some silly > way... > > How precise do you need the result to be? Is the divisor fixed at 5? > > If the divisor is fixed, you are better of thinking of the operation as a > 'multiply by 1/5.' rather than a 'divide by 5' > > If this is the case, you can do the 'divide' as a multiply by 0.2, which > you can decompose into a series of bit shifts (not really existant in an > FPGA...) and additions. 0.2*X can be aproximated to within ~ 0.02% as > x/8 + x/16 + x/128 + x/256 + x/2048 + x/4096. > > I am doing something similar on data with a highish data rate (~100MHz). > If it is hard to meet the timing requirements of your design adding all 6 > signals in one colck cycle, the additions can be performed in pairs, > pipelined. (how I am doing it) If you have a lower speed reqirement, you > could use bit serial arithmetic, which would result in a highly reduced > logic usage. > > This may be a daft question, but are you sure you can't just divide by 4 > and compensate somewhere else? Probably not! > > Also, I note you are using a Virtex-II - this leads me on to a question / > idea..... I am working on something where a low latency divider > (<10cycles) with variable coeficients (a/b) could be a 'magic bullet' - > b is ~ 16 bits wide, a~10. Is there any reason I can't use the embeded > multiplier, connected to a BlockRAM acting as a look up table for the > coefficients to convert a divider of X into a multiplier of 1/X. I > understand this will have serious scaling issues as the number of bits of > acuracy required by 'b' rises mind... > > If you have a situation of a/b, where a has a high data rate, and b > changes infrequently, perhaps c=1/b could be generated with bit serial > arithmetic, and a fast parallel multiplier used to calculate a*c. > > Comments appreciated! > > Regards, > Chris Saunter ###### From: kolja@bnl.gov (Kolja Sulimma) Newsgroups: comp.arch.fpga Subject: Re: divide by 5 Date: 8 Jun 2002 09:50:38 -0700 Organization: http://groups.google.com/ Lines: 13 Message-ID: <25c81abf.0206080850.25570568@posting.google.com> References: <70029bf5.0206030753.79ed5416@posting.google.com> NNTP-Posting-Host: 213.23.52.94 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: posting.google.com 1023555038 24470 127.0.0.1 (8 Jun 2002 16:50:38 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: 8 Jun 2002 16:50:38 GMT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!newsfeed.icl.net!news.maxwell.syr.edu!newsfeed.stanford.edu!postnews1.google.com!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:18231 > However, 51/256ths is pretty close: > 0.1992. When this is expressed in binary, it is 0.0110011, which has only > four ones so you can do the multiplication with four shifted adds (if you > don't have a multiplier). > > So the optimized code would look something like: > > wire [20:0] in; // number to be divided > wire [20:0] result = (in + (in<<1) + (in<<4) + (in<<5)) >> 8; Actually, you need only two adds: temp = in + (in<<1) result = (temp + (temp<<4)) >> 8