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

Hello all,

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)?

Thanks,
Tilmann

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

Tilmann Reh wrote:

> Hello all,
> 
> 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)?

Tilman,
the binary log of a number mainly counts the number of bits the most 
signifgicant bit is moved from One. Then comes the conversion of the 
number itself.

Rene
-- 
Ing.Buero R.Tschaggelar - http://www.ibrtses.com
& commercial newsgroups - http://www.talkto.net

Rene Tschaggelar schrieb:

>> Can anyone point to fixed-point logarithmic routines I could use (resp.
>> tailor to my needs)?
> 
> the binary log of a number mainly counts the number of bits the most 
> signifgicant bit is moved from One. Then comes the conversion of the 
> number itself.

I know.

I was hoping to get/see a working sample for the latter part ("the
conversion of the number itself"), or even for the complete number...

Tilmann

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

> Can anyone point to fixed-point logarithmic routines I could use 
> (resp. tailor to my needs)?

Good book with an idea on that : 
  Crenshaw "Math Toolkit for Real Time Programming" CMP Books 2000

I adapted it to 6502/FORTH but 
   http://www.embeddedforth.de  Heft 9 
is no longer free. But there was a preprint in
   http://www.forth-ev.de/filemgmt_data/files/4d2004_1.pdf
   ( FORTH e.V. has now all issues of the magazine back to 1984
available
     for download, http://www.forth-ev.de/filemgmt/viewcat.php?cid=2
     but no good index yet ).
Both descriptions are in german.  

  Beyond that one would have to dig out literature on logarithmic 
numbersystems. The best known published implementation for a 
controller was FOCUS for the Z80 in assembler.
I think i have the description als pdf ( scan from book, bulky ) 
somewhere and the source typed in, but didn�t get to porting 
it to 6502/FORTH yet. 

MfG  JRD

Rafael Deliano schrieb:

>> Can anyone point to fixed-point logarithmic routines I could use 
>> (resp. tailor to my needs)?
> 
> Good book with an idea on that : 
>   Crenshaw "Math Toolkit for Real Time Programming" CMP Books 2000

Is it worth buying it?

> I adapted it to 6502/FORTH but 
>    http://www.embeddedforth.de  Heft 9 
> is no longer free. But there was a preprint in
>    http://www.forth-ev.de/filemgmt_data/files/4d2004_1.pdf
>    ( FORTH e.V. has now all issues of the magazine back to 1984
> available
>      for download, http://www.forth-ev.de/filemgmt/viewcat.php?cid=2
>      but no good index yet ).
> Both descriptions are in german.  

Thanks for the link. The description sounds good, unfortunately the
listing appears somehow broken (at least it's not readable to me...).

>   Beyond that one would have to dig out literature on logarithmic 
> numbersystems. The best known published implementation for a 
> controller was FOCUS for the Z80 in assembler.

I think I remember that... But this time I just need a few single
logarithms within a great mass of linear arithmetics, so I think a log
numbersystem wouldn't help me much.

However, the bitlog function appears to be useful here, so I would
greatly appreciate more info on it.

Tilmann

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

"Tilmann Reh" <tilmannreh@despammed.com> wrote in message 
news:464433e9$0$23133$9b4e6d93@newsspool1.arcor-online.net...
> Hello all,
>
> 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)?

I had a need for log of an integer with the result fixed point. For fixed 
point input there is just a constant difference. I didn't hugely accurate 
results, but the results are better than I needed. Input was signed 32-bit 
integer and result was ln(x) as 32-bit fixed point with 24-bit fraction. 
log10(x) was then obtained by scaling. There is no particular reason why the 
input can't be unsigned.

However, the method requires a 256-entry 32-bit int table, a 256-entry byte 
table and one integer divide :-(

I can't give out the source code because of copyright constraints but I'm 
happy to explain the algorithm.

Peter 

>>   Crenshaw "Math Toolkit for Real Time Programming" CMP Books 2000 
> Is it worth buying it?
The title is somewhat misleading: its less "embedded" but 
more "numeric", but a good read and i think it wasn�t expensive. 

> unfortunately the listing appears somehow broken (at least it's not 
> readable to me...).
Ah well: thats 6502 postfix assembler. IO ( to FORTH ) is via a 16 bit 
stack simulated by the X-register.
I don�t have the 6502-manual online, but the 68HC08 is similar
( but bigendian ):
http://www.embeddedforth.de/GP32/08asm.pdf

Cleaned up original layout may be easier to read: 
http://www.embeddedforth.de/temp/scanbit.pdf

MfG JRD

Peter Dickerson schrieb:

> I had a need for log of an integer with the result fixed point. For fixed 
> point input there is just a constant difference. I didn't hugely accurate 
> results, but the results are better than I needed. Input was signed 32-bit 
> integer and result was ln(x) as 32-bit fixed point with 24-bit fraction. 
> log10(x) was then obtained by scaling. There is no particular reason why the 
> input can't be unsigned.
> 
> However, the method requires a 256-entry 32-bit int table, a 256-entry byte 
> table and one integer divide :-(
> 
> I can't give out the source code because of copyright constraints but I'm 
> happy to explain the algorithm.

So, please start the explanation. :-)

Tilmann

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

Rafael Deliano schrieb:

>> unfortunately the listing appears somehow broken (at least it's not 
>> readable to me...).
> Ah well: thats 6502 postfix assembler. IO ( to FORTH ) is via a 16 bit 
> stack simulated by the X-register.
> I don�t have the 6502-manual online, but the 68HC08 is similar
> ( but bigendian ):
> http://www.embeddedforth.de/GP32/08asm.pdf
> 
> Cleaned up original layout may be easier to read: 
> http://www.embeddedforth.de/temp/scanbit.pdf

Obviously I'm not used to "postfix assembler" - for me, this one appears
as broken as the other... :-)

Tilmann

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

Peter Dickerson wrote:

> I had a need for log of an integer with the result fixed point. For fixed 
> point input there is just a constant difference. I didn't hugely accurate 
> results, but the results are better than I needed. Input was signed 32-bit 
> integer and result was ln(x) as 32-bit fixed point with 24-bit fraction. 
> log10(x) was then obtained by scaling. There is no particular reason why the 
> input can't be unsigned.

Since the logarithm function is undefined for negative numbers,
why would an implementation allow anything but unsigned input?