As we discussed earlier, sometimes the best approach to implement a costly operation is to do without it altogether. You can often rewrite your computations so that they'll use simpler/faster operations.
For instance, it's very common to avoid using the square root function. Likewise, you can often transform your formulas so you can avoid using log.
If this approach fails for any reason, and you absolutely need a log function, there are ways to implement it efficiently (at the expense of accuracy). There are polynomial approximations, for instance, which I think is what the above posted library does (along with a trick using IEEE FP format). It should be pretty fast already. If it's still not fast enough, and you can deal with even less accuracy, there's a very simple way of getting a log2(x). Scale x so you make it an integer with the max resolution you can, and then you can compute the integer log2(n) ultra fast using the ARM clz instruction for instance. If you're using GCC and don't want to mess with assembly directly, you can use one of the __builtin_clz() built-in functions.
Example of fast integer log2 in C (GCC only though!):
static inline uint8_t Log2Int(uint32_t n)
{
return (uint8_t)(8*sizeof(n) - 1 - ((uint8_t) __builtin_clzl(n)));
}
Then you can scale it back (scaling x with a multiplication such that n = [a.x] => log2(x) ~ Log2Int(n) - log2(a)
Of course the resolution is limited, but it could be enough.
If you need more accuracy, you can further compute the fractional part of the log2 up to a certain number of bits. I wrote the following function for instance:
// Binary log2(n) with nFrac fractional bits.
// Assumes: n >= 1
//
float BinaryLog2b(uint32_t n, uint8_t nFrac)
{
const uint32_t n1 = 1;
uint8_t nLog2, i;
float x, y, b;
nLog2 = Log2Int(n);
x = ((float) n) / ((float)(n1 << nLog2));
y = (float) nLog2;
for (i = 0, b = 0.5f; i < nFrac; i++, b *= 0.5f)
{
x = x * x;
if (x >= 2.0f)
{
y += b;
x *= 0.5f;
}
}
return y;
}
Tested on x86-64: with nFrac = 8, for instance, it's still 3 times faster than the std math lib log2() function, and with a decent accuracy. But it takes an integer input. Could typically be used with fixed-point, or after scaling a FP number as I said.
Home
Help
Search
Login
Register
