tanmay.zargar@gmail.com:> Hello, > > I am trying to compute the antilog of a fixed point number 'x' -> > 10^(x), to be precise.Look for something called "shift-and-add algorithm". There is one algorithm to compute the logarithm of various bases and one to compute exponentiation. The latter one uses a small lookup table with the precomputed values of log_10(1-(2^-k)). You approximate x by adding up values from this table. 10^x can be derived while you compare x with your approximate value. Because the lookup table contains the logarithms of bit values, you won't need fast multiplication for that, just addition and shift. Run-time grows linear with required precision.
Antilog - base 10
Started by ●June 1, 2005
Reply by ●June 2, 20052005-06-02
Reply by ●June 2, 20052005-06-02
Jon Harris wrote:> "robert bristow-johnson" <rbj@audioimagination.com> wrote in message > news:BEC3AE0A.7DB0%rbj@audioimagination.com... > >>in article ks0a1ixr5s35.ajhthf2taxdu.dlg@40tude.net, Siegbert Steinlechner >>at sigi.nospam@onlinehome.de wrote on 06/01/2005 16:44: >> >> >>it is. i used remes also (i have a crude C program and another crude MATLAB >>program since i couldn't find one in MATLAB) but i modified it to constrain >>the error at the endpoints to be zero. since normally the endpoints are set >>to the max error and used in the "alternation theorem", when you constrain >>those endpoint errors to be zero, you have to pay for it somewhere else. >> >>it just bothered me that 2^0 and 2^1 was not exactly 1 and 2 and log2(1) and >>log2(2) were not exactly 0 and 1, respectively. no other reason motivated >>it. i did a similar constraint for sqrt(). > > > I like to do that too, especially if the approximation is used in a piece-wise > fashion, i.e. covering one octave where the input value spans multiple octaves. > It eliminates any discontinuity at the "splice" points. > > I have used a simple linear algebra method in Excel where for a polynomial of > degree n, you constrain n+1 points to exactly equal the "correct" function > values. Along with this, I use a crude trial and error method to pick good > "matching" points so that I don't get a gross error somewhere else. (I usually > use the end points as 2 of the matching points.) It works OK for small n (3-4) > but is not optimal. I should look into the Remez method. RB-J, if you find > your Matlab script and don't mind posting it, I wouldn't mind having a look.You don't have to put the end points of straight-line approximations on the defining curve in order to ensure continuity. intersecting secants, rather than intersecting chords, will reduce the error. That will cut the peak error in half for well-chosen intervals, and make the error much closer to zero mean. It's a chore to do, though. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●June 2, 20052005-06-02
"Jerry Avins" <jya@ieee.org> wrote in message news:7OqdneXcgM3PvgLfRVn-vQ@rcn.net...> Jon Harris wrote: > > "robert bristow-johnson" <rbj@audioimagination.com> wrote in message > > news:BEC3AE0A.7DB0%rbj@audioimagination.com... > > > >>in article ks0a1ixr5s35.ajhthf2taxdu.dlg@40tude.net, Siegbert Steinlechner > >>at sigi.nospam@onlinehome.de wrote on 06/01/2005 16:44: > >> > >> > >>it is. i used remes also (i have a crude C program and another crude MATLAB > >>program since i couldn't find one in MATLAB) but i modified it to constrain > >>the error at the endpoints to be zero. since normally the endpoints are set > >>to the max error and used in the "alternation theorem", when you constrain > >>those endpoint errors to be zero, you have to pay for it somewhere else. > >> > >>it just bothered me that 2^0 and 2^1 was not exactly 1 and 2 and log2(1) and > >>log2(2) were not exactly 0 and 1, respectively. no other reason motivated > >>it. i did a similar constraint for sqrt(). > > > > > > I like to do that too, especially if the approximation is used in apiece-wise> > fashion, i.e. covering one octave where the input value spans multipleoctaves.> > It eliminates any discontinuity at the "splice" points. > > > > I have used a simple linear algebra method in Excel where for a polynomialof> > degree n, you constrain n+1 points to exactly equal the "correct" function > > values. Along with this, I use a crude trial and error method to pick good > > "matching" points so that I don't get a gross error somewhere else. (Iusually> > use the end points as 2 of the matching points.) It works OK for small n(3-4)> > but is not optimal. I should look into the Remez method. RB-J, if you find > > your Matlab script and don't mind posting it, I wouldn't mind having a look. > > You don't have to put the end points of straight-line approximations on > the defining curve in order to ensure continuity. intersecting secants, > rather than intersecting chords, will reduce the error. That will cut > the peak error in half for well-chosen intervals, and make the error > much closer to zero mean. It's a chore to do, though.I'm not sure I totally understand you here Jerry, primarily because I am missing knowledge about "intersecting secants" and "intersecting chords". I _think_ you are saying that as long as I constrain the 2 end points to be equal to _each other_, even though they don't necesarrily match the "ideal" curve value, I still avoid the discontinuity plus theoretically achieve lower peak error. Do I have it? I tried that on a simple 2nd order approximation of a power function, and it did give me slightly better results. -- Jon Harris SPAM blocked e-mail address in use. Replace the ANIMAL with 7 to reply.
Reply by ●June 2, 20052005-06-02
Jon Harris wrote: ...> I'm not sure I totally understand you here Jerry, primarily because I am missing > knowledge about "intersecting secants" and "intersecting chords". I _think_ you > are saying that as long as I constrain the 2 end points to be equal to _each > other_, even though they don't necesarrily match the "ideal" curve value, I > still avoid the discontinuity plus theoretically achieve lower peak error. Do I > have it?Yup. A chord starts and ends on a curve. A secant (literally, by the etymology) cuts through it.> I tried that on a simple 2nd order approximation of a power function, and it did > give me slightly better results.A reasonable way to pick good secants is to start with tangents in the first and last segments, then draw secants parallel to them so displaced that the error at the ends is the negative the error in the center. (Segments with points of inflection excepted.) Then the next segment begins at the previous ending, and ends at a with error again equal to the error at the center with opposite sign. With an odd number of segments, the middle one is determined. With an even number, fudge a bit. How's that for a rule of thumb? Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●June 3, 20052005-06-03
"robert bristow-johnson" <rbj@audioimagination.com> wrote in message news:BEC3D5A0.7DBC%rbj@audioimagination.com...> in article 8mrne.50710$CR5.6856@bignews1.bellsouth.net, > John E. Hadstate at > jh113355@hotmail.com wrote on 06/01/2005 19:25: > > > are you at U. Waterloo?No, sir, I'm not. U. Waterloo has contributed a great deal to many fields related to information theory and one of their great contributions is their collection of much of the theory and practice of modern commercial cryptography into one huge tome, chapters of which can be downloaded for free.
Reply by ●June 3, 20052005-06-03
If your dB value is an int, a lookup table for one decade would only be 20 entries long. tanmay.zargar@gmail.com wrote:> I developed the algorithm to compute 10^x as e^(ln(10)*x). However, > this was too computationally intensive for my liking so I have > reconciled to the table lookup approach. > > The original problem was to convert a dBm0 value to absolute value - in > other words, computing the antilog. However that wasn't all - I had to > then multiply this 10^x value to another fixed point number. Now the > DSP processor I am using does provide intrinsic functions for fixed > point math but only for numbers in 1.15 format or 1.31 format. None of > these functions could be used directly for the problem at hand. I had > therefore to develop the algorithm myself. However, having done that, I > found that it was too demanding in terms of execution cycles. > > I doubt if there is an algorithm that will efficiently do what I need > and more so be portable across the processor I am using. I say this > because most optimized DSP algorithms make use of processor specific > intrinsic functions which ultimately make use of the hardware units > specific to the processor. If however, there is such an algorithm, > please do let me know. > > Thanks, > T. >-- Please change no_spam to a.lodwig when replying via email!
Reply by ●June 3, 20052005-06-03
Jon Harris wrote:> "Jerry Avins" <jya@ieee.org> wrote in message > news:7OqdneXcgM3PvgLfRVn-vQ@rcn.net...>> You don't have to put the end points of straight-line >> approximations on the defining curve in order to ensure >> continuity.> I _think_ you are saying that as long as I constrain the 2 > end points to be equal to _each other_, even though they don't > necesarrily match the "ideal" curve value, I still avoid the > discontinuity plus theoretically achieve lower peak error.Rather, wouldn't the ratio of the end points have to equal the scaling applied in range reduction? -- Quidquid latine dictum sit, altum viditur.
Reply by ●June 3, 20052005-06-03
Martin Eisenberg wrote:> Jon Harris wrote: > > >>"Jerry Avins" <jya@ieee.org> wrote in message >>news:7OqdneXcgM3PvgLfRVn-vQ@rcn.net... > > >>>You don't have to put the end points of straight-line >>>approximations on the defining curve in order to ensure >>>continuity. > > >>I _think_ you are saying that as long as I constrain the 2 >>end points to be equal to _each other_, even though they don't >>necesarrily match the "ideal" curve value, I still avoid the >>discontinuity plus theoretically achieve lower peak error. > > > Rather, wouldn't the ratio of the end points have to equal the > scaling applied in range reduction?I don't clearly understand what you mean. Is it that error can be measured either as a departure from or as a fraction of the correct value? Making the the center and end-point errors equal in magnitude (for mild curves, that doesn't differ much from passing the secant through the 1/4 and 3/4 points) minimizes the first kind of error. This technique typically minimizes the RMS absolute error by a factor of 3 to 4. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●June 3, 20052005-06-03
"Martin Eisenberg" <martin.eisenberg@udo.edu> wrote in message news:1117810754.190977@ostenberg.wh.uni-dortmund.de...> Jon Harris wrote: > > > "Jerry Avins" <jya@ieee.org> wrote in message > > news:7OqdneXcgM3PvgLfRVn-vQ@rcn.net... > > >> You don't have to put the end points of straight-line > >> approximations on the defining curve in order to ensure > >> continuity. > > > I _think_ you are saying that as long as I constrain the 2 > > end points to be equal to _each other_, even though they don't > > necesarrily match the "ideal" curve value, I still avoid the > > discontinuity plus theoretically achieve lower peak error. > > Rather, wouldn't the ratio of the end points have to equal the > scaling applied in range reduction?I see your point here--my wording was imprecise at best. The idea is that you want the curve sections to splice smoothly together over multiple intervals. So the 2 end points won't generally be identical, but related by some constant based on your interval. For example, consider approximating a power function over 1 octave, say y=2^x from [0, 1). Ideally, y(0) = 1 and y(1) = 2. If you use an approximation such that y(0) = 0.99 stead of 1.0, then you would want to make sure that y(1) = 1.98 so the ends "line up" when spliced together.
Reply by ●June 3, 20052005-06-03
Jon Harris wrote:> "Martin Eisenberg" <martin.eisenberg@udo.edu> wrote in message > news:1117810754.190977@ostenberg.wh.uni-dortmund.de... > >>Jon Harris wrote: >> >> >>>"Jerry Avins" <jya@ieee.org> wrote in message >>>news:7OqdneXcgM3PvgLfRVn-vQ@rcn.net... >> >>>>You don't have to put the end points of straight-line >>>>approximations on the defining curve in order to ensure >>>>continuity. >> >>>I _think_ you are saying that as long as I constrain the 2 >>>end points to be equal to _each other_, even though they don't >>>necesarrily match the "ideal" curve value, I still avoid the >>>discontinuity plus theoretically achieve lower peak error. >> >>Rather, wouldn't the ratio of the end points have to equal the >>scaling applied in range reduction? > > > I see your point here--my wording was imprecise at best. The idea is that you > want the curve sections to splice smoothly together over multiple intervals. So > the 2 end points won't generally be identical, but related by some constant > based on your interval. > > For example, consider approximating a power function over 1 octave, say y=2^x > from [0, 1). Ideally, y(0) = 1 and y(1) = 2. If you use an approximation such > that y(0) = 0.99 stead of 1.0, then you would want to make sure that y(1) = 1.98 > so the ends "line up" when spliced together.Yes. I hadn't understood your point about repeating the same basic section at different scales. I'm glad you brought it out explicitly. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
