Hello, I am trying to compute the antilog of a fixed point number 'x' -> 10^(x), to be precise. I do not want to use a look-up table for the same. One way this can be done is to use the Taylor series expansion of 10^(x). Can someone point me to the right place? Also any suggestions on improved (in the number of execute cycles, memory is not much of a constraint - only enough to cancel the table look-up option :]) algorithms will be greatly appreciated. T.
Antilog - base 10
Started by ●June 1, 2005
Reply by ●June 1, 20052005-06-01
tanmay.zargar@gmail.com wrote:> Hello, > > I am trying to compute the antilog of a fixed point number 'x' -> > 10^(x), to be precise. > > I do not want to use a look-up table for the same. One way this can be > done is to use the Taylor series expansion of 10^(x). Can someone point > me to the right place? Also any suggestions on improved (in the number > of execute cycles, memory is not much of a constraint - only enough to > cancel the table look-up option :]) algorithms will be greatly > appreciated. >How big is 'x'? That is, how many bits do you need to represent 'x'?
Reply by ●June 1, 20052005-06-01
Reply by ●June 1, 20052005-06-01
tanmay.zargar@gmail.com writes:> I am trying to compute the antilog of a fixed point number 'x' -> > 10^(x), to be precise.How large can x be? How large can 10^x be?> I do not want to use a look-up table for the same. One way this can be > done is to use the Taylor series expansion of 10^(x). Can someone point > me to the right place? Also any suggestions on improved (in the number > of execute cycles, memory is not much of a constraint - only enough to > cancel the table look-up option :]) algorithms will be greatly > appreciated.To get the Taylor series, you can write 10^x = e^(x log10), then use the Taylor series for e^x: 10^x = 1/0! + log10/1! x + (log10)^2/2! x^2 + ... If you write x = q + r, then 10^x = 10^q * 10^r. If you use as much memory as you can afford to tabulate 10^q, then you can reduce the size of r, so that you need only a few terms of the series. Scott -- Scott Hemphill hemphill@alumni.caltech.edu "This isn't flying. This is falling, with style." -- Buzz Lightyear
Reply by ●June 1, 20052005-06-01
Yes, there are several methods that are much better than iterated multiplication but they have a certain amount of set-up overhead. For small values of 'x', iterated multiplication may be fastest. As 'x' increases, the other methods become more efficient. The crossover points depend partially on what kind of a processor you are using. I'll get you the references to the other methods before the end of the day if someone doesn't help you first.
Reply by ●June 1, 20052005-06-01
"Scott Hemphill" <hemphill@hemphills.net> wrote in message news:m3mzqaox7w.fsf@pearl.local...> tanmay.zargar@gmail.com writes: > > > I am trying to compute the antilog of a fixed point number 'x' -> > > 10^(x), to be precise. > > How large can x be? How large can 10^x be?Also, when you say "fixed point", is x an integer or some fractional format like -1 <= x < 1 or something else? Knowing these things may make a difference--the more detail you can give us, the more we can help.> > I do not want to use a look-up table for the same. One way this can be > > done is to use the Taylor series expansion of 10^(x). Can someone point > > me to the right place? Also any suggestions on improved (in the number > > of execute cycles, memory is not much of a constraint - only enough to > > cancel the table look-up option :]) algorithms will be greatly > > appreciated.I don't know why you are dismissing tables out-of-hand if you want fast execution and you have lots of memory! You might consider a small table to get a "rough" answer and then a simple interpolation scheme between table entries to reduce the error to something acceptable. Think of it this way: you have a continuum of options with a full look-up table with one entry for every possible input on one end and direct calculation on the other end. The "best" solution may lie somewhere in between.> To get the Taylor series, you can write 10^x = e^(x log10), then use > the Taylor series for e^x: > > 10^x = 1/0! + log10/1! x + (log10)^2/2! x^2 + ... > > If you write x = q + r, then 10^x = 10^q * 10^r. If you use as much > memory as you can afford to tabulate 10^q, then you can reduce the > size of r, so that you need only a few terms of the series. > > Scott
Reply by ●June 1, 20052005-06-01
tanmay.zargar@gmail.com wrote:> Well, I have 16 bits for the representation of the number x. But does > that matter? > > TGo to the following URL: http://www.cacr.math.uwaterloo.ca/hac/ Scroll down to where it says "Sample Chapters Free" Download Chapter 14 "Efficient Implementation" Go to Section 14.6 Exponentiation. There you will find a number of ways to efficiently compute exact results, possibly faster than table lookup!
Reply by ●June 1, 20052005-06-01
tanmay.zargar@gmail.com wrote:> Well, I have 16 bits for the representation of the number x. But does > that matter?What matters more is the number of bits available to represent the result. Floating point seems unlikely with 16 bits. If x and 10^x are both integers, the simplest way is a lookup table with seven entries: 0 (for all negative inputs), 1, 10, 100, 1000, 10000, <overload>. You must mean something else, but you don't say what. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●June 1, 20052005-06-01
in article 1117641231.462006.249610@o13g2000cwo.googlegroups.com, tanmay.zargar@gmail.com at tanmay.zargar@gmail.com wrote on 06/01/2005 11:53:> I am trying to compute the antilog of a fixed point number 'x' -> > 10^(x), to be precise. > > I do not want to use a look-up table for the same. One way this can be > done is to use the Taylor series expansion of 10^(x). Can someone point > me to the right place? Also any suggestions on improved (in the number > of execute cycles, memory is not much of a constraint - only enough to > cancel the table look-up option :]) algorithms will be greatly > appreciated.10^x = 2^(log2(10)*x) and you can get a finite series that well approximates 2^x from http://groups-beta.google.com/group/comp.dsp/msg/8ba6bd6fe2474876 . try that. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●June 1, 20052005-06-01
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.