Simple/Fast Algorithm for binary logarithm in C (on ARM7)

Jonathan Kirwan schrieb:

> You've gotten some responses already, but here's another you might
> consider looking at.  It's one of the chapters of a book that Analog
> used to give away (don't know if they still do) to customers.  Great
> book.  Anyway, this chapter covers the logarithm for the ADSP-21xx DSP
> processor, but it includes a good description about the whys and
> wherefores as well as a coded example (which requires a little bit of
> learning of the isntruction set if you want to understand each and
> every step of the code -- but that isn't too hard.)  Here is the
> chapter:
> 
> http://www.analog.com/UploadedFiles/Associated_Docs/727652249Chapter_4.pdf

Thanks for that link, Jonathan. I had also found it doing one more
internet search this afternoon, but didn't yet find the time to look at
it more deeply (which I'll surely do, however).

Tilmann

-- 
http://www.autometer.de - Elektronik nach Ma�.

CBFalconer wrote:
> 
> Tilmann Reh wrote:
> >
> > in a current ARM7 project I need to do some calculations which
> > include a logarithm. All other math is done with integers (i.e.
> > fixed point arithmetic), and I would like to calculate the log
> > fast and with little code - so I don't prefer using FP conversion
> > and the standard math libraries.
> >
> > Can anyone point to fixed-point logarithmic routines I could use
> > (resp. tailor to my needs)?
> 
> If you are using integers the logs are also integers.  The bit
> position of the most significant bit gives the binary log.  If you
> wish you can also round it up if the next two bits are 11.  This is
> probably about as good as you can do in integers.
> 
> You can extract this with (untested)
> 
>    while (b = c & (c - 1)) do c = b;
>    /* now c is the log2 of the original c value */

Correction - the c bit position is the log.

> 
> It may be worthwhile to test for a zero value before starting this.


-- 
 <http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
 <http://www.securityfocus.com/columnists/423>
 <http://www.aaxnet.com/editor/edit043.html>
 <http://kadaitcha.cx/vista/dogsbreakfast/index.html>
                        cbfalconer at maineline dot net



-- 
Posted via a free Usenet account from http://www.teranews.com

On Fri, 11 May 2007 23:02:31 +0200, Tilmann Reh
<tilmannreh@despammed.com> wrote:

>Jonathan Kirwan schrieb:
>
>> You've gotten some responses already, but here's another you might
>> consider looking at.  It's one of the chapters of a book that Analog
>> used to give away (don't know if they still do) to customers.  Great
>> book.  Anyway, this chapter covers the logarithm for the ADSP-21xx DSP
>> processor, but it includes a good description about the whys and
>> wherefores as well as a coded example (which requires a little bit of
>> learning of the isntruction set if you want to understand each and
>> every step of the code -- but that isn't too hard.)  Here is the
>> chapter:
>> 
>> http://www.analog.com/UploadedFiles/Associated_Docs/727652249Chapter_4.pdf
>
>Thanks for that link, Jonathan. I had also found it doing one more
>internet search this afternoon, but didn't yet find the time to look at
>it more deeply (which I'll surely do, however).

I used that routine, with modifications I made, in an application I
wrote (and is still in use today) back in 1990, or so.  It's worked
very well.  If you have further questions about the concepts there,
feel free to ask.  I can address the mathematical treatment to get
there as well as the implementation details.

Jon

"Tilmann Reh" <tilmannreh@despammed.com> wrote in message 
news:4644d8cd$0$10194$9b4e6d93@newsspool4.arcor-online.net...
> Peter Dickerson schrieb:
>
>>> It all depends on how accurate the log function should be. If you are 
>>> fine
>>> with 10% accuracy, just count the insignificant bits and then do a
>>> simplest linear approximation.
>>
>> The OP didn't give an input range or accuracy requirement so its hard to
>> guess what is best. The thing we do know is that its for an ARM7, which 
>> has
>> a reasonable multiplier, so better than linear shouldn't be a issue.
>
> 10% will definitely not be enough...
>
> The input data is in fixed point format, so the range can be choosen
> rather freely - however the differences in the input data already are
> small (say about 1/1000), and the flatness of the log curve makes them
> even smaller in the log result. So the mantissa surely has to be taken
> into account...

one part in a thousand of input isn't a big problem for log. Thats the same 
in natural logs i.e ln(1.001) ~= 0.001. Wide dynamic range isn't a problem 
for logs because thats take out at the shift-renormalization step. So if you 
want ln() to better than 0.001 (or log10() to better than .0004) then you're 
in the realm of table lookup or small polynomial fit. ARM7tdmi has 32x32->64 
fast multiply thats good for polys.

Peter 

Peter Dickerson wrote:
> 
... snip ...
> 
> The OP didn't give an input range or accuracy requirement so its
> hard to guess what is best. The thing we do know is that its for
> an ARM7, which has a reasonable multiplier, so better than linear
> shouldn't be a issue.

I believe he specified that he was dealing solely with integers.

-- 
 <http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
 <http://www.securityfocus.com/columnists/423>
 <http://www.aaxnet.com/editor/edit043.html>
 <http://kadaitcha.cx/vista/dogsbreakfast/index.html>
                        cbfalconer at maineline dot net



-- 
Posted via a free Usenet account from http://www.teranews.com

CBFalconer schrieb:

>> The OP didn't give an input range or accuracy requirement so its
>> hard to guess what is best. The thing we do know is that its for
>> an ARM7, which has a reasonable multiplier, so better than linear
>> shouldn't be a issue.
> 
> I believe he specified that he was dealing solely with integers.

But the represented values are not integers, that's why I mentioned
fixed point arithmetics.

Tilmann

-- 
http://www.autometer.de - Elektronik nach Ma�.

Tilmann Reh wrote:
> CBFalconer schrieb:
> 
>>> The OP didn't give an input range or accuracy requirement so its
>>> hard to guess what is best. The thing we do know is that its for
>>> an ARM7, which has a reasonable multiplier, so better than linear
>>> shouldn't be a issue.
>>
>> I believe he specified that he was dealing solely with integers.
> 
> But the represented values are not integers, that's why I mentioned
> fixed point arithmetics.

I assumed all integers.  Thus the bit position counter.

-- 
 <http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
 <http://www.securityfocus.com/columnists/423>
 <http://www.aaxnet.com/editor/edit043.html>
 <http://kadaitcha.cx/vista/dogsbreakfast/index.html>
                        cbfalconer at maineline dot net



-- 
Posted via a free Usenet account from http://www.teranews.com

"CBFalconer" <cbfalconer@yahoo.com> wrote in message 
news:4648D60D.61D60C05@yahoo.com...
> Tilmann Reh wrote:
>> CBFalconer schrieb:
>>
>>>> The OP didn't give an input range or accuracy requirement so its
>>>> hard to guess what is best. The thing we do know is that its for
>>>> an ARM7, which has a reasonable multiplier, so better than linear
>>>> shouldn't be a issue.
>>>
>>> I believe he specified that he was dealing solely with integers.
>>
>> But the represented values are not integers, that's why I mentioned
>> fixed point arithmetics.
>
> I assumed all integers.  Thus the bit position counter.

You also seem to have assumed log2(x). If we assume a base of the 65536th 
root of 2, say. then intger in and out would be equivalent to log2(x) fixed 
point out with 16-bit fraction. So, even assuming integers in and out isn't 
sufficient explaination :)

Peter 

Peter Dickerson wrote:
> "CBFalconer" <cbfalconer@yahoo.com> wrote in message
>> Tilmann Reh wrote:
>>> CBFalconer schrieb:
>>>
>>>>> The OP didn't give an input range or accuracy requirement so its
>>>>> hard to guess what is best. The thing we do know is that its for
>>>>> an ARM7, which has a reasonable multiplier, so better than linear
>>>>> shouldn't be a issue.
>>>>
>>>> I believe he specified that he was dealing solely with integers.
>>>
>>> But the represented values are not integers, that's why I mentioned
>>> fixed point arithmetics.
>>
>> I assumed all integers.  Thus the bit position counter.
> 
> You also seem to have assumed log2(x). If we assume a base of the
> 65536th root of 2, say. then intger in and out would be equivalent
> to log2(x) fixed point out with 16-bit fraction. So, even assuming
> integers in and out isn't sufficient explaination :)

Of course it is sufficient.  Changing bases is a matter of
multiplying by some constant.  Base 2 gave a relatively wide range
of logs, as compared to e and 10.

-- 
 <http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
 <http://www.securityfocus.com/columnists/423>
 <http://www.aaxnet.com/editor/edit043.html>
 <http://kadaitcha.cx/vista/dogsbreakfast/index.html>
                        cbfalconer at maineline dot net



-- 
Posted via a free Usenet account from http://www.teranews.com