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

Rafael Deliano wrote:
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

Jack Crenshaw explains the whole thing (sprinkled throughout the book, but the area that especially applies here is on page 324, equation 10.53). I've used it to write fast approximation functions for several projects of the years.

Log in a nutshell:
Use log2() and scale the output as needed.
The highest set bit tells you the left-of-radix value.
The remaining bits represent the input in a range from 1.0 to 1.9999...

Choose a table size (2^N) and the number of terms in the interpolation polynomial (3 usually works very well).

Generate an A[] table of the log2(x) where x goes from 1.0 to 1+((2^N-1)/(2^N)).
Make a table of "forward differences" (call it F)
where F[i]=A[i+1]-A[i].
Make another difference table, G[i]=F[i+1]-F[i].
Now you can make B[] and C[] tables for the run-time code.
C[i]=G[i]/2
B[i]=F[i]-G[i]
run time code is:
normalize x and remove MSB
int i = x>>alphaBits // get table index
int alpha = ((1<<alphaBits)-1) & x; // get delta between 1.0 and 1.999
retval = (C[i] * alpha) >> shift1
retval += B[i ]
retval *= alpha
retval >>= shift2
retval += A[i]


The shift1 and shift2 are a function of your table size (N) and any extra scaling you might have done to improve the resolution of B[] and C[]. Crenshaw explains it all with Taylor series and shows how easy it is to extend to D[] or higher order tables. It comes down to a trade-off between accuracy, speed, and table space.

I usually start by analyzing the error vs. table size in a spread***, then use a C program so that I can test it over all possible input values. The C code might get hand converted to asm if I need the speed.

HTH,
Bob
.