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

Correction - the c bit position is the log.

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

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

... snip ...

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

CBFalconer schrieb:

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

Tilmann

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

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.