Site Home Archive Home FAQ Home How to search the Archive How to Navigate the Archive
Compare FPGA features and resources
Threads starting:
Authors:A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
In comp.arch.fpga Rob Gaddi <rgaddi@technologyhighland.invalid> wrote: (snip) > I'm trying to approximate either exp(-1/(n+1)) or 4^(-1/n+1). I can > convince myself I don't care which. n is an integer from 1-65535, and > the result should be fixed-point fractional, probably U0.18. The > function output is always between 0-1, and goes up like a rocket for > small n before leveling off to a steady cruise of >0.9 for the rest of > the function domain. You want an 18 bit function of a 16 bit input. Fits into one BRAM on most current, and not so current, FPGAs. Generate all 65536 values and store them in BRAM (ROM in verilog/VHDL terms). -- glenArticle: 156201
On Fri, 17 Jan 2014 11:00:06 -0800, Rob Gaddi wrote: > Hey y'all -- > > So this is one of those times that my lack of serious math chops is > coming round to bite me, and none of my usual books is helping me out. > I'm hoping someone has some thoughts. > > I'm trying to approximate either exp(-1/(n+1)) or 4^(-1/n+1). I can > convince myself I don't care which. n is an integer from 1-65535, and > the result should be fixed-point fractional, probably U0.18. The > function output is always between 0-1, and goes up like a rocket for > small n before leveling off to a steady cruise of >0.9 for the rest of > the function domain. > > I'm working in an FPGA, so I've got adds, multiplies, and table lookups > from tables of reasonable size (10s of kb) cheap, but other things > (divides especially) are expensive. I can throw several clock cycles at > the problem if need be. > > Taylor series attacks seem to fail horribly. I feel like there may be > some answer where answers for n in [1,127] gets a direct table lookup, > and n in [128,65535] gets some other algorithm, possibly with a table > boost. Or somehow taking advantage of the fact that log(1-f(n)) is > related to log(n)? > > Anyone have any thoughts? First, instead of Taylor's series, try a best-fit polynomial. I suspect you'll be nearly as disappointed, but you can try. Second, when best-fit polynomials let me down, I look to interpolation. Depending on the problem this ends up being somewhere between linear and cubic. You should be aware that for any one way of going from your tables of values to an interpolation, there's way more than one way of coming up with tables of values, some of which are better than others. Depending on how motivated you are you can either generate splines, or do a least-squares best fit, or find an overall minimax solution (minimize the maximum error). Note that this doesn't change the algorithm in your FPGA -- it just changes the values in your look-up tables. Formulating the problem as linear interpolation and using the known points, or formulating the problem as cubic splines and looking up the algorithm to generate your tables is probably the easiest if you've got the typical engineer's "jack of all trades" way with math. If you want to get fancier, then once you have the problem formulated, least-squares can be done with linear algebra on something like Scilab or Matlab in less time than it takes to lift your finger off the enter key. Getting a minimax solution requires more work both in formulating the problem and in waiting for the optimizer to finish. It also means you have to have a decent optimization software package (which Scilab comes with: I'm not sure if it's native to Matlab or if you have to buy yet another package). -- Tim Wescott Wescott Design Services http://www.wescottdesign.comArticle: 156202
On 17/01/14 20:00, Rob Gaddi wrote: > Hey y'all -- > > So this is one of those times that my lack of serious math chops is > coming round to bite me, and none of my usual books is helping me out. > I'm hoping someone has some thoughts. > > I'm trying to approximate either exp(-1/(n+1)) or 4^(-1/n+1). I can > convince myself I don't care which. n is an integer from 1-65535, and > the result should be fixed-point fractional, probably U0.18. The > function output is always between 0-1, and goes up like a rocket for > small n before leveling off to a steady cruise of >0.9 for the rest of > the function domain. > > I'm working in an FPGA, so I've got adds, multiplies, and table lookups > from tables of reasonable size (10s of kb) cheap, but other things > (divides especially) are expensive. I can throw several clock cycles > at the problem if need be. > > Taylor series attacks seem to fail horribly. I feel like there may be > some answer where answers for n in [1,127] gets a direct table lookup, > and n in [128,65535] gets some other algorithm, possibly with a table > boost. Or somehow taking advantage of the fact that log(1-f(n)) is > related to log(n)? > > Anyone have any thoughts? > Taylor series are great for the theory, but very rarely a useful calculation technique in practice. In a case like this, I would first look at using a single table - if you can afford the space, use it for simplicity. Failing that, draw a graph and look at the function as it changes. Also draw some graphs of the derivatives. Any areas of the function where you have low second derivatives are suitable for linear interpolation. Where you have high second derivatives, you need either tightly packed linear interpolation or cubic splines of some sort. There are a few different kinds of cubic splines, depending on things like smooth joins between the parts, least maximal errors, least total square error, etc. But for a limited range function like this, it is not unrealistic to get bit-perfect results if that is what you need. So once you have these graphs, you can look at linear interpolation with a fixed step size, linear interpolation with varying step size, cubic splines of some sort, or dividing the range up and using different techniques for different areas.Article: 156203
> > I'm trying to approximate either exp(-1/(n+1)) or 4^(-1/n+1). I can > > convince myself I don't care which. n is an integer from 1-65535, and > http://flopoco.gforge.inria.fr/ The "Generic fixed point function evaluators" might provide a solution. Caveat; I've played with some of the floating point stuff but not this bit. -AndyArticle: 156204
Just got this from production: https://dl.dropboxusercontent.com/u/53724080/PCBs/ASP_SN1_top.jpg from previously posted layout... https://dl.dropboxusercontent.com/u/53724080/PCBs/P344_15.jpg This is a pretty serious signal processor application, but dropping the Zed on there makes it easy. We can plug a USB logic analyzer directly onto that Mictor connector, which has 16 signals and a clock from the uZed. Rather than being cautious, I just plugged 24 volts into it, and the Zed lit up and ran Linux. -- John Larkin Highland Technology, Inc jlarkin att highlandtechnology dott com http://www.highlandtechnology.comArticle: 156205
David Brown <david.brown@hesbynett.no> writes: > On 17/01/14 20:00, Rob Gaddi wrote: >> Hey y'all -- >> >> So this is one of those times that my lack of serious math chops is >> coming round to bite me, and none of my usual books is helping me out. >> I'm hoping someone has some thoughts. >> >> I'm trying to approximate either exp(-1/(n+1)) or 4^(-1/n+1). I can >> convince myself I don't care which. n is an integer from 1-65535, and >> the result should be fixed-point fractional, probably U0.18. The >> function output is always between 0-1, and goes up like a rocket for >> small n before leveling off to a steady cruise of >0.9 for the rest of >> the function domain. >> >> I'm working in an FPGA, so I've got adds, multiplies, and table lookups >> from tables of reasonable size (10s of kb) cheap, but other things >> (divides especially) are expensive. I can throw several clock cycles >> at the problem if need be. >> >> Taylor series attacks seem to fail horribly. I feel like there may be >> some answer where answers for n in [1,127] gets a direct table lookup, >> and n in [128,65535] gets some other algorithm, possibly with a table >> boost. Or somehow taking advantage of the fact that log(1-f(n)) is >> related to log(n)? >> >> Anyone have any thoughts? >> > > Taylor series are great for the theory, but very rarely a useful > calculation technique in practice. > > In a case like this, I would first look at using a single table - if > you can afford the space, use it for simplicity. Or if a "full" table is too big, consider reducing the table size and interpolating between table entries. -- Randy Yates Digital Signal Labs http://www.digitalsignallabs.comArticle: 156206
On a sunny day (Fri, 17 Jan 2014 13:19:31 -0800) it happened John Larkin <jlarkin@highlandtechnology.com> wrote in <jv6jd9p3qc1sievj88ar7325r1epq46uu0@4ax.com>: > > >Just got this from production: > >https://dl.dropboxusercontent.com/u/53724080/PCBs/ASP_SN1_top.jpg > >from previously posted layout... > >https://dl.dropboxusercontent.com/u/53724080/PCBs/P344_15.jpg > > >This is a pretty serious signal processor application, but dropping >the Zed on there makes it easy. We can plug a USB logic analyzer >directly onto that Mictor connector, which has 16 signals and a clock >from the uZed. > >Rather than being cautious, I just plugged 24 volts into it, and the >Zed lit up and ran Linux. What does 'Z' do that a Raspbery Pi cannot?Article: 156207
In comp.arch.fpga Randy Yates <yates@digitalsignallabs.com> wrote: > David Brown <david.brown@hesbynett.no> writes: (snip) >> In a case like this, I would first look at using a single table - >> if you can afford the space, use it for simplicity. > Or if a "full" table is too big, consider reducing the table size > and interpolating between table entries. Using a table of interpolation values and an adder. -- glenArticle: 156208
On Fri, 17 Jan 2014 13:19:31 -0800, John Larkin <jlarkin@highlandtechnology.com> wrote: > > >Just got this from production: > >https://dl.dropboxusercontent.com/u/53724080/PCBs/ASP_SN1_top.jpg > >from previously posted layout... > >https://dl.dropboxusercontent.com/u/53724080/PCBs/P344_15.jpg > > >This is a pretty serious signal processor application, but dropping >the Zed on there makes it easy. We can plug a USB logic analyzer >directly onto that Mictor connector, which has 16 signals and a clock >from the uZed. > >Rather than being cautious, I just plugged 24 volts into it, and the >Zed lit up and ran Linux. Very nice! Is there stuff under the uZed as well? I calculated that (for us anyway) the assembly cost in small quantities on the uZed would exceed the price, so it's kind of a no-brainer if it will do the job. Best regards, --spArticle: 156209
On Fri, 17 Jan 2014 21:31:01 GMT, Jan Panteltje <pNaonStpealmtje@yahoo.com> wrote: >On a sunny day (Fri, 17 Jan 2014 13:19:31 -0800) it happened John Larkin ><jlarkin@highlandtechnology.com> wrote in ><jv6jd9p3qc1sievj88ar7325r1epq46uu0@4ax.com>: > >> >> >>Just got this from production: >> >>https://dl.dropboxusercontent.com/u/53724080/PCBs/ASP_SN1_top.jpg >> >>from previously posted layout... >> >>https://dl.dropboxusercontent.com/u/53724080/PCBs/P344_15.jpg >> >> >>This is a pretty serious signal processor application, but dropping >>the Zed on there makes it easy. We can plug a USB logic analyzer >>directly onto that Mictor connector, which has 16 signals and a clock >>from the uZed. >> >>Rather than being cautious, I just plugged 24 volts into it, and the >>Zed lit up and ran Linux. > >What does 'Z' do that a Raspbery Pi cannot? Integrate two 600 MHz ARM cores and a screaming-fast FPGA onto one chip. And the Zed has Ethernet, flash, DRAM, USB, power supplies, all that stuff done and tested. It's a great way to do gear that will be built in fairly small quantities. This app will do a lot of signal processing in the FPGA at 48 M samples/second. -- John Larkin Highland Technology, Inc jlarkin att highlandtechnology dott com http://www.highlandtechnology.comArticle: 156210
alb wrote: > Hi everyone, > > I'm trying to optimize the footprint of my firmware on the target device > and I realize there are a lot of parameters which might be stored in the > embedded RAM instead of dedicated registers. > > Certainly the RAM access logic will 'eat some space' but lot's of flops > will be released. Is there any recommendation on how to optimally use > embedded resources? [1] > > The main reason for this optimization is to free some space to include a > function which has been added later in the design phase (ouch!). > > Thanks a lot, > > Al > > [1] I know that put like this this question is certainly open to a hot > discussion! :-) > It depends on the device you're targetting. To some extent the tools can make use of embedded RAM without changing your RTL. For example Xilinx tools allow you to place logic into unused BRAMs, and will automatically infer SRL's where the design allows it. I've often used BRAM as a "shadow memory" to keep a copy of internal configuration registers for readback. That can eliminate a large mux, at least for all register bits that only change when written. Read-only bits and self-resetting bits would still need a mux, but the overall logic could be reduced vs. a complete mux for all bits. -- Gabor P.S. - I find your signature more annoying than top posting. In my opinion the most annoying thing about usenet (besides the text-only format) is people who think they have been appointed to police the ettiquette of other posters.Article: 156211
glen herrmannsfeldt wrote: > In comp.arch.fpga Rob Gaddi <rgaddi@technologyhighland.invalid> wrote: > > (snip) >> I'm trying to approximate either exp(-1/(n+1)) or 4^(-1/n+1). I can >> convince myself I don't care which. n is an integer from 1-65535, and >> the result should be fixed-point fractional, probably U0.18. The >> function output is always between 0-1, and goes up like a rocket for >> small n before leveling off to a steady cruise of >0.9 for the rest of >> the function domain. > > You want an 18 bit function of a 16 bit input. Fits into one BRAM > on most current, and not so current, FPGAs. Generate all 65536 > values and store them in BRAM (ROM in verilog/VHDL terms). > > -- glen Glen, What devices are you using. My measly Xilinx parts only have 36K bits at most per BRAM. I'd need 36 of those to do this table. -- GaborArticle: 156212
On Fri, 17 Jan 2014 16:46:15 -0500, Spehro Pefhany <speffSNIP@interlogDOTyou.knowwhat> wrote: >On Fri, 17 Jan 2014 13:19:31 -0800, John Larkin ><jlarkin@highlandtechnology.com> wrote: > >> >> >>Just got this from production: >> >>https://dl.dropboxusercontent.com/u/53724080/PCBs/ASP_SN1_top.jpg >> >>from previously posted layout... >> >>https://dl.dropboxusercontent.com/u/53724080/PCBs/P344_15.jpg >> >> >>This is a pretty serious signal processor application, but dropping >>the Zed on there makes it easy. We can plug a USB logic analyzer >>directly onto that Mictor connector, which has 16 signals and a clock >>from the uZed. >> >>Rather than being cautious, I just plugged 24 volts into it, and the >>Zed lit up and ran Linux. > >Very nice! It's not nice, it's beautiful. > >Is there stuff under the uZed as well? No, just three rotary hex switches that set the IP address. The customer insisted on that. https://dl.dropboxusercontent.com/u/53724080/PCBs/ASP_SN1_side.jpg Life would be great without customers. > >I calculated that (for us anyway) the assembly cost in small >quantities on the uZed would exceed the price, so it's kind of a >no-brainer if it will do the job. All that DDRx ram and microSim and Ethernet and stuff is a nuisance to design and test. For a tad under $200, it's a bargain. The Xilinx software is, as usual, a horror story, but it looks like we have things working now, namely a Linux app talking to the FPGA talking to pins on the interface connectors. As far as I know, there is *no such* reference design! -- John Larkin Highland Technology, Inc jlarkin att highlandtechnology dott com http://www.highlandtechnology.comArticle: 156213
On a sunny day (Fri, 17 Jan 2014 13:50:46 -0800) it happened John Larkin <jlarkin@highlandtechnology.com> wrote in <559jd9pie6ngd8l1ch1gp47von4771prtl@4ax.com>: >>>Rather than being cautious, I just plugged 24 volts into it, and the >>>Zed lit up and ran Linux. >> >>What does 'Z' do that a Raspbery Pi cannot? > >Integrate two 600 MHz ARM cores and a screaming-fast FPGA onto one >chip. And the Zed has Ethernet, flash, DRAM, USB, power supplies, all >that stuff done and tested. It's a great way to do gear that will be >built in fairly small quantities. Well rapsi has that, but only one core. >This app will do a lot of signal processing in the FPGA at 48 M >samples/second. http://www.bugblat.com/products/pif/ So all together with tools about 75 $; raspi + FPGA board. 2 rapsis ... makes... 3 rapsis makes... any combination thereof. But rapsi also has HD HDMI out, and audio out, etc... That HDMI out is cool, as you can plug it into almost any modern monitor and make nice user friendly presentations. Something that is not so simple or needs extra hardware on other platforms. My rapsi even plays HD movies... Just imagine, when it starts up you can make it play the Highland background with cows grazing. with greener grass...Article: 156214
In comp.arch.fpga GaborSzakacs <gabor@alacron.com> wrote: (snip, I wrote) >> You want an 18 bit function of a 16 bit input. Fits into one BRAM >> on most current, and not so current, FPGAs. Generate all 65536 >> values and store them in BRAM (ROM in verilog/VHDL terms). (snip) > What devices are you using. My measly Xilinx parts only have > 36K bits at most per BRAM. I'd need 36 of those to do this table. Last time I was working with Xilinx, I only needed tiny RAMs. The BRAMs have 18 inputs and 18 outputs (which I remembered) but it seems to be dual port, two 9 bit addresses (the part I didn't remember). The Spartan-6 devices have between 12 and 268 such BRAMs, though. How many such BRAM can you use? Easiest way to do interpolation is with look-up tables for the interpolation values. Start with a 2Kx18 RAM, so 11 address bits. A second 2Kx18 RAM is addresses by the high bits (six in this case) of the address, and the rest (five bits) from the 16 bit address. That, plus an 18 bit adder, possibly pipelined, will give you linear interpolation on the 2Kx18 values. If that isn't enough, two interpolation RAMS, indexed by combinations of the high and low address bits, will do better. One way to look at the interpolation ROM is that the high bits select a slope, and the low bits select an appropriate multiple of that slope to be added. That is what was done when MOS ROMs were about that size. You can also use the block multipliers, with interpolation tables as inputs. A lot depends on how fast it needs to be, and how many of them you need at the same time. -- glenArticle: 156215
In comp.arch.fpga John Larkin <jlarkin@highlandtechnology.com> wrote: > Just got this from production: > https://dl.dropboxusercontent.com/u/53724080/PCBs/ASP_SN1_top.jpg SN #1 hand written on Tape. Nice ! -- Uwe Bonnes bon@elektron.ikp.physik.tu-darmstadt.de Institut fuer Kernphysik Schlossgartenstrasse 9 64289 Darmstadt --------- Tel. 06151 162516 -------- Fax. 06151 164321 ----------Article: 156216
On 1/17/14 3:21 PM, David Brown wrote: > On 17/01/14 20:00, Rob Gaddi wrote: >> Hey y'all -- >> >> So this is one of those times that my lack of serious math chops is >> coming round to bite me, and none of my usual books is helping me out. >> I'm hoping someone has some thoughts. >> >> I'm trying to approximate either exp(-1/(n+1)) or 4^(-1/n+1). to what degree of accuracy do you need this >> Anyone have any thoughts? >> > > Taylor series are great for the theory, but very rarely a useful > calculation technique in practice. > for instance, for one octave range, these finite-order polynomial are accurate to something like 1/10000 octave. (i can't seem to find the max error anymore.) > for 0 <= x <= 1 > > 2^x ~= > 1.00000000000000 > + 0.69303212081966 * x > + 0.24137976293709 * x^2 > + 0.05203236900844 * x^3 > + 0.01355574723481 * x^4 > > > log2(1+x) ~= > 0 > + 1.44254494359510 * x > + -0.71814525675041 * x^2 > + 0.45754919692582 * x^3 > + -0.27790534462866 * x^4 > + 0.12179791068782 * x^5 > + -0.02584144982967 * x^6 > In a case like this, I would first look at using a single table - if you > can afford the space, use it for simplicity. at least for the first few values of integer n. after n gets large enough, you might be able to use a sparce table and interpolate. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."Article: 156217
On 17/01/14 22:06, Jan Panteltje wrote: > On a sunny day (Fri, 17 Jan 2014 13:50:46 -0800) it happened John Larkin > <jlarkin@highlandtechnology.com> wrote in > <559jd9pie6ngd8l1ch1gp47von4771prtl@4ax.com>: > >>>> Rather than being cautious, I just plugged 24 volts into it, and the >>>> Zed lit up and ran Linux. >>> >>> What does 'Z' do that a Raspbery Pi cannot? >> >> Integrate two 600 MHz ARM cores and a screaming-fast FPGA onto one >> chip. And the Zed has Ethernet, flash, DRAM, USB, power supplies, all >> that stuff done and tested. It's a great way to do gear that will be >> built in fairly small quantities. > > Well rapsi has that, but only one core. > > >> This app will do a lot of signal processing in the FPGA at 48 M >> samples/second. > > > http://www.bugblat.com/products/pif/ > So all together with tools about 75 $; raspi + FPGA board. > > 2 rapsis ... makes... > 3 rapsis makes... > > any combination thereof. > > But rapsi also has HD HDMI out, and audio out, etc... > > That HDMI out is cool, as you can plug it into almost any modern monitor > and make nice user friendly presentations. > Something that is not so simple or needs extra hardware on other platforms. > My rapsi even plays HD movies... > Just imagine, when it starts up you can make it play the Highland background with cows grazing. > with greener grass... If my understanding is correct, the RPi's GPIO is particularly weedy and slow. OTOH, the Zync has a high performance FPGA tightly integrated with the CPU and memory. Hence if FPGA-CPU-DRAM communication performance is important, the Zync would win hands down.Article: 156218
On 17/01/14 21:19, John Larkin wrote: > > > Just got this from production: > > https://dl.dropboxusercontent.com/u/53724080/PCBs/ASP_SN1_top.jpg > > from previously posted layout... > > https://dl.dropboxusercontent.com/u/53724080/PCBs/P344_15.jpg > > > This is a pretty serious signal processor application, but dropping > the Zed on there makes it easy. We can plug a USB logic analyzer > directly onto that Mictor connector, which has 16 signals and a clock > from the uZed. > > Rather than being cautious, I just plugged 24 volts into it, and the > Zed lit up and ran Linux. Which version of the Xilix toolset are you using? Please let us know if you continue to find things easy, or if you have had to workaround infelicities.Article: 156219
On Fri, 17 Jan 2014 22:06:12 GMT, Jan Panteltje <pNaonStpealmtje@yahoo.com> wrote: >On a sunny day (Fri, 17 Jan 2014 13:50:46 -0800) it happened John Larkin ><jlarkin@highlandtechnology.com> wrote in ><559jd9pie6ngd8l1ch1gp47von4771prtl@4ax.com>: > >>>>Rather than being cautious, I just plugged 24 volts into it, and the >>>>Zed lit up and ran Linux. >>> >>>What does 'Z' do that a Raspbery Pi cannot? >> >>Integrate two 600 MHz ARM cores and a screaming-fast FPGA onto one >>chip. And the Zed has Ethernet, flash, DRAM, USB, power supplies, all >>that stuff done and tested. It's a great way to do gear that will be >>built in fairly small quantities. > >Well rapsi has that, but only one core. > > >>This app will do a lot of signal processing in the FPGA at 48 M >>samples/second. > > >http://www.bugblat.com/products/pif/ >So all together with tools about 75 $; raspi + FPGA board. > >2 rapsis ... makes... >3 rapsis makes... > >any combination thereof. > >But rapsi also has HD HDMI out, and audio out, etc... > >That HDMI out is cool, as you can plug it into almost any modern monitor >and make nice user friendly presentations. >Something that is not so simple or needs extra hardware on other platforms. >My rapsi even plays HD movies... >Just imagine, when it starts up you can make it play the Highland background with cows grazing. >with greener grass... Offer that to the French imitation... http://www.greenfieldtechnology.com/ who copied our logo and our products. With seagulls. -- John Larkin Highland Technology, Inc jlarkin att highlandtechnology dott com http://www.highlandtechnology.comArticle: 156220
On Fri, 17 Jan 2014 23:07:49 +0000 (UTC), Uwe Bonnes <bon@hertz.ikp.physik.tu-darmstadt.de> wrote: >In comp.arch.fpga John Larkin <jlarkin@highlandtechnology.com> wrote: > >> Just got this from production: > >> https://dl.dropboxusercontent.com/u/53724080/PCBs/ASP_SN1_top.jpg > >SN #1 hand written on Tape. > >Nice ! The yellow block is silkscreened. That's where they usually put the part number + serial number sticker. #1 is mine. I'll scratch up the board to make it ugly enough that they won't swipe it and sell it. -- John Larkin Highland Technology, Inc jlarkin att highlandtechnology dott com http://www.highlandtechnology.comArticle: 156221
On a sunny day (Fri, 17 Jan 2014 16:13:41 -0800) it happened John Larkin <jlarkin@highlandtechnology.com> wrote in <jhhjd99gf3h8farut37cv1slcp99svu62q@4ax.com>: >> >>That HDMI out is cool, as you can plug it into almost any modern monitor >>and make nice user friendly presentations. >>Something that is not so simple or needs extra hardware on other platforms. >>My rapsi even plays HD movies... >>Just imagine, when it starts up you can make it play the Highland background with cows grazing. >>with greener grass... > >Offer that to the French imitation... > >http://www.greenfieldtechnology.com/ > >who copied our logo and our products. With seagulls. I came across that a while back, thought they worked for you... They all look a bit like that MS windows background I have seen in places.Article: 156222
Le Fri, 17 Jan 2014 11:00:06 -0800, Rob Gaddi a écrit: > Hey y'all -- > > So this is one of those times that my lack of serious math chops is > coming round to bite me, and none of my usual books is helping me out. > I'm hoping someone has some thoughts. > > I'm trying to approximate either exp(-1/(n+1)) or 4^(-1/n+1). I can > convince myself I don't care which. n is an integer from 1-65535, and > the result should be fixed-point fractional, probably U0.18. The > function output is always between 0-1, and goes up like a rocket for > small n before leveling off to a steady cruise of >0.9 for the rest of > the function domain. > > I'm working in an FPGA, so I've got adds, multiplies, and table lookups > from tables of reasonable size (10s of kb) cheap, but other things > (divides especially) are expensive. I can throw several clock cycles at > the problem if need be. > > Taylor series attacks seem to fail horribly. I feel like there may be > some answer where answers for n in [1,127] gets a direct table lookup, > and n in [128,65535] gets some other algorithm, possibly with a table > boost. Or somehow taking advantage of the fact that log(1-f(n)) is > related to log(n)? > > Anyone have any thoughts? Required accuracy? (may be absolute or relative) Good approximants for this kind of problems can be obtained through Padé expansion (ratio of polynomials) but this involves one division. Over the [1..65535] range the absolute accuracy you have is 1,013E-3 for order {1,1} 1.054E-6 for order {2,2} 4,71E-10 for order {3,3} At 2.5E-3, orders {1,2} and {2,1} give accuracies worse than the {1,1} and are thus not worth. Given that you want a 18bits result the {2,2} expension is clearly enough, but maybe {1,1} will suit your need. Optimal expansion (symetrical absolute max error) is for: x0=3.3613 (order 1,1) x0=3.21001 (order 2,2) Not much error is introduced when approximating the x0s to 10/3 or 34/10 for (1,1) and 10/3 or 32/10 for (2,2) With a general form p(x) = k (1 + a x + b x^2)/(1 + c x + d x^2) that gives: for order (1,1) {k,a,c} xo=10/3 => {4/(9 Exp(3/13), 29/16, 23/36} xo=34/10 => {27/(61 Exp(5/22)), 49/27, 39/61} for order (2,2) {k,a,b,c,d} xo=10/3 => {337/(727 Exp(3/13)), 1725/674, 2271/1348,2271/1454,1803/2908} xo=32/10 => {883/(1891 Exp(5/21)), 4519/1766, 5947/3532, 5905/3782, 4687/7564} -- Thanks, Fred.Article: 156223
On 17/01/2014 19:00, Rob Gaddi wrote: > Hey y'all -- > > So this is one of those times that my lack of serious math chops is > coming round to bite me, and none of my usual books is helping me out. > I'm hoping someone has some thoughts. > The relevant books also seem to be both rare and expensive.... http://www.amazon.co.uk/Approximations-Digital-Computers-Cecil-Hastings/dp/0691079145 http://www.amazon.co.uk/Standard-C-Library-P-J-Plauger/dp/0131315099/ref=sr_1_2?s=books&ie=UTF8&qid=1390052292&sr=1-2&keywords=c+standard+library > I'm trying to approximate either exp(-1/(n+1)) or 4^(-1/n+1). I can > convince myself I don't care which. n is an integer from 1-65535, and > the result should be fixed-point fractional, probably U0.18. The > function output is always between 0-1, and goes up like a rocket for > small n before leveling off to a steady cruise of >0.9 for the rest of > the function domain. > > I'm working in an FPGA, so I've got adds, multiplies, and table lookups > from tables of reasonable size (10s of kb) cheap, but other things > (divides especially) are expensive. I can throw several clock cycles > at the problem if need be. > > Taylor series attacks seem to fail horribly. Well almost all approximations to functions end end up as a power series of some sorts. If you read Hastings he uses truncated power series with coefficients optimized to minimize the error over the domain in question. When I wrote a "C" Maths library for the IBM/370 (yes I am a Vintage Computer Geek) I wrote a REXX program to calculate the functions to a higher accuracy than needed and then optimize the co-efficients of the taylor series needed. > I feel like there may be > some answer where answers for n in [1,127] gets a direct table lookup, > and n in [128,65535] gets some other algorithm, possibly with a table > boost. Or somehow taking advantage of the fact that log(1-f(n)) is > related to log(n)? > Load it into RAM or Flash at startup.... > Anyone have any thoughts? > See Above DaveArticle: 156224
On Sat, 18 Jan 2014 09:00:22 GMT, Jan Panteltje <pNaonStpealmtje@yahoo.com> wrote: >On a sunny day (Fri, 17 Jan 2014 16:13:41 -0800) it happened John Larkin ><jlarkin@highlandtechnology.com> wrote in ><jhhjd99gf3h8farut37cv1slcp99svu62q@4ax.com>: > >>> >>>That HDMI out is cool, as you can plug it into almost any modern monitor >>>and make nice user friendly presentations. >>>Something that is not so simple or needs extra hardware on other platforms. >>>My rapsi even plays HD movies... >>>Just imagine, when it starts up you can make it play the Highland background with cows grazing. >>>with greener grass... >> >>Offer that to the French imitation... >> >>http://www.greenfieldtechnology.com/ >> >>who copied our logo and our products. With seagulls. > >I came across that a while back, thought they worked for you... No, but Bernard Riondet is sort of an old friend. We never could find a good project to work on together, so he did his own thing. We did the master timing system for NIF, and then he apparently did the one for LMJ. >They all look a bit like that MS windows background I have seen in places. Our logo predates Microsoft! -- John Larkin Highland Technology Inc www.highlandtechnology.com jlarkin at highlandtechnology dot com Precision electronic instrumentation
Site Home Archive Home FAQ Home How to search the Archive How to Navigate the Archive
Compare FPGA features and resources
Threads starting:
Authors:A B C D E F G H I J K L M N O P Q R S T U V W X Y Z