I'm currently using a binary search algorithm with a reverse
(exponential) lookup table to convert float and 16-bit linear data
into 6-bits or 7-bits of log scaled data.

Are there a faster conversion algorithms for DSP's or CPU's with a
single-cycle MACC?  If so, could someone point me at references, or the
appropriate Google search terms?

Thanks.

-- 
Ron Nicholson   rhn AT nicholson DOT com   http://www.nicholson.com/rhn/ 
#include <canonical.disclaimer>        // only my own opinions, etc.

<Ronald H. Nicholson>; "Jr." <rhn@nojunk.rahul.net> wrote in message
news:bfcepc$gjv$1@blue.rahul.net...
> I'm currently using a binary search algorithm with a reverse
> (exponential) lookup table to convert float and 16-bit linear data
> into 6-bits or 7-bits of log scaled data.
>
> Are there a faster conversion algorithms for DSP's or CPU's with a
> single-cycle MACC?  If so, could someone point me at references, or the
> appropriate Google search terms?

Hi Ron,

I would do this in two steps:

1) As an initial estimate, get the position of the highest set bit.  This is
floor(log_2(x)).

2) Using that position shift the highest most significant bits after that
one into the low order N bitsof the word.

3) Fetch (log2_(x) - floor(log_2(x)) from a lookup table on those bits and
add it to the result.

A lot of CPUs have a function to get bit position of the highest 1 bit
directly.  If you don't have such an instruction, then you need some finesse
in step 1).  There are lots of things you can do, depending on what
instructions you do have.  The worst case is you have to do a binary search
using a few ifs.

If you have to do a binary search, you can leave off the last couple
iterations and get a lower bound on floor(log_2(x)) to within a few bits.
Then, by including the actual highest bit, you can lookup the difference in
a larger lookup table.

Jerry Avins wrote:
> Ron wrote:
> > I'm currently using a binary search algorithm with a reverse
> > (exponential) lookup table to convert float and 16-bit linear data
> > into 6-bits or 7-bits of log scaled data.
....
> The exponent of a floating-point number gives most of the log, and
> little refinement is needed. I have reasonably compact code (in Forth,
> but I can translate) to find the highest significant bit of an integer.
> With that, you need to find logs only in one octave.

The floating-point mantissa is a value in [1.0, 2.0[ (in IEEE 754). With
linear interpolation, you get around 1 - 2 dBs of accuracy. With quadratic
interpolation, the error is already below 0.1 dB, which works for me.

Don't use Taylor series approximation.

Regards,
Andor

Hello Ronald,
You can use repeated squaring and shifting to calculate a base two log. This
will use a mult per bit of the final answer.  A final mult will convert to
any radix you need.
Let me know if you need more details.

Clay




<Ronald H. Nicholson>; "Jr." <rhn@nojunk.rahul.net> wrote in message
news:bfcepc$gjv$1@blue.rahul.net...
> I'm currently using a binary search algorithm with a reverse
> (exponential) lookup table to convert float and 16-bit linear data
> into 6-bits or 7-bits of log scaled data.
>
> Are there a faster conversion algorithms for DSP's or CPU's with a
> single-cycle MACC?  If so, could someone point me at references, or the
> appropriate Google search terms?
>
> Thanks.
>
> --
> Ron Nicholson   rhn AT nicholson DOT com   http://www.nicholson.com/rhn/
> #include <canonical.disclaimer>        // only my own opinions, etc.

Hi Ron and Clay

SPRA218 is a 1993 app note, but the algorithm is never the less still
valid and should prove interesting.

http://focus.ti.com/docs/apps/catalog/resources/appnoteabstract.jhtml?abstractName=spra218

I had been using the fast log technique (directly use a float number)
for some time, even back to my C1x/C2x/C5x days, when I realized that
the floating point ALU could be used to perform the squaring and
shifting operations that Clay is mentioning...  But with a lot less
overhead.

The bottom line in this discovery was that 7 additional log2 bits,
adding to the original accuracy, could be 'mined' from the exponent
every 7 iterations.  Why 7?  It is because the 8 bit exponent could
overflow on the 8th iteration (see example below).

The example given in the application note is for converting the value
1.5 to log2 form.  Here is the sequence.  Note how before you even
start, the 'fast log2' value of 1.5 is 0.5, and is not a bad guess!


     Exp S Mantissa
00000000 0 1000000000000000000000000000000 X =1.5 Exp=0 (fastlog2=0.5)
00000001 0 0010000000000000000000000000000 X^2 =2.25 Exp=1
00000010 0 0100010000000000000000000000000 X^4 =5.0625 Exp=2
00000100 0 1001101000010000000000000000000 X^8 =25.628906 Exp=4
00001001 0 0100100001101011101000001000000 X^16 =656.84083 Exp=9
00010010 0 1010010101010011111101110011111 X^32 =431.43988-E3 Exp=18
00100101 0 0101101010110110101000010101001 X^64 =186.14037-E9 Exp=37
01001010 0 1101010110010010001010101100011 X^128 =34.648238-E21 Exp=74
XXXXXXXX S MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM

Hope this helps
Best regards
Keith Larson
===========================
Clay S. Turner wrote:

Hello Ronald, You can use repeated squaring and shifting to calculate a 
base two log. This will use a mult per bit of the final answer.  A final 
mult will convert to any radix you need. Let me know if you need more 
details.

  Clay
===========================
<Ronald H. Nicholson>; "Jr." <rhn@nojunk.rahul.net> wrote in message 
news:bfcepc$gjv$1@blue.rahul.net...


I'm currently using a binary search algorithm with a reverse 
(exponential) lookup table to convert float and 16-bit linear data into 
6-bits or 7-bits of log scaled data. Are there a faster conversion 
algorithms for DSP's or CPU's with a single-cycle MACC?  If so, could 
someone point me at references, or the appropriate Google search terms?

Thanks.

-- Ron Nicholson   rhn AT nicholson DOT com
http://www.nicholson.com/rhn/ #include <canonical.disclaimer>
    // only my own opinions, etc.
+------------------------------------------+
|Keith Larson                              |
|Member Group Technical Staff              |
|Texas Instruments Incorporated            |
|                                          |
| 281-274-3288                             |
| k-larson2@ti.com                         |
|------------------------------------------+
|     TMS320C3x/C4x/VC33 Applications      |
|                                          |
|               TMS320VC33                 |
|    The lowest cost and lowest power      |
|    floating point DSP on the planet!     |
|              500uw/Mflop                 |
+------------------------------------------+