Antilog - base 10

"John Hadstate" <jh113355@hotmail.com> wrote in message 
news:1117654632.785625.143310@f14g2000cwb.googlegroups.com...
>
>
> tanmay.zargar@gmail.com wrote:
>>
>> 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.
>>
>

Here is an efficient, hardware-independent algorithm that 
will exactly compute 10**x where x is a 16-bit scaled number 
in at most 16 iterations.  It works because:

10**(1 + 1/2 + 1/4 + ...) = 
(10**1)*(10**(1/2))*(10**(1/4)*...

First, define the scaling.  If 1.15, I'm assuming you mean 1 
whole number bit and 15 fractional bits and the maximum 
value of x = 1 + 1/2 + 1/4 + ... + 1/32768.

Then, define a table of 16 numbers according to the 
following algorithm:

#define XBITS 16

    double tenTable[XBITS];

    tenTable[0] = 10.;

    for (i = 1; i < XBITS; i++)
    {
        tenTable[i] = sqrt(tenTable[i - 1]);
    }

This computation needs be done once only, and ever after, 
tenTable can live in ROM or RAM.

Now, using said table, the compute 10**x as follows:

double Antilog10(unsigned int x)
{
    int i;
    double y;

    i = XBITS;
    y = 1.;

    while (x != 0)
    {
        i = i - 1;

        if ((x & 1) != 0) y = y * tenTable[i];

        x = (x >> 1);
    }

    return y;
}


By adjusting tenTable, this algorithm is easily adaptable to 
any scaling of x such as 1.31, 2.14, 8.8, etc.

John E. Hadstate wrote:
> "John Hadstate" <jh113355@hotmail.com> wrote in message
> news:1117654632.785625.143310@f14g2000cwb.googlegroups.com...
> >
> >
> > tanmay.zargar@gmail.com wrote:
> >>
> >> 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.
> >>
> >
>
> Here is an efficient, hardware-independent algorithm that
> will exactly compute 10**x where x is a 16-bit scaled number
> in at most 16 iterations.  It works because:
>
> 10**(1 + 1/2 + 1/4 + ...) =
> (10**1)*(10**(1/2))*(10**(1/4)*...
>
> First, define the scaling.  If 1.15, I'm assuming you mean 1
> whole number bit and 15 fractional bits and the maximum
> value of x = 1 + 1/2 + 1/4 + ... + 1/32768.
>
> Then, define a table of 16 numbers according to the
> following algorithm:
>
> #define XBITS 16
>
>     double tenTable[XBITS];
>
>     tenTable[0] = 10.;
>
>     for (i = 1; i < XBITS; i++)
>     {
>         tenTable[i] = sqrt(tenTable[i - 1]);
>     }
>
> This computation needs be done once only, and ever after,
> tenTable can live in ROM or RAM.
>
> Now, using said table, the compute 10**x as follows:
>
> double Antilog10(unsigned int x)
> {
>     int i;
>     double y;
>
>     i = XBITS;
>     y = 1.;
>
>     while (x != 0)
>     {
>         i = i - 1;
>
>         if ((x & 1) != 0) y = y * tenTable[i];
>
>         x = (x >> 1);
>     }
>
>     return y;
> }
>
>
> By adjusting tenTable, this algorithm is easily adaptable to
> any scaling of x such as 1.31, 2.14, 8.8, etc.

Your algorithm suggests a modification.

Use successive approximation to resolve the fractional part of the
argument as the sum from m =1 to M of Am 2**-m where the coefficients
Am are either plus one or  minus one.

For example if x = .34375 then x = .5 - .25 + .125 -.0625 + .03125

At each step of the resolution the mth table entry containing
10**(2**-m) multiples a product register when am is one or divides the
register for am equal minus one.

Hence 10**.34375 = 1 * (10**(1/2))  /  (10**(1/4)) * (10**(1/8)) . . .

Herbert

<a1eah71@aol.com> wrote in message 
news:1118041775.949460.8790@z14g2000cwz.googlegroups.com...
>
>
>
> Your algorithm suggests a modification.
>
> Use successive approximation to resolve the fractional 
> part of the
> argument as the sum from m =1 to M of Am 2**-m where the 
> coefficients
> Am are either plus one or  minus one.
>
> For example if x = .34375 then x = .5 - .25 + .125 -.0625 
> + .03125
>
> At each step of the resolution the mth table entry 
> containing
> 10**(2**-m) multiples a product register when am is one or 
> divides the
> register for am equal minus one.
>
> Hence 10**.34375 = 1 * (10**(1/2))  /  (10**(1/4)) * 
> (10**(1/8)) . . .
>

I can see what you say is true, but I don't quite see what 
it buys me (maybe half the table size?).  Also, isn't 
division universally more time consuming than 
multiplication?

John E. Hadstate wrote:
> <a1eah71@aol.com> wrote in message
> news:1118041775.949460.8790@z14g2000cwz.googlegroups.com...
> >
> >
> >
> > Your algorithm suggests a modification.
> >
> > Use successive approximation to resolve the fractional
> > part of the
> > argument as the sum from m =1 to M of Am 2**-m where the
> > coefficients
> > Am are either plus one or  minus one.
> >
> > For example if x = .34375 then x = .5 - .25 + .125 -.0625
> > + .03125
> >
> > At each step of the resolution the mth table entry
> > containing
> > 10**(2**-m) multiples a product register when am is one or
> > divides the
> > register for am equal minus one.
> >
> > Hence 10**.34375 = 1 * (10**(1/2))  /  (10**(1/4)) *
> > (10**(1/8)) . . .
> >
>
> I can see what you say is true, but I don't quite see what
> it buys me (maybe half the table size?).  Also, isn't
> division universally more time consuming than
> multiplication?

Generally division is more time consuming than multiplication. However,
these differences are negligible compared with the cost of ignoring the
benefits of binary arithmetic. By using resolving the argument as a sum
from m=1 to M of Am log base two ( 1 + 2**-m ), calculation of 2**x
requires only shifts and additions.

Perhaps I am old fashioned but my position is anyone who does decimal
arithmetic deserves to wait for what they get. 


Herbert

<a1eah71@aol.com> wrote in message 
news:1118120058.906145.30700@g49g2000cwa.googlegroups.com...
>
>
> John E. Hadstate wrote:
>> <a1eah71@aol.com> wrote in message
>> news:1118041775.949460.8790@z14g2000cwz.googlegroups.com...
>> >
>> >
>> >
>> > Your algorithm suggests a modification.
>> >
>> > Use successive approximation to resolve the fractional
>> > part of the
>> > argument as the sum from m =1 to M of Am 2**-m where 
>> > the
>> > coefficients
>> > Am are either plus one or  minus one.
>> >
>> > For example if x = .34375 then x = .5 - .25 + 
>> > .125 -.0625
>> > + .03125
>> >
>> > At each step of the resolution the mth table entry
>> > containing
>> > 10**(2**-m) multiples a product register when am is one 
>> > or
>> > divides the
>> > register for am equal minus one.
>> >
>> > Hence 10**.34375 = 1 * (10**(1/2))  /  (10**(1/4)) *
>> > (10**(1/8)) . . .
>> >
>>
>> I can see what you say is true, but I don't quite see 
>> what
>> it buys me (maybe half the table size?).  Also, isn't
>> division universally more time consuming than
>> multiplication?
>
> Generally division is more time consuming than 
> multiplication. However,
> these differences are negligible compared with the cost of 
> ignoring the
> benefits of binary arithmetic. By using resolving the 
> argument as a sum
> from m=1 to M of Am log base two ( 1 + 2**-m ), 
> calculation of 2**x
> requires only shifts and additions.
>
> Perhaps I am old fashioned but my position is anyone who 
> does decimal
> arithmetic deserves to wait for what they get.
>

I'm trying to understand where the improvement is.  The 
light hasn't switched on yet.